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

问题描述

谈起大O表示法，如果一个算法的时间复杂度为O（N）和其他的是O（2N），其中一个是更快？

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

推荐答案

大O的定义是：

O（F（N））= {G |存在N和C> 0，使得G（N）＆LT; C * F（N）的所有N> N}

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的所有功能。

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.

因此​​为O（n）= O（2N）。既不是更快比其他的渐进复杂性方面。他们重新present相同的增长速度 - 即的线性的成长率

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.

证明：

O（n）是O（2N）的一个子集：的假设g是O（n）的函数。然后有N和C> 0，使得G（N）＆LT; C * n表示所有的n> N。所以，G（N）＆LT; （C / 2）×2N对所有的n> N。因此，g是在O（2N）。

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）为O（n）的一个子集：的假设g是O（2n）的功能。然后有N和C> 0，使得G（N）＆LT; C * 2N所有N> N。所以，G（N）＆LT; 2C * N的所有N> N。因此，g是在为O（n）。

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），它们指的是规范的形式。例如：

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

• 对数：O（log n）的
• 线性：O（N）
• linearithmic：为O（n log n）的
• 二次：为O（n ² ）
• 指数：o（C ^N ）对于一些固定的C> 1

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

所以，通常你会写为O（n），而不是O（2N）;为O（n log n）的，而不是O（3 N日志N + 15 N + 5 log n）的。

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屋！