O（N）和O之间的差异（的log（n）） - 这是更好，究竟是为O（log（n））的？(Differ

这是我在数据结构和每次讲座/ TA讲座第一道菜，我们谈论O(log(n)) 这可能是一个愚蠢的问题，但我会很感激，如果有人能向我解释到底是什么意思！？

Answer 1:

这意味着，有问题（通常运行时间）的事情的方式，是与它的输入尺寸的对一致缩放。

大O符号并不意味着精确的公式，而是绑定。例如，以下功能中的输出是所有为O（n）：

f(x) = 3x
g(x) = 0.5x
m(x) = x + 5

因为当增加X，它们的输出都增加而线性-如果有一个6：1之间的比例f(n)和g(n)也将有大约6：1倍的比例之间f(10*n)和g(10*n)等。

至于是否O(n)或O(log n)较好，考虑：如果n = 1000 ，则log n = 3 （日志基-10）。你更愿意有你的算法需要运行1000秒，或3秒？

Answer 2:

对于大小的输入n ，的算法O(n)将执行步骤perportional到n ，而另一算法O(log(n))将执行步骤大致log(n)

清楚log(n)小于n因此复杂的算法O(log(n))效果较好。因为它要快得多。

Answer 3:

对于简答题，O（log n）的比O（n）的更好

现在究竟是O（log n）的？

通常，参照大O符号时， 日志n引用到基部-2对数，（相同的方式，Ln表示以e为底的对数）。这个基-2对数是一个指数函数的反函数。指数函数非常迅速的增长 ，我们可以直观地推断出它的逆会做的正好相反，即生长速度非常缓慢。

例如

X = O（log n）的

我们可以代表n的，

N = ^2×

和

2 ¹⁰ = 1024→LG（1024）= 10

2 ²⁰ = 1048576→LG（1048576）= 20

2 ³⁰ = 1,073,741,824→LG（1073741824）= 30

n的大增量只会导致在日志中一个非常小的增加（N）

对于O（N）的，另一方面复杂性，我们得到了一个线性关系

日志₂ n倍，应采取在N时间不限的因素。

为了进一步巩固这一点，我在对面的例子来解锁托马斯Cormen算法

考虑2台计算机：甲乙

所有的电脑都寻找一个值的阵列的任务假设数组必须通过搜索千万元

计算机A-该计算机每秒能够施1个十亿指令和预期执行使用算法具有O（N）的复杂度以上的任务。我们可以近似的时间花费在这台计算机来完成任务，

N /（指令P个第二）→10 ^7/10 ^ 9 =0.01秒

计算机B-这台计算机是更慢，并且可以执行每秒只有10亿条指令。计算机B有望用O（log n）的复杂度执行使用算法上述任务。我们可以近似的时间花费在这台计算机来完成任务，

的log（n）/（指令P个第二）→日志（10 ^7）/ 10 ⁷ = 0.000002325349

有了这个图，我们可以看到，即使计算机A比B电脑好得多，由于B中的算法，更快完成任务。

我觉得应该是很清楚的，现在为什么O（日志（N））比O速度（N）

Answer 4:

http://en.wikipedia.org/wiki/Big_oh

O（log n）的更好。

Answer 5:

O（logn）时间意味着该算法的最大运行时间正比于输入大小的对数。 O（n）表示，该算法的最大运行时间是正比于输入的大小。

基本上，O（东西）是上界的指令（原子的）算法的数。因此，O（logn）时间比为O（n）更紧，在算法分析方面也比较好。但是，一切都为O（LOGN）的算法也都为O（n），但不是倒退？

Answer 6:

正式的定义：

G（X）= O（F（X））<=>有x0和常数C，对于每x> X0，| G（X）| <= C | F（X）|。

因此，如果你发现了问题P算法的一个，它的复杂度为O（F（N）），你可以说的步骤，你的算法会做的数量，低于或等于渐进到f（n）时，当n通常是输入大小。（n可以是任何东西）

进一步阅读：HTTP：//en.wikipedia.org/wiki/Big_O_notation。

文章来源: Difference between O(n) and O(log(n)) - which is better and what exactly is O(log(n))?