日志基础在 Big O 统治中重要吗？

Do log bases matter in Big O domination?

给出两个函数：

f(n)=O(log₂n) 和 g(n)=O(log₁₀n)

其中一个支配另一个吗？

没有。

碱基之间的差异是一个常数的差异，渐近效率不考虑常数。

在这种情况下，f(n) = O(g(n)) = O(lg(n)) 实际上，f(n) = Θ(g(n)) = Θ(lg(n))

请记住，任何碱基的对数都可以转换为仅随常数变化的公共碱基。

因此它们都有相同的上限

首先，您必须了解函数 f(n) 为 O( g(n) ) 的含义。

正式定义是：*函数 f(n) 被称为 O(g(n)) 当且仅当 |f(n)| <= C * |g(n)|只要 n > k，其中 C 和 k 是常数。*

所以令 f(n) = n 的对数底 a，其中 a > 1 和 g(n) = n 的对数底 b，其中 b > 1

注意：这意味着值 a 和 b 可以是任何大于 1 的值，例如 a=100 和 b = 3

现在我们得到以下内容：对数 n 的基数 a 被称为 O(对数 n 的基数 b) 当且仅当 |对数 n 的基数 | <= C * |log n 的基数 b|每当 n > k

选择k=0，C=对数b的底数a。

现在我们的等式如下所示：|log base a of n| <= 对数 b 的基数 a * |对数 n 的基数 b|每当 n > 0

现在我们的等式如下所示：|log base a of n| <= |log base a of n|每当 n > 0

无论n、b、a取什么值，除了a、b>1和n>0的限制外，方程总是成立的。所以 n 的 log base a 是 O(log base b of n) 并且由于 a,b 无关紧要，我们可以简单地省略它们。