c++ - 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 是以 2 为底的对数。内部循环将是 O(lgN)，因为 k 在每次迭代后加倍。外循环显然是O(N)，使得整个代码:

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

Answer 1

是的，它在 O(n log n) 中，但自 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) 以来，基数在大 O 表示法中并不重要即

请注意，最后的对数仍应为 ln，但人们并不关心 log 以 10 或 e 为底的混淆，因为这在大 O 中无关紧要。

所以偶for(int k = 2; k<N; k*= k)使用大 O 表示法时，复杂度相同。然而，有时人们在比较非常小的优化时会写下常数因子，但这是不可行的，除非你在谈论 quick sort implementation that runs on billions of instances around the world.。

关于我们如何确定您的内部循环确实受 log(n) 约束的部分我有点也没有找到一个很好的数学证明。当然执行它是一种证明，但我的理论方法是，我们可以同意内部循环的执行频率与您的函数一样 k *= 2需要更大的论据才能达到 n ，所以在哪里 k(x) >= n ，我们知道哪些 x我们需要得到 k(x) 吗？我们要的是反函数k^(-1) ，以及 2^x 的反函数是log_2(x) .