algorithm - 这里的复杂性顺序是什么？

Question

   for(int i = n; i > 0; i/=3){
       for(int j = 0; j < i; j++){
           System.out.println("Hello");
       }
   }

是O(n)还是O(nlog n)？

外部循环将运行 log₃ n 次 - 因为迭代器被常数 3 分解。

因此，外循环将被调用 log₃ n 次

属于O(nlog n)？

Answer 1

这部分n + n/3 + n/9 + ..... = n/3 (1 + 1/2 + 1/3 + ....) 不正确.

实际上

n + n/3 + n/9 + ..... = n( 1 + 1/3 + 1/9 +...)

和1 + 1/3 + 1/9 + ... = a / (1-r)其中a = 1 和r = 1/3

收敛于3/2。

因此复杂度为O(n*(3/2))或O(n)

实际上，直观上我会这样想:假设外循环为您提供了您想要解决的问题的输入大小。 所以内部循环就像编写多个不同大小的 for 循环，如下所示:

for ( k = 1 to n )

for ( k = 1 to n/3 )

for ( k = 1 to n/9 )

....

如果您查看这些 for 循环，复杂性似乎会收敛于 O(n)，因为 for 循环的数量取决于 n 并且正在递减/em>，但如果它是像 k 这样的常量，那么它将是 O(n*k)