algorithm - 代码段的时间复杂度

Question

我正在尝试计算以下代码片段的时间复杂度

sum = 0;
for(i = 0; i <= n; i++) {
  for(j = 1; j <= i; j++) {
    if(i % j == 0) {
      for(k = 0; k <= n; k++) {
        sum = sum + k;          
      }        
    }
  }
}

我认为，在 First 循环的 N 次迭代中，只有 1 个值为 0 的值允许进入 K 循环，并且从 i = 1.....N 开始，K 循环永远不会运行。

因此，只有 I 的 1 个值运行 j 循环 N 次和 k 循环 N 次，对于 I 的其他值，只有 J 循环运行 N 次

那么，TC = O(N^2) 吗？

Answer 1

这里令d(n)是n的约数。

我看到您的程序正在为 O( d(n) ) 个除数执行 O(n) 工作(最内层循环)(我从 0 开始循环到最外层循环中的 n:O(n) )。

它的复杂度是O( n * d(n) * n )。

Reference

对于大 n，d() ~ O( exp( log(n)/log(log n) ) )。

所以整体复杂度是O( n^(2 + 1/log(log n) ) )。