-4

在将算法的复杂度写成对数形式时，例如 Merge Sort 是 O(nlogn)。

对数的底是什么，有关系吗，为什么？

4

2 回答 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 回答