渐近时间复杂度 O(sqrt(n)log(n)n)

Question

for(int i=1; i*i <= n; i = i+1) {
   for(int j = n; j >= 1; j/4)   {
      for(int k = 1; k <= j; k=k+1) {
         f();
      }
   }
}

为什么这个函数的渐近复杂度是O(n^{3/2})？我想，应该是O(sqrt(n)log(n)n)。这和O(sqrt(n)n)一样吗？然后，它将是 O(n^{3/2})..

Answer 1

外面的两个循环（i 和 j）的边界取决于 n，但内部循环（k）的边界是 j，不是 n.

注意内层循环迭代j次；假设 f() 是 O(1)，内循环的成本是 O(j).

虽然中间的循环（在j之上）迭代了O(log n)次，但是j的实际值是以n开头的geometric series。因为这个几何级数（n + n/4 + n/16 + ...）总和为4/3*n，所以中间循环的成本是O(n).

由于外层循环迭代 sqrt(n) 次，这使得总成本 O(n^(3/2))

Asymptotic time complexity O(sqrt(n)log(n)n)