归纳法证明T(n)=n×log(n)的基例计算结果疑问

嘿，这个问题我太熟了！你之所以算出0.602但证明里结果是2，核心是对数的底数搞混啦，给你拆解清楚：

• 算法分析里的$\log(n)$默认以2为底
  在时间复杂度的归纳证明（比如分治算法的递归式推导）中，$\log(n)$几乎都是指以2为底的对数（记作$\log_2(n)$）。毕竟很多经典分治算法（比如归并排序）都是把问题拆成2个子问题，底数自然是2。
  按这个底数计算的话：$\log_2(2)=1$，所以$2 \times \log_2(2) = 2 \times 1 = 2$，完全符合证明里的结果。

• 你算出0.602的原因
  你应该是用了常用对数（就是计算器默认的以10为底的对数），$\log_{10}(2)≈0.3010$，所以$2×0.3010≈0.602$——这是选错了底数导致的差异。

• 额外小知识
  其实在算法复杂度的渐进分析里，对数的底数不影响最终的复杂度类别（因为不同底数的对数之间只差一个常数倍数），所以有时候会直接省略底数写$\log(n)$。但在归纳法的精确计算中，必须明确底数是2才能得到正确的基例值哦。

内容的提问来源于stack exchange，提问作者Brian W