algorithm - 'log' 在渐近符号中表示什么？

Question

^{我了解渐近符号的原理，例如，当某事物为 O(1) 或 O(n 2} )时，我明白它的含义。但是 O(log n) 是什么意思呢？或 O(n log n) 例如？

Answer 1

日志是“对数”的缩写：http ://en.wikipedia.org/wiki/Logarithm

例如，对数告诉我们需要多少位来表示一个数字，或者当您向其中添加 N 个元素时，平衡树有多少层。

Answer 2

检查：en.wikipedia.org/wiki/Big_O_notation

请记住，log 比指数函数缓慢增加。所以，如果你有一个算法是 n^2 和其他，做同样的事情，有一个对数函数，最后一个会更有效（一般来说，并非总是如此！）。

要评估函数（或算法）的复杂性，您必须主要考虑时间和空间上的执行。您可以使用其他参数评估函数或算法，但最初，这两个都可以。

编辑： http ://en.wikibooks.org/wiki/Data_Structures/Asymptotic_Notation

另外，检查排序算法。将提供有关复杂性的深刻见解。

Answer 3

log 是一个数学函数。它是求幂的倒数 - 2^n 的对数（以 2 为底）是 n。在实践中，对于任何正 c（包括小数 c，例如 1/2（即平方根）），它都比 n^c 好。查看维基百科了解更多信息。