计算机算法中用到的对数log

来源于：https://www.cnblogs.com/huaxingtianxia/p/7842862.html

之前一直不解为何算法中经常会看到 log

今天看《数据结构与算法分析 Java 语言描述》（第 3 版）2.4.3 节

求最大子序列和的分治算法实现时才注意到原因

翻看第 29 页的最后一句部分内容如下：

即若 N = 2 ^ k，则 T(N) = N * (k + 1) = N log N + N = O(N log N)

我们根据上面的N = 2 ^ k可得到k = log N

所以代入公式消除变量 k：

N * k + N = N log N + N

此时只剩下一个变量可以十分清晰的展现出公式要表达的相对增长率

故公式推导过程中如果存在类似的条件关系（如N = 2 ^ k）

即可代入公式消除多余的变量以 log （如log N）的形式展现

小提示

log：以 2 为底

lg ： 以 10 为底

ln ： 以 e 为底