不知道讀者們有沒有看過陳小玉的《趣學(xué)算法》這本書，該書在出版后受到廣大讀者一致好評(píng)，在一年內(nèi)重印了10次，并輸出了繁體版的版權(quán)。不知道讀過這本書的朋友們感覺第一本怎么樣？歡迎留言給我們。接下來(lái)給讀者們推薦一本此作者的新書：《趣學(xué)數(shù)據(jù)結(jié)構(gòu)》，希望你喜歡

趣學(xué)數(shù)據(jù)結(jié)構(gòu)

陳小玉 著

趣學(xué)數(shù)據(jù)結(jié)構(gòu)

• 完美圖解+豐富實(shí)例，復(fù)雜問題簡(jiǎn)單化
• 原理分析+實(shí)戰(zhàn)演練，真正地學(xué)以致用
• 配套代碼+在線答疑，為學(xué)習(xí)保駕護(hù)航

本書基于C++語(yǔ)言編寫，從趣味故事引入算法復(fù)雜性計(jì)算及數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)內(nèi)容，涵蓋線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)，包括鏈表、棧和隊(duì)列、樹和圖的應(yīng)用等。本書內(nèi)容還涉及數(shù)據(jù)結(jié)構(gòu)的基本應(yīng)用(包括各種查找、排序等)和高級(jí)應(yīng)用(包括優(yōu)先隊(duì)列、并查集、B-樹、B+樹和紅黑樹等)。通過大量圖解將抽象數(shù)據(jù)模型簡(jiǎn)單通俗化，語(yǔ)言表述淺顯易懂，并結(jié)合有趣的實(shí)例幫助讀者輕松掌握數(shù)據(jù)結(jié)構(gòu)。

本書特色

本書具有五大特色。

(1)完美圖解，通俗易懂。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)最好的辦法就是畫圖、畫圖、畫圖。本書中的每一個(gè)基本操作和演示都有圖解，有了圖解，一切就都變得簡(jiǎn)單，迎刃而解。

(2)實(shí)例豐富，簡(jiǎn)單有趣。本書結(jié)合大量實(shí)例，講述如何利用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問題，使復(fù)雜難懂的問題變得簡(jiǎn)單有趣，給讀者帶來(lái)巨大的閱讀樂趣，使讀者在閱讀中不知不覺地學(xué)會(huì)數(shù)據(jù)結(jié)構(gòu)知識(shí)，體會(huì)數(shù)據(jù)結(jié)構(gòu)的妙處。

(3)深入淺出，透析本質(zhì)。本書采用簡(jiǎn)潔易懂的代碼描述，抓住本質(zhì)，通俗描述及注釋使代碼更加易懂。本書不僅對(duì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和操作描述全面細(xì)致，而且有復(fù)雜性分析過程。

(4)實(shí)戰(zhàn)演練，循序漸進(jìn)。本書在每一個(gè)數(shù)據(jù)結(jié)構(gòu)講解清楚后，進(jìn)行實(shí)戰(zhàn)演練，使讀者在實(shí)戰(zhàn)中體會(huì)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和操作，增強(qiáng)自信，從而提高了讀者獨(dú)立思考、自己動(dòng)手實(shí)踐的能力。豐富的練習(xí)題和思考題及時(shí)檢驗(yàn)對(duì)所學(xué)知識(shí)的掌握情況，為讀者從小問題出發(fā)，逐步解決大型復(fù)雜性問題奠定基礎(chǔ)。

(5)網(wǎng)絡(luò)資源，技術(shù)支持。本書為讀者提供本書所有范例程序的源代碼、練習(xí)題以及答案解析，這些源代碼可以自由修改編譯，以符合自己的需要。本書提供源代碼執(zhí)行、調(diào)試說明書，提供博客、QQ群技術(shù)支持，為讀者答疑解惑。

本書內(nèi)容

本書包括10章。

· 第1章是基礎(chǔ)知識(shí)，介紹數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)和算法復(fù)雜性的計(jì)算方法。

· 第2～5章是線性結(jié)構(gòu)，講解線性表、棧和隊(duì)列、字符串、數(shù)組等的基本操作和應(yīng)用。

· 第6章是樹形結(jié)構(gòu)，講解樹、二叉樹、線索二叉樹、樹和森林以及樹的經(jīng)典應(yīng)用。

· 第7章是圖形結(jié)構(gòu)，講解圖的存儲(chǔ)、遍歷以及圖的經(jīng)典應(yīng)用。

· 第8～9章是數(shù)據(jù)結(jié)構(gòu)的基本應(yīng)用，講解查找、排序的方法和算法復(fù)雜性比較。

