java - 你能帮我计算一下这个算法的时间复杂度吗？

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);
    }
}

谁能把答案写给我？

例如，我知道for循环中的操作数是2N+2，

和count++中的操作数；是N

但是其他部分呢。

Answer 1

时间复杂度为O(2<sup>n</sup>) .瓶颈是:

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

自 k i 的每次迭代都呈指数增长.

在i 'th 迭代，k = 2<sup>i-1</sup> .这意味着迭代所有来自 j 的值至 k是O(k) = O(2<sup>i</sup>) .

现在，对所有迭代进行总结:

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

Where last equality comes from sum of geometric series

Note that the next inner loop:

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

不影响时间复杂度(就渐近符号而言)，因为它添加了 O(n) i 每次迭代的时间，这很快被第一个内循环的指数行为所抑制。

如果要统计count的值最后，它是第一个内循环的总和，即 (2<sup>n</sup>)-1 ，以及第二个内循环，即 sum{n | for each i} = n<sup>2</sup> .