educative.io认为下面的代码具有复杂性log2(n！(，因为var随着n的每个值而增加。
然而，我和我的同事认为，因为var总是< n，所以它不可能是log2(n！(，因为它永远不会比while循环刚刚从n运行时花费更多的时间。如果在while谓词中使用n，则时间复杂度为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;
}
}
}
你们都是对的。首先，为什么它是O(logn！(的情况：
-
如果将每个单独迭代的成本相加，则总运行时间为O(log1+log2+…+logn(。
-
根据对数的乘积规则，log a+log b=log a×b。
-
因此，O(log1+log2+…+logn(=O(log1×2×…×n(=0(logn！(。
一旦建立，就可以显示O(logn！(=O(n-logn(。它们实际上是同一个复杂度类。
你应该考虑一下这句话，你们都是对的：
O(n*lg(n))=O(lg(n!))