3

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

我认为下面代码的时间复杂度(大 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++;
     }
  }
}
4

2 回答 2

2

在我看来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)
于 2013-08-11T05:09:04.930 回答
0

使用 Sigma 表示法的正式步骤(需要验证)将产生以下结果:

在此处输入图像描述 在此处输入图像描述

于 2014-03-16T03:29:13.303 回答