在分析各種算法時(shí)，經(jīng)常看到O(log2n)O(log2?n)或O(nlog2n)O(nlog2?n)這樣的漸進(jìn)復(fù)雜度。不知有沒有同學(xué)困惑過(guò)，為什么算法的漸進(jìn)復(fù)雜度中的對(duì)數(shù)都是以2為底？為什么沒有見過(guò)O(nlog3n)O(nlog3?n)這樣的漸進(jìn)復(fù)雜度？本文解釋這個(gè)問(wèn)題。

三分式歸并排序的時(shí)間復(fù)雜度

先看一個(gè)小例子。

大多數(shù)人應(yīng)該對(duì)歸并排序（merge sort）很熟悉，它的漸進(jìn)復(fù)雜度為O(nlog2n)O(nlog2?n)。那么如果我們將歸并排序改為均分成三份而不是兩份，其算法時(shí)間復(fù)雜度是否有變化呢？

遞歸分析

下面通過(guò)遞歸分析對(duì)三分式歸并排序的時(shí)間復(fù)雜度進(jìn)行分析。因?yàn)椴还苁侨诌€是二分，對(duì)于總共n個(gè)數(shù)據(jù)來(lái)說(shuō)，一遍合并的復(fù)雜度為O(n)O(n)，所以三分式歸并排序的遞歸式為：

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

如果把這個(gè)遞歸式的遞歸樹畫出來(lái)，很容易得到T(n)=O(nlog3n)T(n)=O(nlog3?n)。如下圖所示：

對(duì)數(shù)的陷阱

那么這是否意味著三分式歸并排序在時(shí)間復(fù)雜度上要優(yōu)于二分式的歸并排序呢？因?yàn)橹庇X上nlog3nnlog3?n比nlog2nnlog2?n要優(yōu)一些。

實(shí)際上三分式歸并排序的時(shí)間復(fù)雜度確實(shí)是T(n)=O(nlog3n)T(n)=O(nlog3?n)，而且同時(shí)也是T(n)=O(nlog2n)T(n)=O(nlog2?n)。

這看起來(lái)似乎是矛盾的，nlog3nnlog3?n和nlog2nnlog2?n當(dāng)然在絕大多數(shù)情況下是不相等的，但是在漸進(jìn)復(fù)雜度情況下就不同了，因?yàn)闈u進(jìn)復(fù)雜度是忽略常系數(shù)的，但是似乎也看不出來(lái)nlog3nnlog3?n和nlog2nnlog2?n是差一個(gè)常系數(shù)。關(guān)鍵就在于我們應(yīng)該在中學(xué)學(xué)過(guò)的一個(gè)東西：對(duì)數(shù)換底公式。

logab=logcblogcaloga?b=logc?blogc?a

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

根據(jù)換底公式可以得出：

log3n=log2nlog23log3?n=log2?nlog2?3

所以nlog3nnlog3?n比nlog2nnlog2?n只差一個(gè)常系數(shù)1log231log2?3。因此，從漸進(jìn)時(shí)間復(fù)雜度看，三分式歸并并不比二分式歸并更優(yōu)，當(dāng)然還是有個(gè)常系數(shù)的差別的。

更一般的：

logan=log2nlog2aloga?n=log2?nlog2?a

因此對(duì)于大于1的a來(lái)說(shuō)，都與O(log2n)O(log2?n)差一個(gè)常系數(shù)而已，因此為了簡(jiǎn)便，一般都用O(log2n)O(log2?n)表示對(duì)數(shù)的漸進(jìn)復(fù)雜度，這就解決了本文初始的疑問(wèn)。當(dāng)然，以任何大于1的a為底數(shù)都是沒有問(wèn)題的。

from:?http://blog.codinglabs.org/articles/why-logarithm-base-of-asymptotic-time-complexity-always-two.html

總結(jié)

以上是生活随笔為你收集整理的为什么算法渐进复杂度中对数的底数总为2的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。