丨復(fù)雜度分析上如何統(tǒng)計(jì)算法的執(zhí)行效率和資源消耗

你可能會(huì)有些疑惑，我把代碼跑一遍，通過統(tǒng)計(jì)、，就能得到算法執(zhí)行的時(shí)間和占用到的數(shù)據(jù)更準(zhǔn)確嗎？籍還給這種方法起了一個(gè)名字，叫事后統(tǒng)計(jì)法。但是，這種統(tǒng)計(jì)方法有非常大的局限性。1.非常依賴測(cè)試環(huán)InCorei9處理器和InCorei3處理器來運(yùn)行，不用說，i9處理器要比i3處理器執(zhí)行的速度快很多。還有，比如原本在這臺(tái)機(jī)器上a代碼執(zhí)行的速度比b代碼要快，等我們2.受數(shù)據(jù)規(guī)模的影響很一樣，排序的執(zhí)行時(shí)間就會(huì)有很大的差別。情況下，如果數(shù)據(jù)已經(jīng)是有序的，那排序法不需要做任何操作，執(zhí)行時(shí)間就會(huì)非常短。除此之外，如果測(cè)試數(shù)據(jù)規(guī)模太小，可能無法反應(yīng)算法的性能。比如，對(duì)于小規(guī)模的數(shù)據(jù)排序，插入排序可能反倒會(huì)比快速排序要快！所以，法。這就是我們今天要講的時(shí)間、空間復(fù)雜度分析方法。大O下，用“肉眼”得到一段代碼的執(zhí)行時(shí)間呢？這里有段非常簡單的代碼，求1,2,3…n的累加和?，F(xiàn)在，我就帶你一塊來估算一下這段代代intcal(intn)intsum=inti=for(;i<=n;++i)sum=sum+ return 從CPU的角度來看，這段代碼的每一行都執(zhí)行著類似的操作：讀數(shù)據(jù)-運(yùn)算-寫數(shù)據(jù)。盡管每行代碼對(duì)應(yīng)的CPU執(zhí)行的個(gè)數(shù)、執(zhí)行的時(shí)間都不一樣，但是，我們這里只是粗略估計(jì)，所以可以假設(shè)每行代碼執(zhí)行的時(shí)間都一樣，為unit_time。在這個(gè)假設(shè)的基礎(chǔ)之上，這段代第2、3行代碼分別需要1個(gè)unit_time的執(zhí)行時(shí)間，第4、5行都運(yùn)行了n遍，所以需要2n*unit_time的執(zhí)行時(shí)間，所以這段代碼總的執(zhí)行時(shí)間就是(2n+2)*unit_time?？梢钥闯鰜恚写a的執(zhí)行時(shí)間T(n)與每行代碼的執(zhí)行次數(shù)成正比。按照這個(gè)分析思路，我們?cè)賮砜催@段代碼代intcal(intn)intsum=inti=intj=for(;i<=n;++i) j= for(;j<=n;++j)sum=sum+i* 我們依舊假設(shè)每個(gè)語句的執(zhí)行時(shí)間是unit_time。那這段代碼的總執(zhí)行時(shí)間T(n)是多少第2、3、4行代碼，每行都需要1個(gè)unit_time的執(zhí)行時(shí)間，第5、6行代碼循環(huán)執(zhí)行了n遍，需要2n*unit_time的執(zhí)行時(shí)間，第7、8行代碼循環(huán)執(zhí)行了n2遍，所以需要*unit_time的執(zhí)行時(shí)間。所以，整段代碼總的執(zhí)行時(shí)間T(n)=(2n2+2n+3)*unit_time盡管我們不知道unit_time的具體值，但是通過這兩段代碼執(zhí)行時(shí)間的推導(dǎo)過程，我們可以得到一個(gè)非常重要的規(guī)律，那就是，所有代碼的執(zhí)行時(shí)間T(n)與每行代碼的執(zhí)行次數(shù)n我們可以把這個(gè)規(guī)律總結(jié)成一個(gè)。注意，大O就要登場(chǎng)了我來具體解釋一下這個(gè)。其中，T(n)我們已經(jīng)講過了，它表示代碼執(zhí)行的時(shí)間；n表示數(shù)據(jù)規(guī)模的大??；f(n)表示每行代碼執(zhí)行的次數(shù)總和。因?yàn)檫@是一個(gè)，所以用f(n)來表示。中的O，表示代碼的執(zhí)行時(shí)間T(n)與f(n)表達(dá)式成正比。所以，第一個(gè)例子中的T(n)=O(2n+2)，第二個(gè)例子中的T(n)=O(2n2+2n+3)。這就是大O時(shí)間復(fù)雜度表示法。大O時(shí)間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時(shí)間，而是（asymptotictimecomplexity），簡稱時(shí)間復(fù)雜度當(dāng)n很大時(shí)，你可以把它想象成10000、100000。而中的低階、常量、系數(shù)三部分不左右增長趨勢(shì)，所以都可以忽略。我們只需要記錄一個(gè)最大量級(jí)就可以了，如果用大O表示法表示剛講的那兩段代碼的時(shí)間復(fù)雜度，就可以記為：T(n)=O(n)；T(n)=O(n)。前面介紹了大O時(shí)間復(fù)雜度的由來和表示方法?，F(xiàn)在我們來看下，如何分析一段代碼的時(shí)只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代我剛才說了，大O這種復(fù)雜度表示方法只是表示一種變化趨勢(shì)。我們通常會(huì)忽略掉中的常量、低階、系數(shù)，只需要記錄一個(gè)最大階的量級(jí)就可以了。所以，我們?cè)诜治鲆粋€(gè)算法、一段代碼的時(shí)間復(fù)雜度的時(shí)候，也只關(guān)注循環(huán)執(zhí)行次數(shù)最多的那一段代碼就可以了段代碼執(zhí)行次數(shù)的n的量級(jí)，就是整段要分析代碼的時(shí)間復(fù)雜度。為了便于你理解，我還拿前面的例子來說明代intcal(intn)intsum=inti=for(;i<=n;++i)sum=sum+ return 其中第2、3行代碼都是常量級(jí)的執(zhí)行時(shí)間，與n的大小無關(guān)，所以對(duì)于復(fù)雜度并沒有影響。循環(huán)執(zhí)行次數(shù)最多的是第4、5行代碼，所以這塊代碼要重點(diǎn)分析。前面我們也講過，這兩行代碼被執(zhí)行了n次，所以總的時(shí)間復(fù)雜度就是O(n)。加法法則：總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜我這里還有一段代碼。你可以先試著分析一下，然后再往下看跟我的分析思路是否一樣代intcal(intn)intsum_1=intp=for(;p<100;++p)sum_1=sum_1+ 7intsum_2=intq=for(;q<n;++q)sum_2=sum_2+ intsum_3=inti=intj=for(;i<=n;++i) j= for(;j<=n;++j) sum_3=sum_3+i*

