big-o - 以下是 O(n^2*log(n)) 或 O(n^3*log(n)) 的大 o

Question

以下 O(n^2*log(n)) 或 O(n^3*log(n)) 是大 o 吗？

for (int i=0;i<n;i++){
 for(int j=0;j<i;j++){
  for(int k=0;k<n;k*=2){
      System.out.print("test");
           }
        }
     }

Answer 1

O(n^2*log(n))

前两个循环与 n 成正比，最后一个是 log n。

当然，它也是 O(n^3*log(n)) 因为 big-O 只是指定了一个上限，如果 O(n^2*log(n)) 是一个上限，那么 O(n^ 3*log(n))

Answer 2

复杂度是O(n ² log ₂ n)或者通常我们可以说O(n ² log n)。