algorithm - O(N) 或 O(2N) 哪个算法更快？

Question

关于大 O 表示法，如果一种算法的时间复杂度为 O(N)，而另一种算法的时间复杂度为 O(2N)，哪个更快？

Answer 1

大O的定义是:

O(f(n)) = { g | there exist N and c > 0 such that g(n) < c * f(n) for all n > N }

在英语中，O(f(n)) 是最终增长率小于或等于 f 的所有函数的集合。

所以 O(n) = O(2n)。就渐近复杂性而言，两者都不比另一个“更快”。它们代表相同的增长率 - 即“线性”增长率。

Proof:

O(n) is a subset of O(2n): Let g be a function in O(n). Then there are N and c > 0 such that g(n) < c * n for all n > N. So g(n) < (c / 2) * 2n for all n > N. Thus g is in O(2n).

O(2n) is a subset of O(n): Let g be a function in O(2n). Then there are N and c > 0 such that g(n) < c * 2n for all n > N. So g(n) < 2c * n for all n > N. Thus g is in O(n).

通常，当人们提到渐近复杂性(“大 O”)时，他们指的是规范形式。例如:

• 对数:O(log n)
• 线性:O(n)
• 线性:O(n log n)
• 二次方:O(n²)
• 指数:O(cⁿ) 对于某些固定的 c > 1

(这是一个更完整的列表:Table of common time complexities)

所以通常你会写 O(n)，而不是 O(2n)； O(n log n)，而不是 O(3 n log n + 15 n + 5 log n)。