為什麼該迴圈的時間複雜度為Olog2ninti

1樓：匿名使用者

因為從判斷語句上看i從1迴圈到n，但是迴圈體中每次迴圈i都乘以2，所以實際上迴圈體只執行了log2n次（這是個簡單的數**算吧！），而判斷時間複雜度一般都是看迴圈體的實際有效執行語句的次數，所以該迴圈的時間複雜度是o(log2n)。

為什麼該程式段的時間複雜度為o(n^{1/2})，{i=0;s=0;while(s<=n){i++;s=s+i;}}

2樓：匿名使用者

條件：while(s < t)

實際上bais的值如下du:

s = t = 1 + 2 + 3 + 4 +... + k, 實際上累加了k次

這是個等差數列zhi

求和 sn= n(a1+an)/2 = k*(1+k)/2 = t通過k*(1+k)/2=t求解daok, 當回k非常大時k和k+1等價,表示式可化簡為

答k^2 = t, k = t^(1/2), 這裡的t是已知的因此時間複雜度為o(n^1/2)

i=1； while（i<=n） i=i*2； 問時間複雜度為多少？為什麼答案為o（log（2）n）？

3樓：情人節

i的值規律：

1，2，4，8，16……

初始i=1(2的0次)，所以i的變化實際是2的x次，所以就是求式子2^x=n，x=log(2)n

4樓：匿名使用者

時間複雜度復為t(n),o(f(n))叫做漸制進時間複雜度。

當n趨近於無窮大時，t(n)=o(f(n))。此時o(f(n))也可叫時間複雜度。且lim t(n)/o(f(n))=常數，表示兩者的數量級相同。

因此本題中，無論f(n)=log2(n)或=log2(n)+1，lim t(n)/o(f(n))都等於常數，也就是說t(n)=o(f(n))，後者可以代表時間複雜度。而答案為了方便簡潔而寫成log2(n).

5樓：匿名使用者

假設n=8，那麼第一次迴圈後，i=2,第二次迴圈i=4，第三次i=8,第四次i=16

6樓：匿名使用者

在這個程式中，假設要執行y次，則i=i*2^y，由於i≤n，所以i*2^y≤n，考慮到i作為常數對比2的冪級數可忽略，得出最多執行2^y=n，則y=log2 n的結論。我初學，自己瞎琢磨，勿噴

7樓：匿名使用者

^按數量級遞復增排列，常見制的時間複雜度有：

常數階o(1),對數階o(log2n),線性階o(n),

線性對數階o(nlog2n),平方階o(n^2)，立方階o(n^3),...，

k次方階o(n^k),指數階o(2^n)。隨著問題規模n的不斷增大，上述時間複雜度不斷增大，演算法的執行效率越低。

1、一般情況下，演算法的基本操作重複執行的次數是模組n的某乙個函式f(n)，因此，演算法的時間複雜度記做：t(n)=o(f(n))

分析：隨著模組n的增大，演算法執行的時間的增長率和 f(n) 的增長率成正比，所以 f(n) 越小，演算法的時間複雜度越低，演算法的效率越高。

2、在計算時間複雜度的時候，先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出 t(n) 的同數量級（它的同數量級有以下：1，log(2)n，n，n log(2)n ，n的平方，n的三次方，2的n次方，n!），找出後，f(n) = 該數量級，若 t(n)/f(n) 求極限可得到一常數c，則時間複雜度t(n) = o(f(n))

分析下列演算法的時間複雜度 void f(int n) { int i=1; while (i<=n) i=2*i; }

8樓：倒霉熊

時間複雜度，就bai是執行次數du最多的那zhi個語句次數。

這段程dao序中，執行次數最內多的就是 i=2*i;

其執行容的次數為：

2*2*2*2*...........*2<=n假設為x次，

則 2^x <=n

2^x =n 可以推出 x = log2n所以，時間複雜度為 o(log2n)

這裡的2是log的下標。

9樓：小飛花兒的憂傷

設複雜度t(n)

那麼t(n) = 1 + t(n/2)

所以t(n) = log2(n)

下面程式段的時間複雜度是 ？ i=1； while（i<=n） i=i*2

10樓：仁昌居士

i=1； while（i<=n） i=i*2的時間複雜度copyo(log2n)。

整段**語句，中迴圈體只有乙個while（i<=n），執行的次數是：

i = 1，i = 1*2=2，判斷2是否小於等於n，是則繼續迴圈，否則跳出迴圈。

i =2，i = 2*2=4，判斷4是否小於等於n，是則繼續迴圈，否則跳出迴圈。

i =4  ，i = 4*2=8，判斷8是否小於等於n，是則繼續迴圈，否則跳出迴圈。

根據規律發現，迴圈次數由log2n決定，所以複雜度是o(log2n)。

11樓：匿名使用者

假設迴圈次數是x。

i = 1, 2, 4, 8, 16 ，i = 2^x條件是i <= n

2^x <= n

所以x <= log2n 一共執行迴圈體log2n次，所以複雜度是o(log2n)

12樓：匿名使用者

迴圈退出的條件為i > n

設第k次迴圈後退出迴圈

於是2^k > n

因此k > log2n 以2為底的對數，k的實際值為log2n上取整

因此時間複雜度為o(log2n)

為什麼for迴圈的時間複雜度是n+1呢

13樓：

for迴圈來是非常靈活的，其時間複雜自度並bai不一定是n+1。for迴圈語句的標準

du格式為：

for（表zhi達dao式1;表示式2;表示式3）

其執行順序為

表示式1;

while（表示式2）

通常我們熟悉的用法如：

for(i=0;i

從i=0開始判斷執行迴圈，到i=n-1都滿足迴圈條件，共執行n次迴圈體語句，時間複雜度為n；

若改為 i<=n，則執行到 i=n 共執行n+1次迴圈體語句，時間複雜度為n+1；

如果寫成

for(i=0;i

時間複雜度就變成n的平方了，也就是n*n；

另外for（表示式1;表示式2;表示式3）裡面的表示式1,2,3 可以是空語句，也可以是互不相關的三條語句，用起來都是很靈活的。具體我認為可以參考譚浩強寫的《c程式設計》關於迴圈語句部分的講解，說的比較詳細透徹。

時間複雜度o(log2^n)的迴圈語句

14樓：匿名使用者

錯了 明顯的程式

i的初始值應當為1.

這個迴圈執行的次數為以2為底n的對數次

15樓：匿名使用者

....就相當於2^m = n兩邊取以2為底的對數。就是m的值。

複雜度o(nlog2n)怎麼計算的？

16樓：匿名使用者

for(int j=1; j<=n; j*=2)這個迴圈最終執行的次數假設為x，則x次的時候j=2^x 。

當j>n時停止執行，於是2^x>n ，則可以認為該迴圈一共執行了log2(n)次。

所以該迴圈的時間複雜度為o(log2(n))，簡記為o(log n) ，忽略掉2的底數。

方法：1、首先，看外迴圈for（i=0；i2、再看內部迴圈，for（j=1；jn===》x=log2(n)。

3、如果把兩個迴圈合在一起看，也就是一共迴圈了n個x次，也就是log2(n)。

指出下列演算法的功能及時間複雜度 int fun(int n){ int i=1,s=1; while(s