为什么算法渐进复杂度中对数的底数总为2
在分析算法时，我们常看到 O(log₂n) 或 O(n log₂n) 这样的复杂度表达，但很少有人深究：为什么对数的底总是 2？为什么不出现以 3 为底的情况？这篇文章从这个看似理所当然的细节出发，揭示了算法复杂度表示中一个容易被忽略的知识点。 作者以大家熟悉的归并排序为例，引出了“三分式归并排序”这个变体——即每次将数组三等分而非二等分进行递归。通过分析它的实际时间复杂度，文章直观地展示了一个关键事实：不同底数的对数之间只相差一个常数因子。在渐进复杂度的大 O 表示法中，这个常数会被忽略，因此 O(log₂n) 与 O(log₃n) 本质上是等价的。 既然如此，为何惯例上总是书写底数 2？文章指出，这主要源于直觉和历史习惯。因为二分法（每次问题规模减半）是计算机科学中最常见、最基础的分解方式，它直接对应了二叉树的结构和许多经典算法（如二分搜索）的核心思想。使用底数 2 能让人立刻联想到“将问题规模反复减半”的过程，这使得算法的逻辑与复杂度表达在直觉上形成了统一。 因此，底数的选择并非数学上的严格要求，而是一种服务于理解与沟通的工程约定。这篇文章的价值在于，它帮读者厘清了这一约定背后的原理，让我们在写下 O(log n) 时，能更清晰地理解其背后的计算图景。