1. 概述
本文将深入讲解对数时间复杂度（Logarithmic Time Complexity）在算法分析中的应用。
核心目标是理解对数（logarithm）的含义，并掌握其在算法时间复杂度分析中的使用方法。
2. 计算机科学中的对数
2.1. 什么是对数？
对数是指数运算的逆操作。
举个例子：
$$ 2^3 = 8 $$
可以理解为：2 自乘 3 次后得到 8：
$$ 2^3 = 2 * 2 * 2 = 8 $$
反过来，它的逆操作就是对数：
$$ \log_2(8) = 3 $$
可以这样理解：8 被 2 除多少次能得到 1？
$$ \log_2(8) = 3 \Rightarrow (((8 / 2) / 2) / 2) $$
对数可以有不同的底数，比如 base-3 就表示某个数被 3 整除多少次才能到 1。
不过在算法分析中，最常见的是 base-2 的对数，因此本文将主要围绕 base-2 展开讨论。
2.2. 为什么是 base-2？
对数底数选 2 并非随意，而是因为：
✅ 它在算法设计中频繁出现：
- 二分查找、归并排序等算法中，常需要将数组不断二分，这种情况下最多需要 $\log_2(n)$ 次划分
- 位运算中，比如将一个整数转为二进制，需要 $\log_2(n)$ 个 bit
因此当我们说某个算法的时间复杂度为 $O(\log n)$ 时，通常默认是 $O(\log_2 n)$。虽然底数不同，但在大 O 表示法中，所有对数增长趋势是等价的，因此不影响复杂度分析。
3. 时间复杂度回顾
分析算法时间复杂度时，我们要回答的问题是：
随着输入规模 n 增长，算法执行的操作数量如何变化？
我们通常使用 大 O 表示法 来描述和比较不同算法的时间复杂度。
4. O(log n) 时间复杂度详解
4.1. 二分查找示例
我们以 二分查找（Binary Search） 为例，来具体说明对数时间复杂度的应用。
二分查找是一种在有序数组中查找目标值的经典算法。它的核心思想是：
- 每次取中间元素进行比较
- 如果目标值更小，就在左半部分继续查找
- 如果更大，则在右半部分继续查找
- 直到找到目标或确认不存在
来看一个例子：
假设我们有一个有序数组，目标是查找数字 2：
$$ \begin{array}{ccccccccccccc} 2 & 3 & 11 & 13 & 19 & 21 & 34 & 55 & 89 & 111 & 123 & 200\ \end{array} $$
第一步，取中间位置（向下取整）：
$$ \begin{array}{cccccccccccc} 2 & 3 & 11 & 13 & 19 & 21 & 34 & 55 & 89 & 111 & 123 & 200\ & & & & & \uparrow & & & & \ \end{array} $$
目标值 2 小于中间值 21，所以查找左半部分：
$$ \begin{array}{ccccc} 2 & 3 & 11 & 13 & 19\ & & \uparrow & &\ \end{array} $$
继续比较，目标值仍较小，继续缩小区间：
$$ \begin{array}{cc} 2 & 3\ \uparrow\ \end{array} $$
最终找到目标值。
4.2. 复杂度计算分析
我们来分析这个过程的复杂度变化：
每次查找都将问题规模减半，假设原始数组长度为 n：
- 第一次：n
- 第二次：n/2
- 第三次：n/4 ... k. 第 k 次：n / 2^(k-1)
直到 n / 2^(k-1) = 1，解得 k = log₂n
因此，二分查找的时间复杂度为：
✅ $ O(\log n) $
这是对数时间复杂度的典型代表。
5. 总结
通过对二分查找的分析，我们理解了：
- 对数在算法复杂度分析中的意义
- 为什么 base-2 是最常见的对数底数
- 如何推导出 $ O(\log n) $ 的时间复杂度
在实际开发中，遇到需要分治、位操作或频繁缩小问题规模的场景时，对数时间复杂度是非常常见的，值得我们深入理解和掌握。