相信每一位錄友都接觸過(guò)時(shí)間復(fù)雜度，但又對(duì)時(shí)間復(fù)雜度的認(rèn)識(shí)處于一種朦朧的狀態(tài)，所以是時(shí)候?qū)r(shí)間復(fù)雜度來(lái)一個(gè)深度的剖析了。

本篇從如下六點(diǎn)進(jìn)行分析：

• 究竟什么是時(shí)間復(fù)雜度
• 什么是大O
• 不同數(shù)據(jù)規(guī)模的差異
• 復(fù)雜表達(dá)式的化簡(jiǎn)
• O(logn)中的log是以什么為底？
• 舉一個(gè)例子

這可能是你見(jiàn)過(guò)對(duì)時(shí)間復(fù)雜度分析最通透的一篇文章。

究竟什么是時(shí)間復(fù)雜度

時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定性描述該算法的運(yùn)行時(shí)間。

我們?cè)谲浖_(kāi)發(fā)中，時(shí)間復(fù)雜度就是用來(lái)方便開(kāi)發(fā)者估算出程序運(yùn)行的答題時(shí)間。

那么該如何估計(jì)程序運(yùn)行時(shí)間呢，通常會(huì)估算算法的操作單元數(shù)量來(lái)代表程序消耗的時(shí)間，這里默認(rèn)CPU的每個(gè)單元運(yùn)行消耗的時(shí)間都是相同的。

假設(shè)算法的問(wèn)題規(guī)模為n，那么操作單元數(shù)量便用函數(shù)f(n)來(lái)表示，隨著數(shù)據(jù)規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，這稱作為算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度，記為 O(f(n))。

什么是大O

這里的大O是指什么呢，說(shuō)到時(shí)間復(fù)雜度，大家都知道O(n)，O(n^2)，卻說(shuō)不清什么是大O。

算法導(dǎo)論給出的解釋：大O用來(lái)表示上界的，當(dāng)用它作為算法的最壞情況運(yùn)行時(shí)間的上界，就是對(duì)任意數(shù)據(jù)輸入的運(yùn)行時(shí)間的上界。

同樣算法導(dǎo)論給出了例子：拿插入排序來(lái)說(shuō)，插入排序的時(shí)間復(fù)雜度我們都說(shuō)是O(n^2) 。

輸入數(shù)據(jù)的形式對(duì)程序運(yùn)算時(shí)間是有很大影響的，在數(shù)據(jù)本來(lái)有序的情況下時(shí)間復(fù)雜度是O(n)，但如果數(shù)據(jù)是逆序的話，插入排序的時(shí)間復(fù)雜度就是O(n^2)，也就對(duì)于所有輸入情況來(lái)說(shuō)，最壞是O(n^2) 的時(shí)間復(fù)雜度，所以稱插入排序的時(shí)間復(fù)雜度為O(n^2)。

同樣的同理再看一下快速排序，都知道快速排序是O(nlogn)，但是當(dāng)數(shù)據(jù)已經(jīng)有序情況下，快速排序的時(shí)間復(fù)雜度是O(n^2) 的，所以嚴(yán)格從大O的定義來(lái)講，快速排序的時(shí)間復(fù)雜度應(yīng)該是O(n^2)。

但是我們依然說(shuō)快速排序是O(nlogn)的時(shí)間復(fù)雜度，這個(gè)就是業(yè)內(nèi)的一個(gè)默認(rèn)規(guī)定，這里說(shuō)的O代表的就是一般情況，而不是嚴(yán)格的上界。如圖所示：

我們主要關(guān)心的還是一般情況下的數(shù)據(jù)形式。

面試中說(shuō)道算法的時(shí)間復(fù)雜度是多少指的都是一般情況。但是如果面試官和我們深入探討一個(gè)算法的實(shí)現(xiàn)以及性能的時(shí)候，就要時(shí)刻想著數(shù)據(jù)用例的不一樣，時(shí)間復(fù)雜度也是不同的，這一點(diǎn)是一定要注意的。

不同數(shù)據(jù)規(guī)模的差異

如下圖中可以看出不同算法的時(shí)間復(fù)雜度在不同數(shù)據(jù)輸入規(guī)模下的差異。

