在将算法的复杂度写成对数形式时，例如 Merge Sort 是 O(nlogn)。
对数的底是什么，有关系吗，为什么？
问问题
104 次
2 回答
3
对数的底无关紧要。
下一个等式适用于所有 m,n,k 1：
log_m(n) = log_k(n)/log_k(m)
既然1/log_k(m)是不变的，那么一切log_k(n)都是log_m(n)。这对所有 k,m都是正确的，因此在使用大 O 表示法时，对数的底并不重要，因为O(log_k(n)) = O(log_m(n))
(1) 更多详情：http ://en.wikipedia.org/wiki/Logarithm#Change_of_base
于 2012-09-05T10:31:45.283 回答
2
在 O 和 Omega 表示法中，具有不同常数基数的对数是等价的。这是因为差异是常数，常数被忽略。
看。大 O 符号
于 2012-09-05T09:53:05.737 回答