2023年算法設(shè)計(jì)與分析期末備考知識點(diǎn)總結(jié)

通俗地講,算法是解決問題的方法，嚴(yán)格地說,算法是對特定問題求解環(huán)節(jié)的一種描述，是指令的有限序列。算法還必須滿足一下五個重要特性:輸入、輸出、有窮性、擬定性、可行性。程序（Ｐｒogrａｍ)是對一個算法使用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)，原則上，算法可以用任何一種程序設(shè)計(jì)語言來實(shí)現(xiàn)。什么是算法的計(jì)算復(fù)雜性？算法分析指的是對算法所需要的兩種計(jì)算機(jī)資源——時間和空間(時間復(fù)雜性和空間復(fù)雜性進(jìn)行估算，所需要的資源越多,該算法的復(fù)雜性就越高。表達(dá)計(jì)算復(fù)雜性的O你掌握了?若存在兩個正的常數(shù)c和n0,對于任意n≥n0,都有T(ｎ)≤c×ｆ(n)，則稱Ｔ(ｎ）=Ｏ(ｆ（n））(或稱算法在O（f(n)）中)。我們重要介紹了哪幾種算法設(shè)計(jì)方法?分治法:將一個難以直接解決的大問題，分割成一些規(guī)模較小的子問題，以便各個擊破,分而治之。減治法：減治法在將原問題分解為若干個子問題后,運(yùn)用了規(guī)模為n的原問題的解與較小規(guī)模（通常是ｎ／2)的子問題的解之間的關(guān)系,這種關(guān)系通常表現(xiàn)為:(1)原問題的解只存在于其中一個較小規(guī)模的子問題中;(2)原問題的解與其中一個較小規(guī)模的解之間存在某種相應(yīng)關(guān)系。由于原問題的解與較小規(guī)模的子問題的解之間存在這種關(guān)系，所以,只需求解其中一個較小規(guī)模的子問題就可以得到原問題的解。動態(tài)規(guī)劃法、貪心算法、回溯算法、概率RAM程序分治法-－----合并排序設(shè)算法4.３對ｎ個元素排序的時間復(fù)雜性為T(n)，則該二路歸并排序算法存在如下遞推式:二路歸并排序的時間代價是O(nｌog2ｎ)。所需空間只要O(m+ｎ＋min(m,n）)的空間就夠了(假設(shè)兩個合并串的長度分別為ｍ和n)。分治法--－---快速排序在最佳情況下在具有n個記錄的序列中,一次劃分需要對整個待劃分序列掃描一遍,則所需時間為O（n)。時間復(fù)雜度為O(nlｏg２n）。在最壞情況下必須通過n-1次遞歸調(diào)用才干把所有記錄定位,并且第i趟劃分需要通過n-i次關(guān)鍵碼的比較才干找到第i個記錄的基準(zhǔn)位置,因此，總的比較次數(shù)為：時間復(fù)雜度為O(n2)分治法-----－最大子段遞推式:算法時間復(fù)雜度:O(nｌｏg2n)分治法--－－-－棋盤覆蓋問題Ｔ(ｋ)滿足如下遞推式:分治法------循環(huán)賽日安排問題基本語句的執(zhí)行次數(shù)是:算法的其時間復(fù)雜性為Ｏ（４k）。順序記錄問題:算法1找出n個元素中的第ｋ個最小元素輸入:從一個有線性序的集合中抽出的ｎ個元素的序列Ｓ及一個整數(shù)k，1≤k≤ｎ。輸出:S中的第k個最小元素算法2算法2的盼望時間是O(n)。最壞情況O（n2）減治--－--插入排序(手工題）堆的概念:ｎ個元素的序列{K1,Ｋ2,…．．Kn｝,當(dāng)且僅當(dāng)滿足動態(tài)規(guī)劃求解TSP問題注：用動態(tài)規(guī)劃解決TSP問題，算法的時間復(fù)雜性為Ｏ（ｎ22n)。和蠻力法相比，動態(tài)規(guī)劃法求解TＳＰ問題，把本來的時間復(fù)雜性是Ｏ(n!)的排列問題，轉(zhuǎn)化為組合問題,從而減少了算法的時間復(fù)雜性,但它仍需要指數(shù)時間。但遺憾的是這一動態(tài)規(guī)劃算法需要Ｏ（n２n)的空間。當(dāng)n較大時,空間難以滿足。多段圖的最短途徑算法：1.Foｒ(i=1;i<=n；i+＋）COST[i]=0;初始化：數(shù)組ｃｏsｔ[ｎ]初始化為最大值，數(shù)組pａt(yī)ｈ[n］初始化為-1；2．foｒ(i＝n-２;i＞=0；i--)2.１對頂點(diǎn)i的每一個鄰接點(diǎn)ｊ，根據(jù)cｏｓt[i］=ｍｉn{cij＋coｓｔ[ｊ］｝（i≤ｊ≤n且頂點(diǎn)j是頂點(diǎn)i的鄰接點(diǎn))計(jì)算ｃost[i]；2．２根據(jù)ｐath[i］=使cｉj＋coｓt[ｊ]最小的ｊ計(jì)算path[i];3.輸出最短途徑長度ｃost[0];４.輸出最短途徑通過的頂點(diǎn)：4.1i=04.2循環(huán)直到ｐａt(yī)h[i]=n－14.2.1輸出ｐaｔｈ[i];4．2.2i＝paｔｈ［i]；最優(yōu)二叉查找樹算法:最優(yōu)二叉查找樹是以這n個記錄構(gòu)成的二叉查找樹中具有最少平均比較次數(shù)的二叉查找樹,即最小,i=1n回溯法－-－-解空間樹的動態(tài)搜索過程注:搜索過程中,采用兩種策略避免無效搜索:用約束條件剪去得不到可行解的子樹;用目的函數(shù)剪去得不到最優(yōu)解的子樹。例一:對于n=3的0/1背包問題，三個物品的重量為{２0，15,10｝，價值為{20,30,25｝，背包容量為25,從圖８．2所示的解空間樹的根結(jié)點(diǎn)開始搜索，搜索過程如下:(注:樹枝左側(cè)為1,右側(cè)為0,1代表裝包，０代表不裝包,從上到下每一層代表一個物體)例二:對于n＝4的ＴＳP問題,解空間樹如下:代價矩陣Ｃ如下：目的函數(shù)初始化為∞；從結(jié)點(diǎn)１選擇第1棵子樹到結(jié)點(diǎn)2，表達(dá)在圖中從頂點(diǎn)1出發(fā)；從結(jié)點(diǎn)2選擇第1棵子樹到達(dá)結(jié)點(diǎn)３，表達(dá)在圖中從頂點(diǎn)1到頂點(diǎn)２，依代價矩陣可知途徑長度為3；從結(jié)點(diǎn)3選擇第１棵子樹到達(dá)結(jié)點(diǎn)4,表達(dá)在圖中從頂點(diǎn)2到頂點(diǎn)3，依代價矩陣可知途徑長度為3+2=5;從結(jié)點(diǎn)４選擇唯一的一棵子樹到結(jié)點(diǎn)５，表達(dá)在圖中從頂點(diǎn)３到頂點(diǎn)4,途徑長度為5+2=7,結(jié)點(diǎn)5是葉子結(jié)點(diǎn),找到了一個可行解,途徑為1→2→3→4→1,途徑長度為７+3=10,目的函數(shù)值10成為新的下界,也就是目前的最優(yōu)解;從結(jié)點(diǎn)５回溯到結(jié)點(diǎn)４,再回溯到結(jié)點(diǎn)3，選擇結(jié)點(diǎn)3的第2棵子樹到結(jié)點(diǎn)6,表達(dá)在圖中從頂點(diǎn)2到頂點(diǎn)4,途徑長度為3+8＝１1，超過目的函數(shù)值1