在決定使用哪些算法的時(shí)候，不是時(shí)間復(fù)雜越低的越好（因?yàn)楹?jiǎn)化后的時(shí)間復(fù)雜度忽略了常數(shù)項(xiàng)等等），要考慮數(shù)據(jù)規(guī)模，如果數(shù)據(jù)規(guī)模很小甚至可以用O(n^2)的算法比O(n)的更合適（在有常數(shù)項(xiàng)的時(shí)候）。

就像上圖中 O(5n^2) 和 O(100n) 在n為20之前 很明顯 O(5n^2)是更優(yōu)的，所花費(fèi)的時(shí)間也是最少的。

那為什么在計(jì)算時(shí)間復(fù)雜度的時(shí)候要忽略常數(shù)項(xiàng)系數(shù)呢，也就說(shuō)O(100n) 就是O(n)的時(shí)間復(fù)雜度，O(5n^2) 就是O(n^2)的時(shí)間復(fù)雜度，而且要默認(rèn)O(n) 優(yōu)于O(n^2) 呢 ？

這里就又涉及到大O的定義，因?yàn)榇驩就是數(shù)據(jù)量級(jí)突破一個(gè)點(diǎn)且數(shù)據(jù)量級(jí)非常大的情況下所表現(xiàn)出的時(shí)間復(fù)雜度，這個(gè)數(shù)據(jù)量也就是常數(shù)項(xiàng)系數(shù)已經(jīng)不起決定性作用的數(shù)據(jù)量。

例如上圖中20就是那個(gè)點(diǎn)，n只要大于20 常數(shù)項(xiàng)系數(shù)已經(jīng)不起決定性作用了。

所以我們說(shuō)的時(shí)間復(fù)雜度都是省略常數(shù)項(xiàng)系數(shù)的，是因?yàn)橐话闱闆r下都是默認(rèn)數(shù)據(jù)規(guī)模足夠的大，基于這樣的事實(shí)，給出的算法時(shí)間復(fù)雜的的一個(gè)排行如下所示：

O(1)常數(shù)階 < O(logn)對(duì)數(shù)階 < O(n)線性階 < O(n^2)平方階 < O(n^3)(立方階) < O(2^n) (指數(shù)階)

但是也要注意大常數(shù)，如果這個(gè)常數(shù)非常大，例如10^7 ，10^9 ，那么常數(shù)就是不得不考慮的因素了。

復(fù)雜表達(dá)式的化簡(jiǎn)

有時(shí)候我們?nèi)ビ?jì)算時(shí)間復(fù)雜度的時(shí)候發(fā)現(xiàn)不是一個(gè)簡(jiǎn)單的O(n) 或者O(n^2)， 而是一個(gè)復(fù)雜的表達(dá)式，例如：

O(2*n^2+10*n+1000)

那這里如何描述這個(gè)算法的時(shí)間復(fù)雜度呢，一種方法就是簡(jiǎn)化法。

去掉運(yùn)行時(shí)間中的加法常數(shù)項(xiàng) （因?yàn)槌?shù)項(xiàng)并不會(huì)因?yàn)閚的增大而增加計(jì)算機(jī)的操作次數(shù)）。

O(2*n^2+10*n)

去掉常數(shù)系數(shù)（上文中已經(jīng)詳細(xì)講過(guò)為什么可以去掉常數(shù)項(xiàng)的原因）。

O(n^2+n)

只保留保留最高項(xiàng)，去掉數(shù)量級(jí)小一級(jí)的n （因?yàn)閚^2 的數(shù)據(jù)規(guī)模遠(yuǎn)大于n），最終簡(jiǎn)化為：

O(n^2)

如果這一步理解有困難，那也可以做提取n的操作，變成O(n(n+1)) ，省略加法常數(shù)項(xiàng)后也就別變成了：

O(n^2)

所以最后我們說(shuō)：這個(gè)算法的算法時(shí)間復(fù)雜度是O(n^2) 。

也可以用另一種簡(jiǎn)化的思路，其實(shí)當(dāng)n大于40的時(shí)候， 這個(gè)復(fù)雜度會(huì)恒小于O(3 * n^2)， O(2 * n^2 + 10 * n + 1000) < O(3 * n^2)，所以說(shuō)最后省略掉常數(shù)項(xiàng)系數(shù)最終時(shí)間復(fù)雜度也是O(n^2)。

O(logn)中的log是以什么為底？

平時(shí)說(shuō)這個(gè)算法的時(shí)間復(fù)雜度是logn的，那么一定是log 以2為底n的對(duì)數(shù)么？

