復(fù)雜度是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的第一節(jié)，下面是我對(duì)該知識(shí)內(nèi)容的一些理解。
1.什么是數(shù)據(jù)結(jié)構(gòu)
概念：數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式，指互相之間存在的一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
在實(shí)現(xiàn)一些項(xiàng)目時(shí)，需要在內(nèi)存中將數(shù)據(jù)存儲(chǔ)起來(lái)，存儲(chǔ)需要各種方式，這些方式就被稱作數(shù)據(jù)結(jié)構(gòu)，我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)就是要懂用哪種方式存儲(chǔ)更加合適。
2.什么是算法
概念：定義良好的計(jì)算過程，他取一個(gè)或一組的值為輸入，并產(chǎn)生一個(gè)或一組值為輸出。簡(jiǎn)單來(lái)說算法就是一系列的計(jì)算步驟，用來(lái)將輸入數(shù)據(jù)轉(zhuǎn)化為輸出結(jié)果。就如購(gòu)物，我們經(jīng)常通常會(huì)用到排序，如以價(jià)格排序等等，這里的排序就是一種算法。
那么如何衡量一個(gè)算法的好壞，就要引出我們的學(xué)習(xí)內(nèi)容——算法的時(shí)間復(fù)雜度和空間復(fù)雜度
3.算法的復(fù)雜度
算法在編寫可執(zhí)行程序后，運(yùn)行是需要耗費(fèi)時(shí)間資源和空間資源，因此衡量一個(gè)算法的好壞，一般是從時(shí)間和空間兩個(gè)維度來(lái)衡量，即時(shí)間復(fù)雜度和空間復(fù)雜度。
時(shí)間復(fù)雜度主要衡量一個(gè)算法運(yùn)行的快慢，而空間復(fù)雜度主要衡量一個(gè)算法運(yùn)行所需要的額外空間。經(jīng)過計(jì)算機(jī)行業(yè)的迅速發(fā)展，根據(jù)摩爾定律，計(jì)算機(jī)的存儲(chǔ)容量已經(jīng)達(dá)到很高的程度。（摩爾定律是指IC上可容納的晶體管數(shù)目，約每隔18個(gè)月便會(huì)增加一倍，性能也將提升一倍。）
3.1 時(shí)間復(fù)雜度
概念：在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，他描述了算法的運(yùn)行時(shí)間，但不同性能的計(jì)算機(jī)他的運(yùn)行時(shí)間不能比較，所以有了時(shí)間復(fù)雜度這個(gè)分析方式，一個(gè)算法的所花費(fèi)的時(shí)間與其中語(yǔ)句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。
舉例1：
該例寫成函數(shù)為：F(N)=N^2+2*N+10?
N無(wú)窮大時(shí)，N^2遠(yuǎn)遠(yuǎn)大于其他幾位，實(shí)際中我們計(jì)算時(shí)間復(fù)雜度，不一定要計(jì)算到精確的次數(shù)，只需要大概的執(zhí)行次數(shù)，那么這里我們用大O的漸進(jìn)表示法。
3.2 大O的漸進(jìn)表示法
1.用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
2.在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高項(xiàng)階。
3.如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)，得到的結(jié)果就是大O階。
該例使用大O的漸進(jìn)表示時(shí)間復(fù)雜度為： O(N^2)
在實(shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況
舉例2：
strchr函數(shù)是C語(yǔ)言中的一個(gè)字符串處理函數(shù)，主要用于在一個(gè)字符串中查找指定字符的首次出現(xiàn)位置。如果找到該字符，則返回指向該字符的指針;如果沒有找到，則返回NULL。這個(gè)函數(shù)在很多程序中都非常有用，特別是在需要對(duì)字符串進(jìn)行逐字符處理的情況下。
在該例中，我們就該用最壞運(yùn)行情況
舉例3：冒泡排序
該算法我們光從代碼中很難看出執(zhí)行次數(shù)，因此我們需要通過代碼的思想來(lái)計(jì)算次數(shù)。
在冒泡排序中，第一趟執(zhí)行了N-1次，第二趟執(zhí)行N-2次...，不難看出這是一個(gè)等差數(shù)列
故精確的執(zhí)行次數(shù)為：F(N)=N*(N-1)/2? ? ? O(N)=N^2
舉例4：
假設(shè)要查找X次，我們找一次數(shù)組中的數(shù)字少一半，最壞的情況就是左邊的數(shù)等于右邊的數(shù)，數(shù)組中只有一個(gè)數(shù)，在這種情況下，我們找一次數(shù)組中的元素就要除2，反過來(lái)推就是1*2*2*2*...=N，我們執(zhí)行了多少次就要乘多少個(gè)2，故2^X=N，X=log2N
舉例5：
遞歸算法的次數(shù)=遞歸次數(shù)*每次遞歸調(diào)用的次數(shù)
遞歸了N次，時(shí)間復(fù)雜度為O(N)
舉例6：(通過畫圖分析)
Fib(N)=2^1+2^2+2^3+....+2^(N-1)-X=2^N-1-X
O(N)=2^N
等比數(shù)列求和公式：
4.空間復(fù)雜度
空間復(fù)雜度也是一個(gè)數(shù)學(xué)函數(shù)表達(dá)式，是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)額外占用存儲(chǔ)空間大小的量度。
空間復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒太大意義，所以空間復(fù)雜度計(jì)算的是變量的個(gè)數(shù)。
空間復(fù)雜度計(jì)算規(guī)則基本跟實(shí)踐復(fù)雜度類似，也使大O漸進(jìn)表示法
注意:（遞歸算法）函數(shù)運(yùn)行時(shí)所需要的?？臻g(存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過函數(shù)在運(yùn)行時(shí)候顯式申請(qǐng)的額外空間來(lái)確定。
舉例1：
在進(jìn)行這個(gè)算法時(shí)定義的額外變量，在第一個(gè)i完成循環(huán)后空間會(huì)被銷毀，第二個(gè)i和他用的是同一塊空間，所以循環(huán)只額外使用了兩個(gè)空間，故空間復(fù)雜度為：O(1)
(空間可以重復(fù)利用，不累計(jì))
舉例2：
棧的空間不大，如果是2^N，空間不夠。空間是可以重復(fù)利用不累計(jì)的，時(shí)間是一去不復(fù)返，累積的。豎著先調(diào)用一遍，然后返回時(shí)銷毀，在進(jìn)行第二個(gè)調(diào)用。右邊調(diào)用和左邊的調(diào)用重復(fù)用了同一片空間，故空間復(fù)雜度：O(N)文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-828725.html
每次調(diào)用都要建立棧幀，再算到最后一個(gè)時(shí)返回才會(huì)銷毀額外建立的棧幀，要看遞歸的深度。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-828725.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——復(fù)雜度講解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
