算法分析的本質(zhì)

算法分析就是對時間復(fù)雜性和空間復(fù)雜性進行分析

時間復(fù)雜度

概念

時間復(fù)雜性又叫時間復(fù)雜度，是對算法運行時間長短的度量。

人們通常只考慮三種情況下的時間復(fù)雜性：最壞、最好、平均情況。

計算方法

第一步：聲明哪些代碼是基本運算

第二步：計算時間復(fù)雜度

第三步：寫成O(n)的形式

注：基本運算就是程序中運行最多的，最壞的情況

空間復(fù)雜度

概念

空間復(fù)雜性是對一個算法在運行過程中所占用存儲空間大小的度量，一般記為S(n)，這里的n是問題規(guī)模，一般不要求計算空間復(fù)雜度，所以復(fù)習(xí)一下概念。

認識遞歸方法

概念

子程序(或函數(shù))直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己，稱為遞歸。直接或間接調(diào)用自身的方法成為遞歸算法。

遞歸的本質(zhì)

函數(shù)在調(diào)用時，首先在棧頂分配他的形式參數(shù)和局部變量存儲空間，然后執(zhí)行函數(shù)；函數(shù)返回時從棧頂釋放他的形式參數(shù)和局部變量存儲空間，而調(diào)用他的那個函數(shù)的形式參數(shù)和局部變量就成為了新的棧頂，任何函數(shù)運行時都只使用棧頂?shù)哪且环荽鎯臻g，如果遞歸深度太大，棧會溢出——棧式存儲管理。

舉一個具體例子：

long long fun(int n)
{
	if (n < 0)
	{
		printf("Illegal number!\n");
		return -1;
	}
	else if (n == 0)
		return 1;
	else
		return n * fun(n - 1);
}

假如傳入n=3，在棧頂分配fun(3)的局部變量存儲空間和他的形式參數(shù)，然后執(zhí)行函數(shù)；由于n>1，所以會返回3*fun(2)；此時fun(2)成為新的棧頂，也分配形參和存儲空間，再次執(zhí)行函數(shù)，返回2*fun(1)；這時fun(1)成為新的棧頂元素，執(zhí)行后返回結(jié)果為1*fun(0)，再次執(zhí)行函數(shù)，返回fun(0)；fun(0)結(jié)果為1，棧頂?shù)膄un(0)分配的空間被釋放，棧頂變?yōu)閒un(1)，結(jié)果為1*1=1；然后被清理，棧頂變?yōu)閒un(2)，結(jié)果為2*fun(1)=2;最后回歸到fun(3)，結(jié)果為3*fun(2)=6；這就是計算機中本質(zhì)上遞歸的過程，是通過調(diào)用堆棧完成遞歸的遞推和回歸過程的。

基本的數(shù)據(jù)結(jié)構(gòu)

線性表

線性表時最簡單、常用的一種數(shù)據(jù)結(jié)構(gòu)，簡言之，一個線性表時n(n>=0)個數(shù)據(jù)元素的有限序列。線性表分為順序表和鏈表兩種，而這最大的區(qū)別就是順序表是順序存儲的，鏈表是隨機存儲。

順序表

把線性表的元素按邏輯次序依次存放在一組地址連續(xù)的存儲單元，用這種方法存儲的線性表簡稱為順序表。

順序表是將表中的結(jié)點依次存放在計算機內(nèi)存中一組地址連續(xù)的存儲單元中。

順序表的存儲特點是：只要確定了起始位置，表中任一元素的地址都通過下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 　1≤i≤n 其中，L是元素占用存儲單元的長度。

由于高級程序設(shè)計語言中的數(shù)組類型也有隨機存取的特性，因此，通常采用數(shù)組來描述順序表。

鏈表

鏈表是線性表的另一種存儲與方式，其特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的），它由一系列結(jié)點（鏈表中的每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。鏈表的主要形式有單鏈表、循環(huán)鏈表、和雙向鏈表。

