algorithm - 具有相关索引的三重嵌套 Big O

Question

我正在努力寻找这个问题的大 O，但我在处理第三个嵌套循环时遇到了困难。这是代码

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

i forloop 显然是 O(n)。

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

但我不确定如何考虑 k forloop。我知道对于一个完整的 j 循环(1 到 n)，总和类似于 (n + n-4 + n-6 + ...) = sum_{k=1}^n (n - k^2)，但我不确定从那里去哪里。

任何关于如何进行的建议都很棒!

Answer 1

当j大于sqrt(n)时，不进入内循环。当i大于sqrt(n)时也是如此，因为j是从i开始的。

因此，我们可以将完成的工作分为两种情况:

• 在 i 和/或 j 大于 sqrt(n) 的迭代中:k 循环不输入，不难证明外层两个循环完成的时间复杂度为Theta(n^2)。
• 在 i 和 j 都小于 sqrt(n) 的迭代中:前两个循环运行到 sqrt (n) 次，最后一个循环最多运行 n 次，因此总迭代次数的上限为 O(sqrt(n) * sqrt(n) * n) = O (n^2).

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