[[412050]]

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

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

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

這可能是你見過對時間復(fù)雜度分析最通透的一篇文章。

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

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

我們在軟件開發(fā)中，時間復(fù)雜度就是用來方便開發(fā)者估算出程序運(yùn)行的答題時間。

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

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

什么是大O

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

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

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

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

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

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

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

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

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

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

時間復(fù)雜度，不同數(shù)據(jù)規(guī)模的差異

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

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

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

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

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

所以我們說的時間復(fù)雜度都是省略常數(shù)項系數(shù)的，是因為一般情況下都是默認(rèn)數(shù)據(jù)規(guī)模足夠的大，基于這樣的事實，給出的算法時間復(fù)雜的的一個排行如下所示：

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

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

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

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

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

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

去掉運(yùn)行時間中的加法常數(shù)項 (因為常數(shù)項并不會因為n的增大而增加計算機(jī)的操作次數(shù))。

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

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

O(n^2 + n) 

只保留保留最高項，去掉數(shù)量級小一級的n (因為n^2 的數(shù)據(jù)規(guī)模遠(yuǎn)大于n)，最終簡化為：

O(n^2) 

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

O(n^2) 

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

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

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

平時說這個算法的時間復(fù)雜度是logn的，那么一定是log 以2為底n的對數(shù)么?

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

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

時間復(fù)雜度1.png

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

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

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

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

舉一個例子

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

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

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

接下來再想一下其他解題思路。

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

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

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

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

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

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

這就是我們通過分析兩種算法的時間復(fù)雜度得來的。

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

總結(jié)

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

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

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

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