大 O 表示法和 C++ 代码片段的时间复杂度

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).

- Schooter

---

正确提问的方式非常准确。建议：在内部循环中增加计数器。以N = 100、200、400、800等值运行循环，并绘制结果图。将斜率与N * Log(N)进行比较，以了解它们之间的匹配程度。 - user4581301

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)。

注意，最后的日志仍应为ln，但人们并不关心log是以10为底还是以e为底的混淆，因为在大O表示法中这并不重要。

因此，即使使用大O表示法，for(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)。

- Superlokkus