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

Question

educative.io 认为下面的代码具有复杂度 log₂(n!) 因为 var 随着 n 的每个值增加。

但是，我和我的伙伴认为因为 var 总是 < n 所以它不可能是 log2(n!) 因为它永远不会比 while 花费更多的时间循环运行 n。如果在 while 谓词中使用了 n，则时间复杂度为 n*log₂(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)。他们其实是一样的复杂度class.

Answer 2

你应该考虑这个说法，你们都是对的：

O(n*lg(n))=O(lg(n!))

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

What time complexity is this nested loop with multiplication?

algorithm

big-o