其實(shí)不然，也可以是以10為底n的對(duì)數(shù)，也可以是以20為底n的對(duì)數(shù)，但我們統(tǒng)一說(shuō) logn，也就是忽略底數(shù)的描述。

為什么可以這么做呢？如下圖所示：

假如有兩個(gè)算法的時(shí)間復(fù)雜度，分別是log以2為底n的對(duì)數(shù)和log以10為底n的對(duì)數(shù)，那么這里如果還記得高中數(shù)學(xué)的話，應(yīng)該不難理解以2為底n的對(duì)數(shù) = 以2為底10的對(duì)數(shù) * 以10為底n的對(duì)數(shù)。

而以2為底10的對(duì)數(shù)是一個(gè)常數(shù)，在上文已經(jīng)講述了我們計(jì)算時(shí)間復(fù)雜度是忽略常數(shù)項(xiàng)系數(shù)的。

抽象一下就是在時(shí)間復(fù)雜度的計(jì)算過(guò)程中，log以i為底n的對(duì)數(shù)等于log 以j為底n的對(duì)數(shù)，所以忽略了i，直接說(shuō)是logn。

這樣就應(yīng)該不難理解為什么忽略底數(shù)了。

舉一個(gè)例子

通過(guò)這道面試題目，來(lái)分析一下時(shí)間復(fù)雜度。題目描述：找出n個(gè)字符串中相同的兩個(gè)字符串（假設(shè)這里只有兩個(gè)相同的字符串）。

如果是暴力枚舉的話，時(shí)間復(fù)雜度是多少呢，是O(n^2)么？

這里一些同學(xué)會(huì)忽略了字符串比較的時(shí)間消耗，這里并不像int 型數(shù)字做比較那么簡(jiǎn)單，除了n^2 次的遍歷次數(shù)外，字符串比較依然要消耗m次操作（m也就是字母串的長(zhǎng)度），所以時(shí)間復(fù)雜度是O(m * n * n)。

接下來(lái)再想一下其他解題思路。

先排對(duì)n個(gè)字符串按字典序來(lái)排序，排序后n個(gè)字符串就是有序的，意味著兩個(gè)相同的字符串就是挨在一起，然后在遍歷一遍n個(gè)字符串，這樣就找到兩個(gè)相同的字符串了。

那看看這種算法的時(shí)間復(fù)雜度，快速排序時(shí)間復(fù)雜度為O(nlogn)，依然要考慮字符串的長(zhǎng)度是m，那么快速排序每次的比較都要有m次的字符比較的操作，就是O(m * n * logn) 。

之后還要遍歷一遍這n個(gè)字符串找出兩個(gè)相同的字符串，別忘了遍歷的時(shí)候依然要比較字符串，所以總共的時(shí)間復(fù)雜度是 O(m * n * logn + n * m)。

我們對(duì)O(m * n * logn + n * m) 進(jìn)行簡(jiǎn)化操作，把m * n提取出來(lái)變成 O(m * n * (logn + 1))，再省略常數(shù)項(xiàng)最后的時(shí)間復(fù)雜度是 O(m * n * logn)。

最后很明顯O(m * n * logn) 要優(yōu)于O(m * n * n)！

所以先把字符串集合排序再遍歷一遍找到兩個(gè)相同字符串的方法要比直接暴力枚舉的方式更快。

這就是我們通過(guò)分析兩種算法的時(shí)間復(fù)雜度得來(lái)的。

當(dāng)然這不是這道題目的最優(yōu)解，我僅僅是用這道題目來(lái)講解一下時(shí)間復(fù)雜度。

總結(jié)

本篇講解了什么是時(shí)間復(fù)雜度，復(fù)雜度是用來(lái)干什么，以及數(shù)據(jù)規(guī)模對(duì)時(shí)間復(fù)雜度的影響。

還講解了被大多數(shù)同學(xué)忽略的大O的定義以及l(fā)og究竟是以誰(shuí)為底的問(wèn)題。

再分析了如何簡(jiǎn)化復(fù)雜的時(shí)間復(fù)雜度，最后舉一個(gè)具體的例子，把本篇的內(nèi)容串起來(lái)。

相信看完本篇，大家對(duì)時(shí)間復(fù)雜度的認(rèn)識(shí)會(huì)深刻很多！