哪种算法更快 O(N) 或 O(2N)? [英] Which algorithm is faster O(N) or O(2N)?

问题描述

说到 Big O 符号，如果一种算法的时间复杂度是 O(N) 而另一种是 O(2N)，哪个更快?

解决方案

大O的定义是:

<块引用>

O(f(n)) = { g |存在 N 和 c >0 使得 g(n) 否 }

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

所以 O(n) = O(2n).两者都不是更快"在渐近复杂性方面比另一个.它们代表相同的增长率——即线性"；增长率.<块引用>

证明:

O(n) 是 O(2n) 的子集: 设 g 是 O(n) 中的函数.然后有 N 和 c >0 使得 g(n) N. 所以 g(n) <(c/2) * 2n 对于所有 n >N.因此 g 在 O(2n) 中.

O(2n) 是 O(n) 的子集: 设 g 是 O(2n) 中的函数.然后有 N 和 c >0 使得 g(n) N. 所以 g(n) <2c * n 对于所有 n >N.因此 g 在 O(n) 中.

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

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

(以下是更完整的列表:常见时间复杂度表)

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

Talking about Big O notations, if one algorithm time complexity is O(N) and other's is O(2N), which one is faster?

解决方案

The definition of big O is:

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

In English, O(f(n)) is the set of all functions that have an eventual growth rate less than or equal to that of f.

So O(n) = O(2n). Neither is "faster" than the other in terms of asymptotic complexity. They represent the same growth rates - namely, the "linear" growth rate.

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

Typically, when people refer to an asymptotic complexity ("big O"), they refer to the canonical forms. For example:

• logarithmic: O(log n)
• linear: O(n)
• linearithmic: O(n log n)
• quadratic: O(n²)
• exponential: O(cⁿ) for some fixed c > 1

(Here's a fuller list: Table of common time complexities)

So usually you would write O(n), not O(2n); O(n log n), not O(3 n log n + 15 n + 5 log n).

这篇关于哪种算法更快 O(N) 或 O(2N)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！