这是我在数据结构和每个讲座/ TA讲座的第一门课程，我们谈论O(log(n))。这可能是一个愚蠢的问题，但如果有人能够向我解释它究竟是什么意思，我会很感激！
这意味着有问题的东西（通常是运行时间）以与其输入大小的对数一致的方式缩放。
Big-O notation并不意味着一个确切的等式，而是一个界限。例如，以下函数的输出都是O（n）：
f(x) = 3x
g(x) = 0.5x
m(x) = x + 5
因为当你增加x时，它们的输出都会线性增加 - 如果f(n)和g(n)之间的比例为6：1，那么f(10*n)和g(10*n)之间的比率也会大约为6：1，依此类推。
至于O(n)或O(log n)是否更好，请考虑：如果n = 1000，那么log n = 3（对于log-base-10）。你宁愿让你的算法运行：1000秒，还是3秒？
对于n大小的输入，O(n)的算法将执行对n的步骤，而另一个O(log(n))算法将执行大致log(n)的步骤。
显然log(n)比n小，因此复杂性O(log(n))算法更好。因为它会快得多。
简而言之，O（log n）优于O（n）
那么究竟是什么O（log n）？
通常，当引用大O表示法时，log n指的是base-2对数，（同样地，ln表示基数e对数）。这个基数为2的对数是指数函数的倒数。指数函数的增长非常迅速，我们可以直观地推断它的反向将完全相反，即增长非常缓慢。
例如
x = O（log n）
我们可以代表n，
n = 2x
和
210 = 1024→lg（1024）= 10
220 = 1,048,576→lg（1048576）= 20
230 = 1,073,741,824→lg（1073741824）= 30
n中的大增量仅导致log（n）的非常小的增加
另一方面，对于O（n）的复杂性，我们得到线性关系
log2n的因子应该随时取n因子。
为了进一步巩固这一点，我在Algorithms Unlocked By Thomas Cormen遇到了一个例子
考虑2台计算机：A和B.
两台计算机都有一个搜索数组值的任务让我们假设这些数组有1000万个要搜索的元素
计算机A-该计算机每秒可执行10亿条指令，并期望使用复杂度为O（n）的算法执行上述任务。我们可以估算出这台计算机完成任务的时间
n /（指令p秒）→107/10 ^ 9 = 0.01秒
计算机B-这台计算机速度慢得多，每秒只能执行1000万条指令。期望计算机B使用复杂度为O（log n）的算法执行上述任务。我们可以估算出这台计算机完成任务的时间
log（n）/（指令p秒）→log（107）/ 107 = 0.000002325349
通过这个例子，我们可以看到，即使计算机A比计算机B好得多，由于B使用的算法，它可以更快地完成任务。
我认为现在应该很清楚为什么O（log（n））比O（n）快得多
http://en.wikipedia.org/wiki/Big_oh
O（log n）更好。
O（logn）表示算法的最大运行时间与输入大小的对数成正比。 O（n）表示算法的最大运行时间与输入大小成正比。
基本上，O（某事物）是算法指令数量（原子数量）的上限。因此，O（logn）比O（n）更紧密，并且在算法分析方面也更好。但是所有O（logn）的算法也是O（n），但不是向后...
正式定义：
g（x）= O（f（x））<=>有x0和常数C，每x> x0，| g（x）| <= C | f（x）|。
因此，如果你发现问题P的算法A的复杂度为O（f（n）），你可以说算法将执行的步数渐近或等于f（n），当n通常是输入大小。 （可以是任何东西）
如需进一步阅读：http：//en.wikipedia.org/wiki/Big_O_notation。