O(n)和O(log(n))之间的差异 - 哪个更好,什么是O(log(n))？

Question

这是我在数据结构和每个讲座/ TA讲座的第一门课程,我们谈论O(log(n)).这可能是一个愚蠢的问题,但如果有人能够向我解释它究竟是什么意思,我会很感激!

Answer 1

这意味着有问题的东西(通常是运行时间)以与其输入大小的对数一致的方式缩放.

Big-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 to n,而另一算法O(log(n))将粗略地执行步骤log(n).

显然log(n)小于n复杂算法O(log(n))更好.因为它会快得多.

Answer 3

对于简短的答案，O（log n）优于O（n）

现在O（log n）到底是什么？

通常，当提到大O表示法时，log n表示以2为底的对数（ln表示底e的对数的方式相同）。这个以2为底的对数是指数函数的反函数。指数函数的增长非常快，我们可以直观地推断出它的反函数会做正相反的事情，即增长非常缓慢。

例如

x = O（log n）

我们可以将n表示为，

n = 2 ^x

和

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

2 ²⁰ = 1,048,576→lg（1048576）= 20

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

n的大增量只会导致log（n）的增加很小

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

随时应将因数₂ n取为n的因数。

为了进一步巩固这一点，我在《Thomas Cormen解锁的算法》中遇到了一个例子

考虑两台计算机：A和B

两台计算机都有一个在数组中搜索值的任务。我们假设要搜索的数组中有1000万个元素

计算机A-该计算机每秒可以执行10亿条指令，并有望使用复杂度为O（n）的算法执行上述任务。我们可以估计这台计算机完成任务所需的时间为

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

计算机B-这台计算机慢得多，每秒只能执行1000万条指令。期望计算机B使用复杂度为O（log n）的算法执行上述任务。我们可以估计这台计算机完成任务所需的时间为

log（n）/（指令p秒）→log（10 ⁷）/ 10 ⁷ = 0.000002325349

通过此插图，我们可以看到，尽管计算机A比计算机B更好，但由于计算机B使用的算法，它可以更快地完成任务。

我认为现在应该很清楚为什么O（log（n））比O（n）快得多

Answer 4

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

O(log n) 更好。

Answer 5

O(logn) 表示算法的最大运行时间与输入大小的对数成正比。O(n) 表示算法的最大运行时间与输入大小成正比。

基本上，O(something) 是算法指令数量（原子指令）的上限。因此，O(logn) 比 O(n) 更严格，并且在算法分析方面也更好。但是所有 O(logn) 的算法也是 O(n)，但不是倒退......