time-complexity - 嵌套循环的 Big O (int j = 0; j < i * i;++j)

Question

问题1

for (i = 0; i < n; i++) {
  for (j = 0; j < i * i ; j++){

  }
}
Answer: O(n^3)

乍一看，O(n^3) 对我来说很有意义，但我记得我之前做过的一个问题:

问题2

for (int i = n; i > 0; i /= 2) {
   for (int j = 0; j < i; j++) {
     //statement
   }
}
Answer: O(n)

对于问题 2，外层循环的复杂度为 O(log n)，内层循环的复杂度为 O(2n/log n)，结果为 O(n)。内部循环是 O(2n/log n) 因为 - 请参阅此处的解释: Big O of Nested Loop (int j = 0; j < i; j++)

---

为什么我们不像问题 2 那样做问题 1，因为在问题 1 中，j 也取决于 i，这意味着我们实际上应该取多少个的平均值迭代将发生在内循环中(正如我们在问题 2 中所做的那样)。

我的答案是:外循环为 O(n)，内循环为 O(n^2/n)，这会导致问题 1 的 O(n^2)。

Answer 1

你的答案是错误的。代码为θ(n3)。

要注意的是，内部循环需要 i² 步，最多为 n²，但外层循环迭代的一半至少为 (n/2)² = n²/4。

因此内部迭代总数最多为 n * n2 = n3 但至少为 n/2 * n2/4 = n3/8。

---

您的考虑是错误的，因为内部循环平均与 n² 次迭代成比例，而不是 n²/n。