i 1while i《ni i 2 這個演算法的時間

1樓：匿名使用者

你可以分析i，和迴圈次數之間的關係

i = 1, 2, 4, 8, 16 ...

所以假設迴圈次數是x。

那麼i = 2^x

條件是i <= n

2^x <= n

所以x <= logn

所以x 從1 到logn，一共執行迴圈體logn次，所以複雜度是logn

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

2樓：仁昌居士

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)。

3樓：匿名使用者

假設迴圈次數是x。

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

2^x <= n

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

4樓：匿名使用者

迴圈退出的條件為i > n

設第k次迴圈後退出迴圈

於是2^k > n

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

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

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

5樓：情人節

i的值規律：

1，2，4，8，16……

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

6樓：匿名使用者

時間複雜度復為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).

7樓：匿名使用者

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

8樓：匿名使用者

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

9樓：匿名使用者

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

常數階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))

i 1while i《ni i 2 這個演算法的時間

並聯的情況下，I1 I2 R2，並聯的情況下，I1 I2 R2 R1。

c 裡1 i 2是什麼意思2 i《1是什麼意思

在forintini2n1i提示陣列

相關推薦