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

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