· 第10章是高級(jí)數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用，講解優(yōu)先隊(duì)列、并查集、B-樹、B+樹、紅黑樹等。

本書的每一章中都有大量圖解，并給出數(shù)據(jù)結(jié)構(gòu)的基本操作，最后結(jié)合實(shí)例幫助讀者鞏固相關(guān)知識(shí)點(diǎn)，力求學(xué)以致用、舉一反三。

樣章試讀：

1.2　算法復(fù)雜度

首先看一道某跨國(guó)公司的招聘試題。

寫一個(gè)算法，求下面序列之和：

?1，1，?1，1，…，(?1)n

當(dāng)你看到這個(gè)題目，你會(huì)怎么想？使用for語(yǔ)句或while循環(huán)？

先看算法1-1。

//算法1-1 sum=0;for(i=1;i<=n;i++) sum=sum+pow(-1,n); //即(-1)^n

這段代碼可以實(shí)現(xiàn)求和運(yùn)算，但是為什么不這樣算呢？

再看算法1-2。

//算法1-2if(n%2==0) //判斷n是不是偶數(shù)，%表示求余數(shù) sum=0;else sum=-1;

有的讀者看到算法1-2后恍然大悟，原來(lái)可以這樣啊！這不就是高斯那種將兩個(gè)數(shù)結(jié)合成對(duì)的算法嗎？

一共50對(duì)數(shù)，每對(duì)之和均為101，那么總和為：

(1+100) × 50＝5050

1787年，小高斯10歲，用了幾分鐘的時(shí)間算出了結(jié)果，而其他孩子卻要算很長(zhǎng)時(shí)間。

可以看出，算法1-1需要運(yùn)行n次加法，如果n=10 000，就要運(yùn)行10 000次，而算法1-2只需要運(yùn)行1次！是不是有很大差別？

問：高斯的方法我也知道，但遇到類似的題還是……我用的笨辦法也是算法嗎？答：是算法。

算法是指對(duì)特定問題求解步驟的一種描述。

算法只是對(duì)問題求解方法的一種描述，它不依賴于任何一種語(yǔ)言，可以用自然語(yǔ)言、C、C++、Java、Python等描述，也可以用流程圖、框圖來(lái)表示。為了更清楚地說明算法的本質(zhì)，我們一般去除了計(jì)算機(jī)語(yǔ)言的語(yǔ)法規(guī)則和細(xì)節(jié)，采用“偽代碼”來(lái)描述算法。“偽代碼”介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間，它更符合人們的表達(dá)方式，容易理解，但不是嚴(yán)格的程序設(shè)計(jì)語(yǔ)言，如果要上機(jī)調(diào)試，則需要轉(zhuǎn)換成標(biāo)準(zhǔn)的計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言才能運(yùn)行。

算法具有以下特性。

(1)有窮性：算法是由若干條指令組成的有窮序列，總是在執(zhí)行若干次后結(jié)束，不可能永不停止。

(2)確定性：每條語(yǔ)句有確定的含義，無(wú)歧義。

(3)可行性：算法在當(dāng)前環(huán)境條件下可以通過有限次運(yùn)算實(shí)現(xiàn)。

(4)輸入和輸出：有零個(gè)或多個(gè)輸入，一個(gè)或多個(gè)輸出。

問：嗯，第二種方法的確算得挺快的，但我寫了一個(gè)算法，怎么知道它好不好？

“好”算法的標(biāo)準(zhǔn)如下。

(1)正確性：指算法能夠滿足具體問題的需求，程序運(yùn)行正常，無(wú)語(yǔ)法錯(cuò)誤，并能夠通過典型的軟件測(cè)試，達(dá)到預(yù)期需求規(guī)格。

(2)易讀性：算法遵循標(biāo)識(shí)符命名規(guī)則，簡(jiǎn)潔、易懂，注釋語(yǔ)句恰當(dāng)、適量，方便自己和他人閱讀，并便于后期調(diào)試和修改。

(3)健壯性：算法對(duì)非法數(shù)據(jù)及操作有較好的反應(yīng)和處理。例如，在學(xué)生信息管理系統(tǒng)中，登記學(xué)生年齡時(shí)，21歲誤輸入為210歲，系統(tǒng)應(yīng)該提示出錯(cuò)。

(4)高效性：指算法運(yùn)行效率高，即算法運(yùn)行所消耗的時(shí)間短。算法時(shí)間復(fù)雜度就是算法運(yùn)行需要的時(shí)間。現(xiàn)代計(jì)算機(jī)一秒能計(jì)算數(shù)億次，因此不能用秒來(lái)具體計(jì)算算法消耗的時(shí)間。由于相同配置的計(jì)算機(jī)進(jìn)行一次基本運(yùn)算的時(shí)間是一定的，我們可以用算法基本運(yùn)算的執(zhí)行次數(shù)來(lái)衡量算法的效率。因此將算法基本運(yùn)算的執(zhí)行次數(shù)作為時(shí)間復(fù)雜度的度量標(biāo)準(zhǔn)。

