C++代码片段的大O符号和时间复杂性

Question

所以我正在寻找c ++代码片段的时间复杂性的确认:

for(int i = 0; i<N, i++){
    for(int k = 1; k<N; k*=2){
    //code with O(1)
    }
 }

我认为这将是O(NlgN)lg是log base 2的地方.内部循环将是O(lgN)因为k在每次迭代后加倍.外循环显然是O(N),整个代码:

 O(N)*O(lgN) = O(NlgN).

Answer 1

是的，它是 O(n log n) 但基数在大 O 表示法中并不重要，因为f=n \cdot log_2(n) \in \mathcal{O}(log_2(n) * n ) \subseteq \mathcal{O}(\frac{ln(n)}{ln(2)} * n ) \subseteq \mathcal{O}(log(n) * n ) \ni f = n \cdot ln (n)ie

注意最后的 log 仍然应该是 ln，但是人们并不关心 log 以 10 或 e 为底的混乱，因为这在大 O 中并不重要。

因此，当使用大 O 表示法时，evenfor(int k = 2; k<N; k*= k)的复杂度是相同的。然而，有时人们在比较非常小的优化时会写下常数因素，但这是不可行的，除非您正在谈论在世界各地数十亿个实例上运行的快速排序实现。

对于我们如何确定您的内部循环确实受到约束的部分，log(n)我也没有找到很好的数学证明。当然，执行它是一种证明，但我的理论方法是，我们可以同意，当您的函数k *= 2需要更大的参数才能到达时，内部循环就会执行n，那么在哪里，以及我们知道我们需要得到k(x) >= n哪个x我们k(x)想要的 是 的反函数k^(-1)，而 的反函数2^x是log_2(x)。