(1)在線性鏈表中，每個結(jié)點包括兩個部分:一個是存儲數(shù)據(jù)元素信息的數(shù)據(jù)域;另一個是存儲直接后繼存儲位置的指針域，該域表示了元素與其直接后繼元素之間的邏輯關(guān)系，

域中存儲的信息稱做指針或鏈。n個結(jié)點鏈接成一個鏈表，即為線性表的鏈式存儲結(jié)構(gòu)。 由于此鏈表的每個結(jié)點中只包含一個指針域，故稱為線性鏈表或單鏈表。 用鏈表來表示線性表時，數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點中的指針指示的，邏輯上相鄰的兩個元素其存儲的物理位置不要求緊鄰。因此，在使用鏈表時，人們關(guān)心的是它所表示的線性表中數(shù)據(jù)元素的邏輯順序，而不是每個數(shù)據(jù)元素在存儲器中的實際位置。那么如何設(shè)計鏈表的邏輯結(jié)構(gòu)圖呢?

通常把鏈表畫成用箭頭相鏈接的結(jié)點的序列，結(jié)點之間的箭頭表示鏈域中的指針。例如線性表的邏輯結(jié)構(gòu)圖：

其中，H稱為頭指針，它指示鏈表中第一個結(jié)點的存儲位置，整個鏈表的存取必須從頭指針開始進行。由于最后一個元素a3沒有直接后繼，因此他的指針域設(shè)為空（NULL）。

棧與隊列

棧與隊列時另外兩種重要的線性結(jié)構(gòu)，他們可以使用上面所講的順序表或者鏈表的結(jié)構(gòu)來最終實現(xiàn)。

棧

?？煽闯墒且环N“特殊”的線性表，該線性表限定僅在 表尾進行插人和刪除操作。棧主要應(yīng)用于表達式的計算、子程序嵌套調(diào)用遞歸調(diào)用等。

棧具有下述特殊的性質(zhì):

(1)通常稱插入、刪除的這一端為棧頂(Top);另一端稱為棧底( Bottom)。

(2)當(dāng)表中沒有元素時稱為空棧。

(3)棧的修改是按“后進先出”的原則進行，因此棧簡稱為LIFO表(LastInFirstOut)。

每次刪除(退棧)的總是當(dāng)前棧中“最新”的元素，即最后插人 (進棧)的元素，而最先插人的元素是被放在棧的底部，要到最后才能刪除。

隊列

和棧相反，隊列是一種先進先出(First In First Out,FIFO)的線性表，它只允許在表的端進行插人元素 ，而在另端刪除元素。

隊列有下述特殊性質(zhì):

(1)允許刪除的一端稱為隊頭(Front)。

(2)允許插人的端稱為隊尾(Rear)。

(3)當(dāng)隊列中沒有元素時稱為空隊列。

(4)隊列的結(jié)構(gòu)特點是先進隊的元素先出隊。

(5)隊列的修改時依先進先出的原則進行的。新來的成員總是加入隊尾，每次離開的成員總時隊頭元素，而不允許中途離隊。

重要算法概念

貪心法

通過局部最優(yōu)來得到全局最優(yōu)

結(jié)論：

貪心法在面臨選擇時，都做出對眼前來講最有利的選擇，不考慮該選擇對將來是否有影響。

該算法不允許回溯

該算法的好壞在于正確的選擇貪心策略

貪心法具有高效性和不穩(wěn)定性，這個解不一定時最優(yōu)解，但是一定是最優(yōu)解的近似解。

分治法

分治法,字面上的解釋是“分而治之”，就是把個復(fù)雜的問題分成兩個或更多的相同子

問題，再把子問題分成更小的子問題，直到最后各個子問題可以簡單地直接求解,對各個子 問題的解進行合并即得原問題的解。

可見，分治法的基本思想是將一個難以直接解決的大問題，分解成一些規(guī)模較小的相同 問題，以便各個擊破，分而治之。

那么,何時能、何時應(yīng)該采用分治法來解決問題呢?即分治法所能解決的問題應(yīng)該具備 哪些特征?從許多可以用分治法求解的問題中，我們看到這些問題一般具有以下幾個特征:

