algorithm - 我被时间复杂度困住了

Question

我正在研究算法的时间复杂度，但我遇到了一些问题。你能帮我找出下面代码的时间复杂度吗？谢谢。

x=1;
for(i=0; i<=n-1; i++){
        for(int j=1; j<=x; j++)
            std::cout<<j<< std::endl;
        x =x*2;
    }

标签： algorithmtime-complexity

Answer 1

以下是我的思考过程的演练：

1. 第一个 for 循环运行n时间，因此时间复杂度为O(n)。
2. 随着第一个 for 循环的进行，第二个 for 循环的循环次数增加了两倍，因此时间复杂度为O(2^n)。
3. 将两者结合起来，看起来代码的时间复杂度为O(n*2^n)。
4. 但是，你想得更深一点，这是不正确的。
5. 如果考虑第二个 for 循环运行的循环数，则为 1、2、4、8、...、2^(n-2)、2^(n-1)。
6. 因此，循环的总数将是 2^(n-1) + 2^(n-2) + ... + 2^1 + 2^0。
7. 对于任何给定的 x，x + x/2 + x/4 + ... + 2 + 1 = 2*x - k（其中 k 的值取决于）。
8. 应用相同的概念，循环的总数为 2*2^(n-1)。
9. 结果，整体时间复杂度为O(2^n)。