algorithm - 时间复杂度算法中的对数底

Question

所有时间复杂度算法的对数底数是什么？是以 10 为底还是以 e 为底？

当我们说平均排序复杂度是O(n log n)。 log n 的底数是 10 还是 e？

Answer 1

在计算机科学中，它通常以 2 为基数。这是因为许多表现出这种复杂性的分而治之算法在每一步都将问题一分为二。

二分查找是一个典型的例子。在每一步中，我们将数组一分为二，并且只在其中一半中递归搜索，直到到达一个元素(或零个元素)的子数组的基本情况。将长度为 n 的数组一分为二时，在到达单元素数组之前的总划分次数为 log2(n)。

这通常被简化，因为在讨论算法分析时，不同底数的对数实际上是等价的。