运行时间是O(logn)还是O(n)?

Question

我对这个问题有些困惑。每一步似乎都将问题大小减半，这表明是O(logn)的时间复杂度。但如果你仔细思考一下，迭代的次数只是一个等比数列2 + 4 + 8 + ...小于n，这表明是O(n)的时间复杂度。请问有人能提供他们的见解吗？

for (int i=1; i < n; i=2i)
    for (int j=i; j < n; j++)
        // do something

- codeMonkey17

---

试试吧！这通常是检查你的直觉的好方法，尽管有时会误导。 - user2357112

另外请注意：j 从 i 开始，到 n 结束。那么内部循环要做多少工作呢？ - user2357112

你关于几何级数的评论是错误的。如果j从1变化到i，那就会成立。 - Paul Hankin

你的标题使用了小o，但是你的问题文本使用了大O... - AakashM

Answer 1

假设do something是Theta(1)，那么根据U2EF1的建议，算法应该是Theta(nlog(n))。

以下是如何找到双重求和的闭式公式的解释：

Sum p in [1, logn] (Sum j in [2^p, n] 1) =
Sum p in [1, logn] (n - 2^p) =
nlogn - Sum p in [1, logn] (2^p) =
nlogn - Theta(n) =
Theta(nlogn)

特别地，您可以使用闭式来计算几何级数中前n项的最终求和。或者您可以使用更为有限的变体，类似于“将n视为二进制数，例如1111，并注意如果您从p = 1到log（n）对每个幂2 ^ p进行求和，则再次得到n”。

闭式足以证明Theta界限，尽管您需要使用复杂度分析中的其他常见引理来展示步骤，例如Theta（nlogn）- Theta（n）= Theta（nlogn）。

- rliu

Answer 2

看起来正好是 sum(sum(1, j = (2^i)..n), i = 1..log(n)) = nlog(n) - 2n + log(n) + 2 = O(n log n)

- U2EF1

---

嗯，我理解你是如何得到sum(sum(1, j = (2^i)..n), i = 1..log(n))的，但我不确定你是如何得到等式右边的部分的:/ - codeMonkey17

Answer 3

复杂度为O(n log n)

首先举个例子以便更清楚： 当n为4时，外部循环迭代2次 当n为64时，外部循环迭代6次 因此，外部循环迭代log2(n)次。

解决方案： 在外部循环的第一次迭代中，“do somethings”语句运行n次 在外部循环的第二次迭代中，“do somethings”语句运行n-2次 在外部循环的最后一次迭代中，“do somethings”语句运行n-log2(n)次

因此，在程序的总执行过程中，“do somethings”语句运行n+n-2+n-4+...+n-log2(n)次。 它等于n*log2(n)-(1+2+4+8+...+log2(n)) = n*log2(n)-(2n-1)次。 因此，复杂度为o(n log n)

- Shahyad Sharghi

---

这个主张和证明都是错误的。在第二次迭代中它不会“运行n/2次”，而是运行n-2次。如果你把求和分开，你会发现它实际上是Theta(nlogn) - Theta(n) = Theta(nlogn)。 - rliu

Answer 4

一个好的方法是分别计算内部循环和外部循环的复杂度。一旦你这样做了，你就可以计算两者的乘积来得到总复杂度。

你也可以考虑每个循环需要多少步骤，这可以作为方法的一个良好的检查。按照之前的逻辑，很明显可以看出，由于 i 增长呈几何级数增长，实际上会发生的迭代次数将是其倒数，即 O(log n)。

如果你想知道在给定的 n 下有多少个内部循环将运行，很明显，由于每个 n 只有一个步骤，对于外部循环的给定结果，内部循环将是线性的。这给出了 O(n) 的复杂度。

这种方法返回一个 O(n log n) 的结果。

- Slater Victoroff

---

外层循环的复杂度应该是O(log(n))吗？不是，因为我们只需要log(n)步就可以超过n了。 - codeMonkey17

@codeMonkey17 外部循环的计算仅仅是计算需要运行多少个内部循环。根据您如何构建定义，您可以交换内部和外部循环的复杂性，但我认为这种方式更具直观性。 - Slater Victoroff

@codeMonkey17 我会更新答案，加入另一种解释。 - Slater Victoroff

@roliu 我回答了提出的问题，但上面的分析确实可以扩展到Theta界限。如果上面的分析对您不够清晰，我很抱歉，但是如果是“j=i/2; j < i; j++”这种情况，紧密边界只会是Theta(n)，我的方法会揭示出来。简单地意识到有一个与n成比例的重复量表明该问题的紧密边界不可能是Theta(n)。 - Slater Victoroff

@SlaterTyranus 我的评论并没有说上述算法有Theta(n)的限制，请再仔细阅读一下（实际上，您可以看看本页上我的回答，以了解我对Theta(nlogn)限制的证明）。您能否请解释一下以上呈现的逻辑是如何产生内部循环为j=0；j<i；j++的另一个情况中的Theta(n)限制的？因为这个算法确实具有Theta(n)时间复杂度。 - rliu