算法分析的本質(zhì)

算法分析就是對(duì)時(shí)間復(fù)雜性和空間復(fù)雜性進(jìn)行分析

時(shí)間復(fù)雜度

概念

時(shí)間復(fù)雜性又叫時(shí)間復(fù)雜度，是對(duì)算法運(yùn)行時(shí)間長(zhǎng)短的度量。

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

計(jì)算方法

第一步：聲明哪些代碼是基本運(yùn)算

第二步：計(jì)算時(shí)間復(fù)雜度

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

注：基本運(yùn)算就是程序中運(yùn)行最多的，最壞的情況

空間復(fù)雜度

概念

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

認(rèn)識(shí)遞歸方法

概念

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

遞歸的本質(zhì)

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

舉一個(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)的局部變量存儲(chǔ)空間和他的形式參數(shù)，然后執(zhí)行函數(shù)；由于n>1，所以會(huì)返回3*fun(2)；此時(shí)fun(2)成為新的棧頂，也分配形參和存儲(chǔ)空間，再次執(zhí)行函數(shù)，返回2*fun(1)；這時(shí)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；這就是計(jì)算機(jī)中本質(zhì)上遞歸的過(guò)程，是通過(guò)調(diào)用堆棧完成遞歸的遞推和回歸過(guò)程的。

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

線性表

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

順序表

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

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

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

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

鏈表

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

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

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

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

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

棧與隊(duì)列

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

棧

棧可看成是一種“特殊”的線性表，該線性表限定僅在 表尾進(jìn)行插人和刪除操作。棧主要應(yīng)用于表達(dá)式的計(jì)算、子程序嵌套調(diào)用遞歸調(diào)用等。

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

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

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

(3)棧的修改是按“后進(jìn)先出”的原則進(jìn)行，因此棧簡(jiǎn)稱為L(zhǎng)IFO表(LastInFirstOut)。

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

隊(duì)列

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

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

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

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

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

(4)隊(duì)列的結(jié)構(gòu)特點(diǎn)是先進(jìn)隊(duì)的元素先出隊(duì)。

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

重要算法概念

貪心法

通過(guò)局部最優(yōu)來(lái)得到全局最優(yōu)

結(jié)論：

貪心法在面臨選擇時(shí)，都做出對(duì)眼前來(lái)講最有利的選擇，不考慮該選擇對(duì)將來(lái)是否有影響。

該算法不允許回溯

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

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

分治法

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

問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題，直到最后各個(gè)子問(wèn)題可以簡(jiǎn)單地直接求解,對(duì)各個(gè)子 問(wèn)題的解進(jìn)行合并即得原問(wèn)題的解。

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

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

(1)問(wèn)題的規(guī)?？s小到一定程度就可以容易地解決。

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

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

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

搜索法

寬度優(yōu)先搜索

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

分支限界法

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

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

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

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

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

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

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

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

總結(jié)

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

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

最新評(píng)論