为什么两个循环的时间复杂度不是O(n*2^n)？

Question

我的教授说，这种方法的时间复杂度为O(2^n)。

我认为这种方法的时间复杂度应该是O(n * 2^n)，因为

外部for循环的成本为O(n)

内部for循环的成本为O(2^n)

public static int loop(int n) {
    int j = 1;
    for (int i = 0; i < n; i++) {
        for (int k = j; k > 0; k--) {
            System.out.println("Hello world");
        }
        j *= 2;
    }
    return j;
}

- Peter

---

内部循环并不总是迭代O(2^n)次；只有在最后的常数次迭代中才是O(2^n)。例如，在中间，它大约是O(1.4^n)，因为2^(n/2)大约等于1.4^n。 - kaya3

Answer 1

考虑以下情况：

对于 i = 0 ：j = 1 -> 2^0 对于 i = 1 ：j = 2 -> 2^1 对于 i = 2 ：j = 4 -> 2^2 对于 i = 3 ：j = 8 -> 2^3 ....

对于 i = n-1 ：j = 2^n-1 如果将它们全部加起来:

2^0 + 2^1 + 2^2 +.....+2^(n-1) => order of 2^(n) -> 2^(n) - 1 to be precise

因此时间复杂度为 O(2^n)

- SomeDude

---

所以，这是因为n-1项的总和为2^n - 1，而第2^n项的总和等于2^(n+1) - 1，这简化为O(2^n)？ - Peter

@Peter 是的，我们将复杂度作为输入规模函数来衡量。 - SomeDude

Answer 2

您是正确的，外层循环运行O（n）次。您也正确地指出，内层循环完成的最长时间是O（2 ^ n）。因此，说这里完成的工作不超过O（n2 ^ n）是没有问题的。

但是，这个界限并不紧密，因为这种分析假定内层循环的每次迭代所做的工作等于内层循环在每次迭代中完成的最大工作量。类比推理：如果我有十只动物，其中最重的一只是1000公斤的大象，我可以正确地说，通过将动物数量乘以最大质量，这些动物的总重量最多为10,000千克，但这可能是一个非常高估的数字。我最好只添加每个单独动物的重量以查看结果。

在这种情况下，我们需要观察第i次通过内部循环时，我们花费2^ i个迭代。这意味着完成的总工作量大约是：

2 ^ 0 + 2 ^ 1 + ... + 2 ^ n-1。

这是一个几何级数的总和，计算结果为2 ^ n-1，因此是总的O（2 ^ n）时间上限。回到动物的例子，如果我的动物是1kg的松鼠，10kg的乌龟，100kg的人类和1000kg的大象，几乎所有的质量都由大象占据，因为重量增长得太快了。几何级数的正式表达使这个想法在数学上得到了证实。

- templatetypedef