算法課程總結(jié)

1、算法概述算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。An algorithm is a step-by-step procedure for solving a problem in a finite amount of time.算法是假設(shè)干指令的有窮序列，滿足性質(zhì)：(1)輸入：有外部提供的量作為算法的輸入。(2)輸出：算法產(chǎn)生至少一個(gè)量作為輸出。(3)確定性：組成算法的每條指令是清晰，無(wú)歧義的。有限性:算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。 算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。按數(shù)量級(jí)遞增排列，常見(jiàn)的時(shí)間復(fù)雜度有：常數(shù)階。,對(duì)數(shù)階0(log?九)，

2、線性階0(n)3線性對(duì)數(shù)階O(nlog2n),平方階0(nA2),立方階0(nA3),.,k次方階0(Mk),指數(shù)階0(2八n)。隨著問(wèn)題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷 增大，算法的執(zhí)行效率越低。算法與數(shù)據(jù)結(jié)構(gòu)區(qū)別數(shù)據(jù)結(jié)構(gòu)負(fù)責(zé)你的數(shù)據(jù)以什么方式存放算法負(fù)責(zé)你的數(shù)據(jù)以什么方式操作或處理比方你從文本文件或者數(shù)據(jù)庫(kù)中讀取數(shù)據(jù)到本地內(nèi)存中你就會(huì)考慮如何存儲(chǔ)，數(shù)組，單鏈表,雙鏈表或是樹(shù)，然后你可能要對(duì)這些數(shù)據(jù)進(jìn)行一些處理如篩選，排序，合并，這時(shí)候考慮的就是算法了，如何占用空間小且速度快當(dāng)然這兩者相輔相成，互相影響通常數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的好，算法處理上會(huì)簡(jiǎn)單一些反之，數(shù)據(jù)結(jié)構(gòu)很簡(jiǎn)單或是設(shè)計(jì)得不好，處理的時(shí)

3、候算法設(shè)計(jì)上就會(huì)復(fù)雜一些遞歸分治的基本概念特性分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以 便各個(gè)擊破，分而治之。直接或間接地調(diào)用自身的算法稱(chēng)為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱(chēng)為遞歸 函數(shù)。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。 在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類(lèi)型一致而其規(guī)模卻不 斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。全排列問(wèn)題從n個(gè)不同元素中任取m (ml時(shí)，perm(R)S (r1)perm(R1), (r2)perm(R2),， (rn) perm(Rn)構(gòu)

4、成。整數(shù)分解前面的幾個(gè)例子中，問(wèn)題本身都具有比擬明顯的遞歸關(guān)系，因 而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，那么難以找到遞歸關(guān) 系，因此考慮增加一個(gè)自變量：將最大加數(shù)由不大于m的劃分個(gè) 數(shù)記作q(n, m)。可以建立q(n, m)的如下遞歸關(guān)系。n = 1n m 1正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n, n)。鴿巢原理桌上有十個(gè)蘋(píng)果，要把這十個(gè)蘋(píng)果放到九個(gè)抽屜里，無(wú)論怎樣放，我們會(huì)發(fā)現(xiàn)至少會(huì)有一個(gè) 抽屜里面至少放兩個(gè)蘋(píng)果。這一現(xiàn)象就是我們所說(shuō)的“抽屜原理”。抽屜原理有時(shí)也被稱(chēng)為鴿 巢原理。動(dòng)態(tài)規(guī)劃基本概念特性 動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其基本思想也是將待求解問(wèn)題分解成

5、假設(shè)干個(gè)子問(wèn)題由于動(dòng)態(tài)規(guī)劃解決的問(wèn)題多數(shù)有重疊子問(wèn)題這個(gè)特點(diǎn)，為減少重復(fù)計(jì)算，對(duì)每一個(gè)子問(wèn)題 只解一次，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。矩陣連乘問(wèn)題將矩陣連乘積44+1.4簡(jiǎn)記為Ai:j,這里iwj考察計(jì)算Ai:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣 Ak和Ak+1之間將矩陣鏈斷開(kāi)，ikj,那么其相應(yīng)完全 加括號(hào)方式為(44+14X4+14+24)計(jì)算量:Ai:k的計(jì)算量加上Ak+l:j的計(jì)算量,再加上 Ai:k和Ak+l:j相乘的計(jì)算量特征：計(jì)算的最優(yōu)次序所包含的計(jì)算矩 陣子鏈Ai:k和Ak+l:j的次序也是最優(yōu)的。矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn) 題的最優(yōu)解。這種性質(zhì)稱(chēng)

6、為最優(yōu)子結(jié)構(gòu)性質(zhì)。 問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃 算法求解的顯著特征。建立遞歸關(guān)系.設(shè)計(jì)算lijn,所需要的最少數(shù)乘次數(shù) mij,那么原問(wèn)題的最優(yōu)值為ml,n.當(dāng)i=j時(shí),Ai:j=Ai,因此，mizi=O, i = l,2,n.當(dāng)ivj時(shí)，mi,j = mi,k + mk + l,j + ppkPj這里4的維數(shù)為Pi-i x Pt-可以遞歸地定義mi,j為:鹿加+誹+LZI+Pk的位置只有j-i種可能 l 二 J . J89對(duì)于lwiwjwn不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問(wèn)題。 因此，不同子問(wèn)題的個(gè)數(shù)最多只有3 + 77 = 0(77)由此可見(jiàn)，在遞歸計(jì)算時(shí)，許多子問(wèn)題被重復(fù)計(jì)算多 次。這也是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著 特征。用動(dòng)態(tài)規(guī)劃算法解此