三重嵌套的Big O符号与相关指数

Question

我正在研究如何找到这个问题的时间复杂度，但是第三个嵌套循环让我有些困难。以下是代码：

for (int i = 1 to n)
  for (int j = i to n)
    for (int k = j*j to n)
      //some constant operation

i循环显然是O(n)。

j循环是(n + n-1 + n-2 + ... + 2 + 1) = (n-1)n/2 = O(n^2)。

但是我不确定如何考虑k循环。我知道对于j的一个完整循环（从1到n），求和类似于(n + n-4 + n-6 + ...) = sum_{k=1}^n (n - k^2)，但我不确定该怎么继续下去。

请给出如何继续的建议，谢谢！

- GentleSaint

---

我认为你的求和公式有误。你说应该是(n + (n - 4) + (n - 6) + ... )，但实际上应该是(n - 9)而不是(n - 6)。 - nbro

提示：你能否在不改变结果的大O复杂度的情况下减少j循环的上限？ - interjay

Answer 1

当j大于sqrt(n)时，内部循环不会执行。同样地，当i大于sqrt(n)时，内部循环也不会执行，因为j从i开始。

因此，我们可以将工作分成两种情况：

1. 在i和/或j大于sqrt(n)的迭代中：不会进入k循环，并且很容易证明外部两个循环所做的时间复杂度是Theta(n^2)。

2. 在i和j都小于sqrt(n)的迭代中：前两个循环每次运行最多sqrt(n)次，最后一个循环最多运行n次，因此总迭代次数的上限是O(sqrt(n) * sqrt(n) * n) = O(n^2)。

在这两种情况下，时间复杂度的上限都是O(n^2)，第一种情况表明它也是一个下限。因此，总时间复杂度是Theta(n^2)。

- interjay

---

这似乎是有道理的，但是当运行一个程序来测试我在k循环中的次数时，我得到的结果比理论极限要低得多。例如，与理论相比，我的程序结果低了一个数量级。这样做可以吗？为什么会发生这种情况？ - GentleSaint

@GentleSaint 次数并不重要，因为在大O符号中涉及到一个常数因子。但是，如果你取一个很大的n，然后检查n和2n的迭代次数，你会发现对于2n来说，它大约是n的4倍。 - interjay

没错，现在清晰多了。非常感谢你！ - GentleSaint

第三个循环运行的次数恰好为1*(n - 1*1 + 1) + 2*(n - 2*2 + 1) + 3*(n - 3*3 + 1) + ... + floor(sqrt(i))*(n - i*i + 1)，这比第二个循环运行的次数少。 - nbro