时间复杂度算法中的对数基

Question

所有时间复杂度算法的对数基数是多少？它是基数10还是基数e？

当我们说平均排序复杂度是O(n log n)时.log n 10或e的基数是多少？

Answer 1

在Big-O复杂性分析中,对数基数实际上并不重要.(它们渐近相同,即它们只有一个常数因子不同):

O(log2 N) = O(log10 N) = O(loge N)

大部分时间,当数学家谈论日志时,他们隐含意味着基础e.计算机科学家倾向于支持基数2,但实际上并不重要.

Answer 2

在计算机科学中,它通常是基础2.这是因为许多表现出这种复杂性的分而治之的算法在每一步都将问题分成两部分.

二进制搜索是一个典型的例子.在每一步中,我们将数组分成两部分,并且仅在一半中递归搜索,直到达到一个元素(或零元素)的子数组的基本情况.将长度数组分为n两个时,到达一个元素数组之前的总分割数是log2(n).

这通常被简化,因为在讨论算法分析时,不同碱基的对数实际上是等价的.

Answer 3

就Big-O而言,基数并不重要,因为基数公式的变化意味着它只是一个恒定的因子差异.

但是,有时计算算法执行的操作数量大约是有用的.在这种情况下,由于大多数分而治之的算法的性质,大多数时候它是基数2.

Answer 4

这个网站有一些解释

基本上，以 10 为底、以 2 为底或以 e 为底的对数可以通过添加常数来交换（转换）为任何其他底数。因此，日志的基础并不重要。

需要注意的关键是 log2N 增长缓慢。将 N 加倍的影响相对较小。对数曲线很好地平坦化。 来源