(5)低存儲(chǔ)性：指算法所需要的存儲(chǔ)空間低。尤其是像手機(jī)、平板電腦這樣的嵌入式設(shè)備，算法如果占用空間過大，則無(wú)法運(yùn)行。算法占用的空間大小稱為空間復(fù)雜度。

除了前3條基本標(biāo)準(zhǔn)外，我們對(duì)好的算法的評(píng)判標(biāo)準(zhǔn)就是高效性、低存儲(chǔ)性。

問：前3條都好辦，但時(shí)間復(fù)雜度怎么算呢？

時(shí)間復(fù)雜度：算法運(yùn)行需要的時(shí)間，一般將算法基本運(yùn)算的執(zhí)行次數(shù)作為時(shí)間復(fù)雜度的度量標(biāo)準(zhǔn)。

看算法1-3，并分析這一算法的時(shí)間復(fù)雜度。

//算法1-3sum=0; //運(yùn)行1次total=0; //運(yùn)行1次for(i=1;i<=n;i++) //運(yùn)行n+1次，最后依次判斷條件不成立，結(jié)束{ sum=sum+i; //運(yùn)行n次 for(j=1;j<=n;j++) //運(yùn)行n*(n+1)次 total=total+i*j; //運(yùn)行n*n次}

把算法所有語(yǔ)句的運(yùn)行次數(shù)加起來(lái)，即1+1+n+1+n+n×(n+1)+n×n，可以用一個(gè)函數(shù)T(n)表達(dá)：

看算法1-4，并分析算法的時(shí)間復(fù)雜度。

//算法1-4i=1; //運(yùn)行1次while(i<=n) //可假設(shè)運(yùn)行x次{ i=i*2; //可假設(shè)運(yùn)行x次}

問題規(guī)模：即問題的大小，是指問題輸入量的多少。一般來(lái)講，算法的復(fù)雜度和問題規(guī)模有關(guān)，規(guī)模越大，復(fù)雜度越高。復(fù)雜度一般表示為關(guān)于問題規(guī)模的函數(shù)，如問題規(guī)模為n，時(shí)間復(fù)雜度漸進(jìn)上界表示為О(f (n))。

語(yǔ)句頻度：語(yǔ)句重復(fù)執(zhí)行的次數(shù)。

在算法分析中，漸進(jìn)復(fù)雜度是對(duì)算法運(yùn)行次數(shù)的粗略估計(jì)，大致反映問題規(guī)模增長(zhǎng)趨勢(shì)，而不必精確計(jì)算算法的運(yùn)行時(shí)間。在計(jì)算漸進(jìn)時(shí)間復(fù)雜度時(shí)，可以只考慮對(duì)算法運(yùn)行時(shí)間貢獻(xiàn)大的語(yǔ)句，而忽略那些運(yùn)算次數(shù)少的語(yǔ)句，循環(huán)語(yǔ)句中處在循環(huán)內(nèi)層的語(yǔ)句往往是運(yùn)行次數(shù)最多的，即語(yǔ)句頻度最多的語(yǔ)句，該語(yǔ)句對(duì)運(yùn)行時(shí)間貢獻(xiàn)最大。比如，在算法1-3中，total=total+i*j是對(duì)算法貢獻(xiàn)最大的語(yǔ)句，只計(jì)算該語(yǔ)句的運(yùn)行次數(shù)即可。

注意：不是每個(gè)算法都能直接計(jì)算運(yùn)行次數(shù)。

例如算法1-5，在a[n]數(shù)組中順序查找x，返回其下標(biāo)i，如果沒找到，則返回?1。

//算法1-5 findx(int x) //在a[n]數(shù)組中順序查找x{ for(i=0;i

算法1-5很難計(jì)算該程序到底執(zhí)行了多少次，因?yàn)閳?zhí)行次數(shù)依賴于x在數(shù)組中的位置。如果第一個(gè)元素就是x，則執(zhí)行1次(最好情況)；如果最后一個(gè)元素是x，則執(zhí)行n次(最壞情況)；如果分布概率均等，則平均執(zhí)行次數(shù)為

(平均情況)。

