算法課程總結

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

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

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

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

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

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