究竟什么是時(shí)間復(fù)雜度
時(shí)間復(fù)雜度就是用來(lái)方便開(kāi)發(fā)者估算出程序的運(yùn)行時(shí)間
我們?cè)撊绾喂烙?jì)程序運(yùn)行時(shí)間呢，我們通常會(huì)估計(jì)算法的操作單元數(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
這里就要說(shuō)一下這個(gè)大O，什么是大O呢，很多同學(xué)說(shuō)時(shí)間復(fù)雜度的時(shí)候都知道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ù)本來(lái)有序的情況下時(shí)間復(fù)雜度是O(n)，也就對(duì)于所有輸入情況來(lái)說(shuō)，最壞是O(n^2) 的時(shí)間復(fù)雜度，所以稱插入排序的時(shí)間復(fù)雜度為O(n^2)
同樣的同理我們?cè)诳匆幌驴焖倥判颍贾揽焖倥判蚴荗(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)格的上界
所以這里大家知道這么一回事就好了
面試中面試官絕對(duì)不會(huì)針對(duì)快速排序的時(shí)間復(fù)雜度問(wèn)題來(lái)討論O的定義， 大家知道討論的時(shí)間復(fù)雜度就是指一般情況下的時(shí)間復(fù)雜度就好了。
大家要對(duì)算法的時(shí)間復(fù)雜度有這樣的一個(gè)概念
就是同一個(gè)算法的時(shí)間復(fù)雜度不是一成不變的，和輸入的數(shù)據(jù)形式依然有關(guān)系
我們主要關(guān)心的還是一般情況下的數(shù)據(jù)形式。
面試中說(shuō)道算法的時(shí)間復(fù)雜度是多少指的都是一般情況
但是如果面試官和我們深入探討一個(gè)算法的實(shí)現(xiàn)以及性能的時(shí)候 我們就要時(shí)刻想著 數(shù)據(jù)用例的不一樣 時(shí)間復(fù)雜度也是不同的，這一點(diǎn)同學(xué)們要注意
如何描述時(shí)間復(fù)雜度
這個(gè)圖中我們可以看出 不同算法的時(shí)間復(fù)雜度 在不同數(shù)據(jù)輸入規(guī)模下的差異。
我們?cè)跊Q定使用那些算法的時(shí)候 ，不是時(shí)間復(fù)雜越低的越好，要考慮數(shù)據(jù)規(guī)模，如果數(shù)據(jù)規(guī)模很小 甚至可以用O(n^2)的算法比 O(n)的更合適
就像上圖中圖中 O(5n^2) 和 O(100n) 在n為20之前 很明顯 O(5n^2)是更優(yōu)的，所花費(fèi)的時(shí)間也是最少的。
那我們?yōu)槭裁丛谟?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)?strong>大O其實(shí)就是數(shù)據(jù)量級(jí)突破一個(gè)點(diǎn)且數(shù)據(jù)量級(jí)非常大的情況下所表現(xiàn)出的時(shí)間復(fù)雜度，這個(gè)點(diǎn)也就是 常數(shù)項(xiàng)系數(shù)已經(jīng)不起決定性作用的點(diǎn)。
例如上圖中 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ù)階)
你所不知道的O(logn)
我們平時(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ù)的
抽象一下 log 以i為底n的對(duì)數(shù) 等于 log 以j為底n的對(duì)數(shù)，所以我們忽略了i，直接說(shuō)是logn，正式因?yàn)閘ogij 是就一個(gè)常數(shù)
所以，這樣就應(yīng)該不難理解了 我們?yōu)槭裁春雎缘讛?shù)了
如果時(shí)間復(fù)雜度是一個(gè)復(fù)雜的表達(dá)式，我們?nèi)绾魏?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)
如果這一步同學(xué)們理解有困難，那也可以做提取n的操作，變成O(n(n+1)) ，省略加法常數(shù)項(xiàng)后 也別變成了
O(n^2)
所以最后我們說(shuō)：我們這個(gè)算法的算法時(shí)間復(fù)雜度是 O(n^2)
也可以用另一種簡(jiǎn)化的思路，當(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)
舉例說(shuō)明時(shí)間復(fù)雜度要怎么算
我們通過(guò)一道題目，來(lái)看一下具體時(shí)間復(fù)雜度應(yīng)該怎么算
題目描述：找出n個(gè)字符串中相同的兩個(gè)字符串（假設(shè)這里只有兩個(gè)相同的字符串）
一些同學(xué)可能以為解決這道題目可以采用枚舉遍歷的解法，時(shí)間復(fù)雜度是O(n^2)
這個(gè)時(shí)間復(fù)雜度其實(shí)是不對(duì)的。
這里一些同學(xué)忽略了字符串比較的時(shí)間消耗，這里并不像int 型數(shù)字做比較那么簡(jiǎn)單
除了n^2 次的遍歷次數(shù)外， 字符串比較依然要消耗m次操作（m也就是字母串的長(zhǎng)度），所以時(shí)間復(fù)雜度是O(m*n*n)
那么我們?cè)傧胍幌缕渌忸}思路
我們先排對(duì)n個(gè)字符串按字典序來(lái)排序，排序后n個(gè)字符串就是有序的，意味著兩個(gè)相同的字符串就是挨在一起
然后在遍歷一遍n個(gè)字符串，這樣就找到兩個(gè)相同的字符串了
那我們來(lái)看看這種算法的時(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)， 那我們比較一下時(shí)間效率O(m*n*logn) 是不是比第一種方法O(m*n*n)更快一些呢
很明顯O(m*n*logn) 要優(yōu)于O(m*n*n)
所以 先把字符串集合排序在遍歷一遍找到兩個(gè)相同字符串的方式要比直接暴力枚舉的方式更快。
通過(guò)這個(gè)例子 希望大家對(duì)時(shí)間復(fù)雜的是怎么算的有一個(gè)初步的理解和認(rèn)識(shí)。
歡迎大家關(guān)注我的微信公眾號(hào)：「代碼隨想錄」，一線互聯(lián)網(wǎng)技術(shù)從業(yè)者，分享自己對(duì)互聯(lián)網(wǎng)以及技術(shù)的想法與思考。關(guān)注后回復(fù)： 「java」「C++」「python」「算法與數(shù)據(jù)結(jié)構(gòu)」 等等關(guān)鍵字就可以獲得我多年整理出來(lái)的學(xué)習(xí)資料。求職內(nèi)推也可以來(lái)找我，首推百度。騰訊、阿里、頭條等也可以幫忙聯(lián)系