有些算法(如排序、查找、插入等)可以分為最好情況、最壞情況和平均情況分別求算法漸進(jìn)復(fù)雜度，但我們考查一個(gè)算法通常考查其最壞情況，而不是最好情況，最壞情況對(duì)衡量算法的好壞具有實(shí)際的意義。在現(xiàn)實(shí)生活中，我們做什么事情，也會(huì)考慮最壞會(huì)怎樣，最好會(huì)怎樣，但最壞情況對(duì)決策有關(guān)鍵作用。

問：我明白了，那空間復(fù)雜度應(yīng)該就是算法占多大存儲(chǔ)空間了？

空間復(fù)雜度：算法占用的空間大小。一般將算法的輔助空間作為衡量空間復(fù)雜度的標(biāo)準(zhǔn)。

空間復(fù)雜度的本意是指算法在運(yùn)行過程中占用了多少存儲(chǔ)空間，算法占用的存儲(chǔ)空間包括如下。

(1)輸入/輸出數(shù)據(jù)所占空間。

(2)算法本身所占空間。

(3)額外需要的輔助空間。

輸入/輸出數(shù)據(jù)占用的空間是必需的，算法本身占用的空間可以通過精簡(jiǎn)算法來(lái)縮減，但這個(gè)壓縮的量是很小的，可以忽略不計(jì)。而在運(yùn)行時(shí)使用的輔助變量所占用的空間，即輔助空間是衡量空間復(fù)雜度的關(guān)鍵因素。

算法1-6將兩個(gè)數(shù)交換，并分析其空間復(fù)雜度。

//算法1-6 swap(int x,int y) //x與y交換 { int temp; temp=x; // temp為輔助空間 ① x=y; ② y=temp; ③}

兩數(shù)的交換過程如圖1-17所示。

圖1-18中的步驟標(biāo)號(hào)與算法1-6中的語(yǔ)句標(biāo)號(hào)一一對(duì)應(yīng)，該算法使用了一個(gè)輔助空間temp，空間復(fù)雜度為О(1)。

注意：在遞歸算法中，每一次遞推需要一個(gè)棧空間來(lái)保存調(diào)用記錄，因此空間復(fù)雜度需要計(jì)算遞歸棧的輔助空間。

看算法1-7，計(jì)算n的階乘，并分析其空間復(fù)雜度。

//算法1-7 fac(int n) //計(jì)算n的階乘{(lán) if(n<0) //小于零的數(shù)無(wú)階乘值 { printf("n<0,data error!"); return -1; } else if(n==0||n==1) return 1; else return n*fac(n-1); }

階乘是典型的遞歸調(diào)用問題，遞歸包括遞推和回歸。遞推首先將原問題不斷分解成子問題，直到達(dá)到結(jié)束條件，返回最近子問題的解；然后逆向逐一回歸，最終到達(dá)遞推開始的原問題，返回原問題的解。

思考：例如，求5的階乘，程序?qū)⒃鯓佑?jì)算呢？

5的階乘遞推和回歸過程如圖1-18和圖1-19所示。

圖1-18和圖1-19的遞推和回歸過程是我們從邏輯思維上推理，并以圖的方式形象表達(dá)出來(lái)的。計(jì)算機(jī)內(nèi)部是怎樣處理的呢？計(jì)算機(jī)使用一種稱為“棧”的數(shù)據(jù)結(jié)構(gòu)，它類似于一個(gè)放一摞盤子的容器，每次放進(jìn)去一個(gè)，拿出來(lái)的時(shí)候只能從頂端拿一個(gè)，不允許從中間插入或抽取，因此稱為“后進(jìn)先出”(Last In First Out，LIFO)。

5的階乘遞推(進(jìn)棧)過程的形象表達(dá)如圖1-20所示，實(shí)際遞歸中傳遞的是參數(shù)地址。

圖1-20　5的階乘遞推(進(jìn)棧)過程

5的階乘回歸(出棧)過程的形象表達(dá)如圖1-21所示。

圖1-21　5的階乘回歸(出棧)過程

從圖1-20和圖1-21的進(jìn)棧和出棧過程中可以很清晰地看到，首先一步步把子問題壓進(jìn)棧，直到得到返回值，再一步步出棧，最終得到遞歸結(jié)果。在運(yùn)算過程中，使用了n個(gè)棧空間作為輔助空間，因此階乘遞歸算法的空間復(fù)雜度為О(n)。算法1-7中的時(shí)間復(fù)雜度也為О(n)，因?yàn)閚的階乘僅比n?1的階乘多了一次乘法運(yùn)算，fac(n)=n*fac(n?1)，如果用T(n)表示fac(n)的時(shí)間復(fù)雜度，那么：

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的序列复杂度怎么看_《趣学算法》作者又一力作上架，再分享您一篇算法复杂度...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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