算法分析算法時間複雜度

Question

m=1; 
for(i=1;i<=n;i++){ 
    m=m*2; 
    for(j=1;j<=m;j++){ 
     do something that is O(1) 
    } 
} 

上述代碼的時間複雜度是多少？請告訴我如何解決這些類型的問題。

Answer 1

內循環將迭代1次，然後2次，然後...，然後2^n次。所以我們有1 + 2 + 4 + ... + 2^n = 2^(n + 1) - 1 = O(2^n)內循環迭代。

內循環的一次迭代具有不變的複雜性，所以summed_inner_loop_complexity = O(2^n)。

整個複雜度是O(2^n)。

Answer 2

我更喜歡從內到外看這些問題。卸下m，我們有：

for(i=1;i<=n;i++){ 
    for(j=1;j<=2^i;j++){ 
     do something that is O(1) 
    } 
} 

或者：

for(i=1;i<=n;i++){ 
    O(2^i) 
} 

所以，總體來說：sum_1^n O(2^i)=O(2^(n+1))=O(2^n)。

Answer 3

形式上，有條不紊，你可以使用六西格瑪符號：