algorithm - 这个带乘法的嵌套循环的时间复杂度是多少？

Question

educative.io 认为以下代码的复杂度为 log2(n!) 因为 var n 的每个值都会增加。
但是，我和我的同事认为是因为 var总是 < n它不可能是 log2(n!) 因为它永远不会比 while 循环刚刚跑掉花费更多的时间 n .时间复杂度如果 n用于 while 谓词是 n*log2(n)。

public static void main(String[] args) {
    int n = 10;   

    for (int var = 0; var < n; var++) {   
      int j = 1;  
      while(j < var) { 
        j *= 2;  
      }
    }
}

Answer 1

你们都是对的。首先，为什么它是 O(log n!) 的情况:

如果将每个单独迭代的成本相加，则总运行时间为 O(log 1 + log 2 + ... + log n)。

根据对数乘积法则，log a + log b = log a×b。

因此，O(log 1 + log 2 + ... + log n) = O(log 1×2×...×n) = O(log n!)。

一旦建立，可以证明 O(log n!) = O(n log n) .它们实际上是相同的复杂度类。