序列复杂度怎么看_《趣学算法》作者又一力作上架,再分享您一篇算法复杂度...
不知道讀者們有沒有看過陳小玉的《趣學(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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: php输出1到10的和,php通过排列组
- 下一篇: php 规则配置,模块Config配置规