O(log n) 和 O(log n +1) 之间的区别

Question

我觉得时间和空间复杂度很混乱（如果有什么通俗易懂的博客/视频感觉 免费链接它）。

那里的 +1 在时间复杂度的情况下会有所不同吗？或者 O(log n) 被认为与 O(log n + 1) 相同？

Answer 1

加法和乘法常数无关紧要。对于所有常数 M≠0 和 A，O(M ⋅ f(n) + A) = O(f(n)).

Answer 2

当你计算大 O 符号时，常量并不重要，因为我们正在计算事物增长的速度，这里有一个常量与大输入完全无关。

假设有两种算法用

O(n)

和

O(n^2)

进行排序，给定

n=50

的输入

现在假设我们确实有一个常数用于

O(n)

的

500

和另一个 5

的 O(n^2) 常数

O(n) = 50 * 500 = 25000

O(n^2) = 50 * 50 * 5 = 12500

对于这种情况，O(n^2) 实际上更快，但是假设我们有 n = 1,000,000 例如

O(n) = 1,000,000 * 500 = 500,000,000 

O(n^2) = 1,000,000 * 1,000,000 * 5 = 5,000,000,000,000 

正如您所见，随着输入越来越大，差距会越来越大，因此常数在大 O 符号计算中并不重要。