returnsum_1+sum_2+這個(gè)代碼分為三部分，分別是求sum_1、sum_2、sum_3。我們可以分別分析每一部分的第一段的時(shí)間復(fù)雜度是多少呢？這段代碼循環(huán)執(zhí)行了100次，所以是一個(gè)常量的執(zhí)行時(shí)間，跟n的規(guī)模無關(guān)。這里我要再強(qiáng)調(diào)一下，即便這段代碼循環(huán)10000次、100000次，只要是一個(gè)已知的數(shù)，跟n無關(guān)，照樣也是常量級(jí)的執(zhí)行時(shí)間。當(dāng)n無限大的時(shí)候，就可以忽略。盡管對(duì)代碼的對(duì)增長趨勢(shì)并沒有影響。那第二段代碼和第三段代碼的時(shí)間復(fù)雜度是多少呢？答案是O(n)和O(n2)，你應(yīng)該能容易O(n)。也就是說：總的時(shí)間復(fù)雜度就等于量級(jí)最大的那段代碼的時(shí)間復(fù)雜度。那這個(gè)規(guī)律抽象成就是：如果T1(n)=O(f(n))，T2(n)=O(g(n))；那么T(n)=T1(n)+T2(n)=max(O(f(n)),=O(max(f(n),乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘我剛講了一個(gè)復(fù)雜度分析中的加法法則，這兒還有一個(gè)乘法法則到”是什么樣子的吧？如果T1(n)=O(f(n))，T2(n)=O(g(n))；那么也就是說，假設(shè)T1(n)=O(n)，T2(n)=O(n2)，則T1(n)*T2(n)=O(n3)。到具體的代intcal(intn)intret=inti=for(;i<n;++i)ret=ret+ 8intf(intn)intsum=inti=for(;i<n;++i)sum=sum+ return 我們單獨(dú)看cal()函數(shù)。假設(shè)f()只是一個(gè)普通的操作，那第4～6行的時(shí)間復(fù)雜度就是，T1(n)=O(n)。但f()函數(shù)本身不是一個(gè)簡單的操作，它的時(shí)間復(fù)雜度是T2(n)=O(n)，所以，整個(gè)cal()函數(shù)的時(shí)間復(fù)雜度就是，T(n)=T1(n)*T2(n)=O(n*n)=O(n2)。我剛剛講了三種復(fù)雜度的分析技巧。不過，你并不用刻意去。實(shí)際上，復(fù)雜度分析這東西關(guān)鍵在于“熟練”。你只要多看案例，多分析，就能做到“無招勝有招”。乎涵蓋了你今后可以接觸的所有代碼的復(fù)雜度量級(jí)?；A(chǔ)復(fù)雜度分析的知識(shí)到此就講完了，我們來總結(jié)一下不多，從低階到高階有：O(1)、O(logn)、O(n)、O(nlogn)、O(2)。等你學(xué)完整個(gè)專欄之后，你就會(huì)發(fā)現(xiàn)幾乎所有的數(shù)據(jù)結(jié)構(gòu)和算法的復(fù)雜度都跑不出這幾個(gè)。復(fù)雜度分析并不難，關(guān)鍵在于多練。數(shù)據(jù)結(jié)構(gòu)和算法的時(shí)間、空間復(fù)雜度。只要跟著我的思路學(xué)習(xí)、練習(xí)，你很快就能和我一樣，每次看到代碼的時(shí)候，簡單的一眼就能看出其復(fù)雜度，難的稍微分析一下就能得出答案。是多此一舉呢？而且，每段代碼都分析一下時(shí)間復(fù)雜度、空間復(fù)雜度，是不是很浪費(fèi)時(shí)間呢？你怎么看待這個(gè)問題呢？歡迎留言和我，我會(huì)第一時(shí)間給你反饋 科技所有 上一 02|如何抓住重點(diǎn)，系統(tǒng)高效地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法下一 04|復(fù)雜度分析（下）：淺析最好、、平均、均攤時(shí)間復(fù)雜言精選留言言2018-09-

778展開2018-09-2.展開

2018-09-展開

180呂 2018-09-展開8用二進(jìn)制表示就是3個(gè)bit。16用二進(jìn)制表示就是4個(gè)bitn用二進(jìn)制表 662018-09-展開 2018-09-看不懂別慌，也別忙著總結(jié)，先讀五遍文章先，無他，唯手熟爾起名好 382018-09-個(gè)時(shí)候，為了代碼質(zhì)量考慮分析復(fù)雜度的時(shí)間也并不浪費(fèi)。再有甚者，我們學(xué)習(xí)這個(gè)分展開作者回復(fù):理解的非常透徹非常有邏輯性很贊。ps 2018-09-第二個(gè)例子中，第6.7行為什么是2n平方遍而不是n作者回復(fù):因?yàn)閮蓪友h(huán)一層是n兩層是n*n。不信你自己令n=5有一 332018-09-一直有一個(gè)很糾結(jié)的問題，煩請(qǐng)解答一下：O最愛小黑 2018-09-展開 232018-09-thinkingswhile(i<=n){i=i*2展開作者回復(fù):??分析的通俗易懂馮 2018-09-在分析多項(xiàng)式復(fù)雜度的時(shí)候，有根據(jù)輸入規(guī)模確定復(fù)雜度O(m+n),n是相展開 202018-09-沒有看懂，所以，我們只要知道x值是多少，就知道這行代碼執(zhí)行的次數(shù)了。通過求解x這個(gè)問題我們想高中應(yīng)該就學(xué)過了，我就不多說了。這里的x不就是代碼里的n時(shí)間復(fù)雜度不是O(n