在分析各种算法时，经常看到O(log2n)或O(nlog2n)这样的渐进复杂度。不知有没有同学困惑过，为什么算法的渐进复杂度中的对数都是以2为底？为什么没有见过O(nlog3n)这样的渐进复杂度？本文解释这个问题。

三分式归并排序的时间复杂度

先看一个小例子。

大多数人应该对归并排序(merge sort)很熟悉，它的渐进复杂度为O(nlog2n)。那么如果我们将归并排序改为均分成三份而不是两份，其算法时间复杂度是否有变化呢？

递归分析

下面通过递归分析对三分式归并排序的时间复杂度进行分析。因为不管是三分还是二分，对于总共n个数据来说，一遍合并的复杂度为O(n)，所以三分式归并排序的递归式为：

T(n)=3T(n/3)+O(n)

如果把这个递归式的递归树画出来，很容易得到T(n)=O(nlog3n)。如下图所示：

对数的陷阱

那么这是否意味着三分式归并排序在时间复杂度上要优于二分式的归并排序呢？因为直觉上nlog3n比nlog2n要优一些。

实际上三分式归并排序的时间复杂度确实是T(n)=O(nlog3n)，而且同时也是T(n)=O(nlog2n)。

这看起来似乎是矛盾的，nlog3n和nlog2n当然在绝大多数情况下是不相等的，但是在渐进复杂度情况下就不同了，因为渐进复杂度是忽略常系数的，但是似乎也看不出来nlog3n和nlog2n是差一个常系数。关键就在于我们应该在中学学过的一个东西：对数换底公式。

logab=logcblogca

其中a和c均大于0且不等于1。

更多内容详见原文：http://blog.codinglabs.org/articles/why-logarithm-base-of-asymptotic-time-complexity-always-two.html