你能幫我計算一下這個算法的時間複雜度嗎？

Question

public static void complexityexample(int n) { 
    int count = 0; 
    int k = 1; 
    for (int i = 0; i < n; i++) { 
     for (int j = 0; j < k; j++) { 
      count++; 
     } 
     k *= 2; 
     for (int t = 0; t < n; t++) { 
      count++; 
     } 
     System.out.println(count); 
    } 
} 

任何人都可以給我寫答案嗎？

例如，我知道操作的那個nuber在for循環是2N + 2，

和在計數++操作的次數;是N

但是對於其他部分。

Answer 1

時間複雜度爲O(2n)。瓶頸是：成倍

for(int j = 0; j < k; j++){ 
    count++; 
} 

由於k增加i每次迭代。

在i'th迭代中，k = 2i-1。這意味着迭代從j到k的所有值是O(k) = O(2i)。

現在，總括起來，爲所有的迭代：

 
20 + 21 + 22 + ... + 2n-1 = 2n - 1 

當最後一個等式來自sum of geometric series

注意，接下來的內環：

for (int t = 0; t < n; t++) { 

不影響時間複雜性（根據漸近表示法），因爲它爲i的每次迭代增加了O(n)時間，並且這得到q被第一個內部循環的指數行爲劇烈抑制。

如果要在最後對count進行計數，它是第一個內循環的總和，其爲(2n)-1，第二個內循環爲sum{n | for each i} = n2。

Answer 2

（2^N）+（N * N）

作爲它們的主循環是

for (int i = 0; i < n; i++) { 

2^n的：

for (int j = 0; j < k; j++) { 
     count++; 
    } 

和N * N從：

for (int t = 0; t < n; t++) { 
     count++; 
    } 

Answer 3

第1行）1操作。

第2行）2個操作。

第3行）1 + n + 1 + n = 2N + 2。

4）2 N + 2

5）N

7）N

9）2 N + 2

10）N

13）1

這是正確的嗎。

經過數學計算，最終的結果是：14N^2 + 22N + 11 - 操作。

Answer 4

使用西格瑪符號的精確方法將是：

經驗證實：

當n = 10，總的迭代次數是1123

當n = 25，整個迭代的次數是33555056.

當n = 50時，它需要永遠執行（我不得不改變變量從int類型到long類型）。

確實，這個非多項式算法很昂貴。