以下代码的时间复杂度（用大O表示法）是多少？

Question

我只是想知道以下代码的时间复杂度。

在我看来，以下代码的时间复杂度（大O）应该是O(n^4)。

你们觉得呢？

int result = 0;
for(int i =1; i<n*n; i++){
  for (int j=i; j*j <n; j++){
    for(int k =j; k*k <n; k++){
      result++;
     }
  }
}

- Lawrence Wong

---

做一个实验吧。运行n=1到100的代码，并在每次运行时打印出“结果”。这会让你认为O(n^4)很不可能是正确答案。另一方面，“结果”的值并不能可靠地给出时间复杂度。 - gnasher729

Answer 1

我认为它是 n^(2.75)：

- outer loop: n^2
- first inner loop is sqrt(n)
- second inner loop is sqrt(sqrt(n))

总计：

n^2 * sqrt(n) *  sqrt(sqrt(n)) = n^(2+ 0.5 + 0.25) = n^(2.75)

- Nir Alfasi

---

两个问题都错了：内部循环不是sqrt(sqrt(n))。如果用“for(j=i;j<sqrt(n);++j)”和“for(k=j;k<sqrt(n);++k)”替换两个循环，这一点显而易见。另一个问题是当i>sqrt(n)时，j循环根本没有执行；只需花费常数时间来检查它是否执行。“result”将被设置为O(n^1.5)。外部循环执行n^2次，使整个代码的时间复杂度为O(n^2)。 - gnasher729

@gnasher729 那个分析可能值得发布为一个单独的答案。 - DPenner1

Answer 2

使用Σ符号进行正式步骤（需要验证）将产生以下结果：

- Mohamed Ennahdi El Idrissi