对数函数

概述

对数函数 是算法分析中最核心的数学函数之一，$\lg n={\log }_{2}n$，许多高效算法的复杂度都包含对数因子。

定义

对数函数（CLRS 约定）

• $\lg n={\log }_{2}n$（以 2 为底，CLRS 默认）
• $\ln n={\log }_{e}n$（自然对数）
• $\log n={\log }_{2}n$（CLRS 中 $\log$ 默认以 2 为底）
• ${\lg }^{k}n=(\lg n{)}^k$（对数的 $k$ 次幂）

核心性质

• 基本运算：$\lg (ab)=\lg a+\lg b$；$\lg (a^b)=b\lg a$；$\lg (a/b)=\lg a-\lg b$
• 换底公式：${\log }_{b}n=\frac{{\log }_{a}n}{{\log }_{a}b}=\Theta ({\log }_{a}n)$，即不同底的对数仅差常数因子。
• 增长极其缓慢：$\lg n$ 是 $O(n^{ϵ})$ 对任意 $ϵ>0$ 成立。
• 迭代对数：${\lg }^{\ast }n$ 是将 $n$ 反复取 $\lg$ 直到结果 $\le 1$ 的次数，增长极慢（如 ${\lg }^{\ast }{2}^{65536}=5$）。
• 对数出现在分治算法（归并排序 $\Theta (n\lg n)$）、二分搜索（$\Theta (\lg n)$）、堆操作（$\Theta (\lg n)$）等核心算法中。

章节扩展

第3章：运行时间刻画

• 3.3 标准记号与常见函数 系统列出对数函数的性质与常见恒等式。

参见

• 调和级数
• 渐近记号
• 大Theta记号