O(log n)总是比O(n)更快吗？

Question

如果有两个算法可以计算出相同的结果，但时间复杂度不同，那么O(log n)是始终更快的吗？如果是，请解释一下。顺便说一句，这不是一个作业问题。

- Varkolyn

---

当 n 足够大时，它总是会更快。 - Phonon

O(n)和O(log n)的区别是什么？哪个更好？O(log n)到底是什么意思？希望这可以帮到你。 - user3133925

Answer 1

不是的。如果一个算法在 N/100 的时间内运行，而另一个算法在 (log N)*100 的时间内运行，则对于较小的输入大小，第二个算法将更慢。渐近复杂度关注的是当输入大小趋向无穷时，运行时间的行为。

- a3nm

---

O(n)在极小的输入情况下可能比O(log n)更快吗？ - Varkolyn

1n是O(n)。10000000000000000000000000000000(log n)是O(log n)。在这种情况下，O(n)不仅会在非常小的输入上更快。但当“n”趋近于无穷大时，“最终”O(log n)将更快。 - Alex D

@Varkolyn：不一定非常极端。根据算法，交叉点在n!中可能非常大。 - kkm

Answer 2

不会总是更快。但是，随着问题规模越来越大，最终您将始终达到一个点，其中O(log n)算法比O(n)算法更快。

在现实世界的情况下，O(log n)算法超过O(n)算法的点通常很快就会到来。O(log n)和O(n)之间存在很大的差异，就像O(n)和O(n^2)之间存在很大的差异一样。

如果您有机会阅读Jon Bentley编写的《编程珠玑》, 其中有一章非常棒，他在那里将一个O(n)算法与一个O(n^2)算法进行比较，并尽一切可能给予O(n^2)算法优势。（他在Alpha上使用C编码了O(n^2)算法，在旧的Z80或其他设备上用解释BASIC编写了O(n)算法，运行速度约为1MHz。）令人惊讶的是，O(n)算法多快地超过了O(n^2)算法。

不过，偶尔可能会遇到某些非常复杂的算法，其复杂度略好于较简单的算法。在这种情况下，请不要盲目选择具有更好大O符号的算法--您可能会发现它仅在极大的问题上更快。

- Alex D

Answer 3

对于大小为n的输入，O(n)算法将执行与n成比例的步骤，而O(log(n))算法将执行大约log(n)的步骤。

显然，log(n)比n小，因此复杂度为O(log(n))的算法更好。因为它会快得多。

来自stackoverflow的更多答案

- user3133925