(1)問題的規(guī)模縮小到一定程度就可以容易地解決。

(2)問題可以分解為若干個規(guī)模較小的相同子問題。（遞歸）

(3)問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。

(4)問題分解出的子問題的解可以合并為原問題的解（分治法的根本依據(jù)）

搜索法

寬度優(yōu)先搜索

給定圖G=(V,E),它的初始狀態(tài)是所有頂點均未被訪問過，在圖G中任選-個頂點u作為源點，則寬度優(yōu)先搜索的思想為:先訪問頂點U,并將其標記為已訪問過:然后從v出發(fā),依次訪問V的鄰接點(孩子節(jié)點)w.w...,w,如果w,(i= .2..t)未訪問過，則標 記w;為已訪問過,將其插人到隊列中;然后再依次從隊列中取出wI ,w.*,w,，訪問它們 的鄰接點。依次類推,直到圖中所有和源點U有路徑相通的頂點均已訪問過為止;若此時 圖G中仍然存在未被訪問過的頂點，則另選一個尚未訪問過的頂點作為新的源點。重復(fù)上 述過程，直到圖中所有頂點均已訪問過為止。

分支限界法

分支限界法是一種在問題的解空間樹中搜索問題解的算法，它常以寬度優(yōu)先或以最小耗費(最大效益)優(yōu)先的方式搜索問題的解空間樹。

分支限界法首先將根結(jié)點加人活結(jié)點表(用于存放活結(jié)點的數(shù)據(jù)結(jié)構(gòu))，接著從活結(jié)點表中取出糧結(jié)點，使其成為當(dāng)前擴展結(jié)點，一次性生成其所有孩子結(jié)點，判斷孩子結(jié)點是含棄還是保留，含棄那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的孩子結(jié)點,其余的被保留在活結(jié)點表中。再從活結(jié)點表中取出一個活結(jié)點作為當(dāng)前擴展結(jié)點,重復(fù)上述擴展過程，一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。由此可見，每一個活結(jié)點最多只有一次機會成為擴展結(jié)點。

可見，分支限界法搜索過程的關(guān)鍵在于判斷孩子結(jié)點是舍棄還是保留。因此,在搜索之 前要設(shè)定孩子結(jié)點是舍棄還是保留的判斷標準，這個判斷標準與回溯法搜索過程中用到的 約束條件和限界條件含義相同?；罱Y(jié)點表的實現(xiàn)通常有兩種方法:一是 先進先出隊列，二 是優(yōu)先級隊列，它們對應(yīng)的分支限界法分別稱為隊列式(FIFO)分支限界法和優(yōu)先隊列式分 隊列式分支限界法按照隊列先進先出(FIFO)的原則選取下一個結(jié)點作為當(dāng)前擴展結(jié) 點。優(yōu)先隊列式分支限界法按照規(guī)定的優(yōu)先級選取隊列中優(yōu)先級最高的結(jié)點作為當(dāng)前擴展 結(jié)點。優(yōu)先隊列一般用二叉堆來實現(xiàn):最大堆實現(xiàn)最大優(yōu)先隊列，體現(xiàn)最大效益優(yōu)先:最 小堆實現(xiàn)最小優(yōu)先隊列，體現(xiàn)最小費用優(yōu)先。

分支限界法的般解題步驟為:

(1)定義問題的解空間。

(2)確定問題的解空間組織結(jié)構(gòu)(樹或圖)。

(3)搜索解空間。搜索前要定義判斷標準(約束函數(shù)或限界雨數(shù))，如果選用優(yōu)先隊列

式分支限界法，則必須確定優(yōu)先級。

總結(jié)

本來想小小總結(jié)一下，但是到最后發(fā)現(xiàn)工作量真的大，肝了大半天，也可能是我太認真了，哈哈，真的希望可以對你們有所幫助，最后求一個小小的三連?。?！

到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)與算法的基礎(chǔ)知識和經(jīng)典算法匯總的文章就介紹到這了,更多相關(guān)C++數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論