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

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循环中的nuber操作是2N + 2,

和count ++中的操作数; 是N.

但是对于其他部分呢.

Answer 1

时间复杂性是.瓶颈是:O(2n)

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

因为k每次迭代都会呈指数增长i.

在第二i次迭代中.这意味着从迭代所有的值到是.k = 2i-1jkO(k) = O(2i)

现在,总结所有迭代:

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

最后的平等来自几何系列的总和

注意下一个内循环:

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

不影响时间复杂度(在渐近符号方面),因为它O(n)为每次迭代增加了时间i,并且这可以通过第一个内部循环的指数行为迅速抑制.

如果你想计算最后的值count,它是第一个内部循环的总和,如上所述,和第二个内部循环,即.(2n)-1sum{n | for each i} = n2