1樓：匿名使用者
演算法1是最壞情況執行n/2次，也就是o(n);
演算法2是執行次數是[lgn]+1，也就是o(lgn)演算法3是最壞情況執行[√n]-1次，這就是o(√n)其中，lg是以10為底的對數。[ ]是向下取整。
如何計算一個演算法的時間複雜度
2樓：匿名使用者
求解演算法的時間複雜度的具體步驟是：
⑴找出演算法中的基本語句；
演算法中執行次數最多的那條語句就是基本語句，通常是最內層迴圈的迴圈體。
⑵計算基本語句的執行次數的數量級；
只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函式中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的係數。這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：增長率。
⑶用大ο記號表示演算法的時間效能。
將基本語句執行次數的數量級放入大ο記號中。
如果演算法中包含巢狀的迴圈，則基本語句通常是最內層的迴圈體，如果演算法中包含並列的迴圈，則將並列迴圈的時間複雜度相加。例如：
for(i=1;i<=n;i++) x++; for(i=1;i<=n;i++)
for(j=1;j<=n;j++) x++; 第一個for迴圈的時間複雜度為ο(n)，第二個for迴圈的時間複雜度為ο(n2)，則整個演算法的時間複雜度為ο(n+n2)=ο(n2)。
常見的演算法時間複雜度由小到大依次為：
ο(1)＜ο(log2n)＜ο(n)＜ο(nlog2n)＜ο(n2)＜ο(n3)＜…＜ο(2n)＜ο(n!)ο(1)表示基本語句的執行次數是一個常數，一般來說，只要演算法中不存在迴圈語句，其時間複雜度就是ο(1)。ο(log2n)、ο(n)、ο(nlog2n)、ο(n2)和ο(n3)稱為多項式時間，而ο(2n)和ο(n!
)稱為指數時間。電腦科學家普遍認為前者是有效演算法，把這類問題稱為p類問題，而把後者稱為np問題。
這隻能基本的計算時間複雜度，具體的執行還會與硬體有關。
3樓：線雍厙夏蓉
這裡主要是計算count++;執行的次數。
i=1的時候：
j=1k=1
執行1次；
i=2的時候
j=1k=1
j=2k=1,2
執行3次；
i=3的時候
j=1k=1
j=2k=1,2
j=3k=1,2,3
執行6次；
依次類推
i=n的時候，
執行n*(n+1)/2
總共執行1+3+6+n*(n+1)/2=n(n+1)(n+2)/6次。
n(n+1)(n+2)/6的最高次項是3，所以它的時間複雜度是o(n^3).
分析下列演算法的時間複雜度。麻煩也告訴一下怎樣算的，謝謝！
4樓：
每當呼叫這個函式時會產生2個遞迴分支，所以時間複雜度是o(2^n)。
n==1時，呼叫1次rec(1)，
n==2時，呼叫1次rec(2)，2次rec(1)，n==3時，呼叫1次rec(3)，2次rec(2)，4次rec(1)，
以此類推，總的呼叫次數為2^0+2^1+2^2+...+2^(n-1)=2^n-1，
因為函式內不存在迴圈，t(n)=(2^n-1)*1=2^n-1，存在正的常數c,n0使得對於任意n>=n0時有t(n)<=c*2^n，
所以這個時間複雜度是o(2^n)。
分析下面演算法（程式段）給出最大語句頻度 ，該演算法的時間複雜度是__ __。
5樓：愈升榮其寒
分析每一次bai迴圈可以發現du，當迴圈執zhi
行10次後x>100，y方才減1，此時daox被複原為回91；
如此下去，由於答每執行10次迴圈才使y減1，所以迴圈體執行100*10次，也就是說if語句判斷執行了1000次（但裡面的y--執行了100次）。至於時間複雜度，你現在資料都給定值了那不就是o(1)嗎……如果x、y沒給初值，則粗略地說應該為o(y)（或者說是o(10y)）。
6樓：匿名使用者
一樓的回答是sb，希望那些沒好好學演算法的人就別在這裡禍害學生。
版時間複雜度很好算，權
實際上它是一個1+2+3.....+m=n的過程。等於n後迴圈終止。m好算吧？m=根號下（2n+1/4）-1/2.
所以時間複雜度是o(根號n).
7樓：匿名使用者
s=1+2+3+.....+i=【（1+i）i/2】 所以時間複雜度是o（√n） 根號不好打 反正就是根號下的n 8樓：匿名使用者 這段程式是錯的。. 正確的應該是: i=s=0; while (s do 複雜度是n 只有一次迴圈 沒有巢狀迴圈. 這個演算法的時間複雜度是什麼，分析過程大概說一下 9樓：大空翼 只是一個for迴圈，所以時間複雜度：t(n)=o(n)你這個函式不清楚在表達什麼，在提問前也不把內函式的作用先描述容下。 我的理解是把數值e插入到表的第i個位置上，如果位置i在當前位置p的 後面，則直接插入； 否則如果在前面，則將位置i到位置p的資料往後退1位，然後插入i。 有個問題是，如果位置i 等於 位置p 時，就不執行for迴圈，也就是不執行插入資料 10樓：starveclt溪花 你這個是什麼. 我看不懂啊.. 請問遞迴演算法的時間複雜度如何計算呢? 11樓：木子青耶 遞迴演算法的時間複雜度在演算法中，當一個演算法中包含遞迴呼叫時，其時間複雜度的分析會轉化為一個遞迴方程求解，常用以下四種方法： 代入法的基本步驟是先推測遞迴方程的顯式解，然後用數學歸納法來驗證該解是否合理。 迭代法的基本步驟是迭代地遞迴方程的右端，使之成為一個非遞迴的和式，然後通過對和式的估計來達到對方程左端即方程的解的估計。 這個方法針對形如「t(n) = at(n/b) + f(n)」的遞迴方程。這種遞迴方程是分治法的時間複雜性所滿足的遞迴關係。 即一個規模為n的問題被分成規模均為n/b的a個子問題，遞迴地求解這a個子問題，然後通過對這a個子間題的解的綜合，得到原問題的解。 可以將某些遞迴方程看成差分方程，通過解差分方程的方法來解遞迴方程，然後對解作出漸近階估計。 12樓：泡影果果 1、遞迴 是指對一個問題的求解，可以通過 同一問題的更簡單的形式的求解來表示. 並通過問題的簡單形式的解求出複雜形式的解. 遞迴是解決一類問題的重要方法. 遞迴程式設計是程式設計中常用的一種方法，它可以解決所有有遞迴屬性的問題，並且是行之有效的. 但對於遞迴程式執行的效率比較低，無論是時間還是空間都比非遞迴程式更費，若在程式中消除遞迴呼叫，則其執行時間可大為節省. 以下討論遞迴的時間效率分析方法，以及與非遞迴設計的時間效率的比較. 2、時間複雜度的概念及其計算方法 演算法是對特定問題求解步驟的一種描述. 對於演算法的優劣有其評價準則，主要在於評價演算法的時間效率，演算法的時間通過該演算法編寫的程式在計算機中執行的時間來衡量，所花費的時間與演算法的規模n有必然的聯絡，當問題的規模越來越大時，演算法所需時間量的上升趨勢就是要考慮的時間度量。 演算法的時間度量是依據演算法中最大語句頻度（指演算法中某條語句重複執行的次數）來估算的，它是問題規模n的某一個函式f(n). 演算法時間度量記作：t（n）=o（f（n）） 。 它表示隨問題規模n的增大，演算法執行時間的增長率和f（n）的增長率相同，稱作演算法的時間複雜度，簡稱時間複雜度[2]。 例如下列程式段： （1）x=x+1;（2）for(i=1;i<=n;i++) x=x+1;（3）for(j=1;j<=n;j++) for(k=1;k<=n;k++) x=x+1. 以上三個程式段中，語句x=x+1的頻度分別為1，n，n2，則這三段程式的時間複雜度分別為o（1），o（n），o（n2）。 求解過程為：先給出問題規模n的函式的表示式，然後給出其時間複雜度t（n）。 但是在現實程式設計過程中，往往遇到的問題都是比較複雜的演算法，就不能很容易地寫出規模n的表示式，也比較難總結其時間複雜度. 遞迴函式就是屬於這種情況. 下面舉例說明遞迴函式的時間複雜度的分析方法。 請說明下列演算法的時間複雜度。 13樓：匿名使用者 第一個是 o(8*n) 去常數項就是 o(n) 第二個是 o（m*n） x+=2和x++ 的複雜度是一樣的 都是o（1） 這也是為什麼在高版精度之類的演算法裡 用四權位、八位分割後 可以提高速度的原因 14樓：匿名使用者 （1）o(n)。外層for迴圈 o(n)；內層for迴圈o(1)，因為是常數個迴圈；x+=2為o(1)。則總的時間複雜度為o(n)。 （2）o(n^2)。外專層for迴圈o(n)；內層屬for迴圈o(n)；兩者都是線性時間複雜度。x++為o(1)。則總的時間複雜度為o(n^2)。 15樓：匿名使用者 (1) void sf1 (int n)f(n)=1+n+1+（n+1）*8+（n+1）*8f(n)=2+n+16*（n+1） f(n)=18+17n t(n)=o(f(n))=o(18+17n)=o(n)(2) void sf2 (int n, int m){ for (i=0; i， 答t(n)=o(f(n))=o(n+2n²)=o(n²) 快速排序演算法在平均情況下的時間複雜度為 求詳解 16樓：匿名使用者 時間複雜度為o(nlogn) n為元素個數 1. 快速排序的三個步驟： 1.1. 找到序列中用於劃分序列的元素 1.2. 用元素劃分序列 1.3. 對劃分後的兩個序列重複1,2兩個步驟指導序列無法再劃分 所以對於n個元素其排序時間為 t(n) = 2*t(n/2) + n （表示將長度為n的序列劃分為兩個子序列，每個子序列需要t(n/2) 的時間，而劃分序列需要n的時間） 而 t(1) = 1 （表示長度為1的序列無法劃分子序列，只需要1的時間即可） t(n) = 2^logn + logn * n （n被不斷二分最終只能二分logn次（最優的情況,每次選取 的元素都均分序列）） = n + nlogn 因此t(n) = o(nlogn) 以上是最優情況的推導，因此快速排序在最優情況下其排序時間為o(nlogn),通常平均情況 我們也認為是此值。 在最壞情況下其會退化為氣泡排序，t(n) = t(n - 1) + n (每次選取的元素只能將序列劃分為 一段，即自身是 最小元素或最大元素) 因此t(n) = n * (n-1) / 2 相當於o(n^2) 17樓：匿名使用者 時間複雜度為o（nlogn）n是多少元素 1。快速排序的三個步驟： 1.1。查詢序列用於劃分的序列中的元素 1.2元素劃分的序列 1.3 1,2兩個步驟的過程不斷重複，兩個序列劃分指導序列不能被細分 n個元素的排序條件為t（n）= 2 * t（n / 2個）+ n（表示序列分為兩個子序列中的n的長度，每個子序列需要到t（n / 2個） 時間除以 t（1）= 1（序列的長度不能被劃分為子序列，序列的n個）只需要1罐） t（n）= 2 ^ logn + logn * n（n為不斷二分法最後只有兩點：logn（最佳，各選擇 平均序列的元素）） = n + nlogn 因此，t（n）= o（nlogn ） 以上是派生的理想情況下，快速排序排序在最佳的情況下，時間為o（nlogn）通常平均 我們也相信，這個值。 在最壞的情況下，它會淪為氣泡排序，t（n）= t（n - 1個）+ n（每次選擇元素序列分為 一些，這是他們自己的元素是最小的或最大的元素） t（n）= n *（n-1）/ 2，相當於為o（n ^ 2） 我來舉個例子說明 比如一種排序演算法的時間複雜度是 o n 那麼執行時間就是正比於要素個數n,另一種排序演算法的時間複雜度是o n logn 那麼執行時間就正比於n logn 所以n足夠大的情況下，總是第一種演算法快.但是，如果n不是很大，那麼具體的運算時間並不一定都是前一種演算法快，比如剛才的第一... 對於排序 演算法，平均時間複雜度 插入排序 o n 2 氣泡排序 o n 2 選擇排序 o n 2 快速排序 o n log n 堆排序 o n log n 歸併排序 o n log n 基數排序 o n 希爾排序 o n 1.25 有一個時間複雜度的排列順序，依次為 1 log2n n nlog2... 1 時間複雜度 1 時間頻度 一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機執行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數...演算法時間複雜度與執行時間的關係演算法的空間複雜度於時間複雜度的關係？
以下哪個排序演算法的最壞時間複雜度是
時間複雜度的定義，C 中時間複雜度是什麼意思