計算機算法設(shè)計與分析知識點整理

算法是一系列解決問題的清晰指令，也就是說，能夠?qū)Ψ弦欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。簡單的說，就是解決問題的一種方法或過程。算法－特征：（1）確定性（2）多樣性（3）有窮性（4）輸出所需資源越少，該算法越好，計算機最重要的資源是時間和空間把基本操作（最重要的操作）次數(shù)作為算法運行時間的度量單位。T(n)≈copC(n)基本操作的執(zhí)行時間基本操作次數(shù)算法輸入規(guī)模n為時間效率的參數(shù)算法的時間效率和空間效率都用輸入規(guī)模的函數(shù)進行度量O(g(n))是增長次數(shù)小于等于g(n)(以及其常數(shù)倍，n趨向于無窮大)的函數(shù)集合。符號О成立條件：對于所有足夠大的n，t(n)的上界由g(n)的常數(shù)倍數(shù)所確定。即，存在大于0的常數(shù)c和非負(fù)的整數(shù)n0，使得：對于所有的n≥n0來說，t(n)≤cg(n)?(g(n))代表增長次數(shù)大于等于g(n)(以及其常數(shù)倍,n趨向于無窮大)的函數(shù)集合符號?成立條件：對于所有足夠大的n，t(n)的下界由g(n)的常數(shù)倍所確定，即，存在大于0的常數(shù)c和非負(fù)的整數(shù)n0，使得：對于所有的n≥n0來說，t(n)≥cg(n)Θ(g(n))是增長次數(shù)等于g(n)(以及其常數(shù)倍,n趨向于無窮大)的函數(shù)集合。符號Θ成立條件：對于所有足夠大的n，t(n)的上界和下界都由g(n)的常數(shù)倍數(shù)所確定，即，存在大于0的常數(shù)c1，c2和和非負(fù)的整數(shù)n0，使得：對于所有的n≥n0來說，c2g(n)≤t(n)≤c1g(n)算法的整體效率是由具有較大的增長次數(shù)的部分所決定的，即它的效率較差的部分。1lognnnlognn2n32nn!動態(tài)規(guī)劃算法的基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問題性質(zhì)矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果通常不同的子問題個數(shù)隨問題的大小呈多項式增長動態(tài)規(guī)劃算法的步驟(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。(3)以自底向上的方式計算出最優(yōu)值。(4)根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。基本思想也是將待求解問題分解成若干個子問題,能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算，從而得到多項式時間算法貪心法只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個選擇都不會改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu),這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解（OptimalSolution），但通常能獲得近似最優(yōu)解貪心法求解的問題的特征：（1）最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，也稱此問題滿足最優(yōu)性原理。（2）貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來得到。動態(tài)規(guī)劃法通常以自底向上的方式求解各個子問題，而貪心法則通常以自頂向下的方式做出一系列的貪心選擇。圖著色貪心策略：選擇一種顏色，以任意頂點作為開始頂點，依次考察圖中的未被著色的每個頂點，如果一個頂點可以用顏色1著色，換言之，該頂點的鄰接點都還未被著色，則用顏色1為該頂點著色。當(dāng)沒有頂點能以這種顏色著色時，選擇顏色2和一個未被著色的頂點作為開始頂點，用第二種顏色為盡可能多的頂點著色，如果還有未著色的頂點，則選取顏色3并為盡可能多的頂點著色，依此類推。最小生成樹問題至少有兩種合理的貪心策略：最近頂點策略：任選一個頂點，并以此建立起生成樹，每一步的貪心選擇是簡單地把不在生成樹中的最近頂點添加到生成樹中。Prim算法應(yīng)用貪心策略,使生成樹以一種自然的方式生長，即從任意頂點開始，每一步為這棵樹添加一個分枝，直到生成樹中包含全部頂點。最短邊策略：設(shè)G=(V，E)是一個無向連通網(wǎng)，令T=(U，TE)是G的最小生成樹。最短邊策略從TE={}開始，每一次貪心選擇都是在邊集E中選取最短邊(u,v)，如果邊(u,v)加入集合TE中不產(chǎn)生回路，則將邊(u,v)加入邊集TE中，并將它在集合E中刪去。Kruskal算法應(yīng)用貪心策略，它使生成樹以一種隨意的方式生長，先讓森林中的樹木隨意生長，每生長一次就將兩棵樹合并，到最后合并成一棵樹所有可能的解向量構(gòu)成了問題的解空間。問題的解空間一般用解空間樹（也稱狀態(tài)空間樹）的方式組織?；厮莘◤母Y(jié)點出發(fā)，按照深度優(yōu)先策略遍歷解空間樹，搜索滿足約束條件的解。在用回溯法求解問題時，常常遇到兩種典型的解空間樹：（1）子集樹（SubsetTrees）：當(dāng)所給問題是從n個元素的集合中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為子集樹。在子集樹中，|S1|=|S2|=…=|Sn|=c，即每個結(jié)點有相同數(shù)目的子樹，通常情況下c=2，所以，子集樹中共有2n個葉子結(jié)點，因此，遍歷子集樹需要Ω(2n)時間。（2）排列樹（PermutationTrees）：當(dāng)所給問題是確定n個元素滿足某種性質(zhì)的排列時，相應(yīng)的解空間樹稱為排列樹。在排列樹中，通常情況下，|S1|=n，|S2|=n-1，…，|Sn|=1，所以，排列樹中共有n!個葉子結(jié)點，因此，遍歷排列樹需要Ω(n!)時間?；厮莘▽嶋H也是窮舉,最壞情況下的時間代價肯定是指數(shù)階.分支限界法首先確定一個合理的限界函數(shù)，并根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界[down,up]按照廣度優(yōu)先策略遍歷問題的解空間樹，在分支結(jié)點上，依次搜索該結(jié)點的所有孩子結(jié)點，分別估算這些孩子結(jié)點的目標(biāo)函數(shù)的可能取值。如果某孩子結(jié)點的目標(biāo)函數(shù)可能取得的值超出目標(biāo)函數(shù)的界，則將其丟棄，因為從這個結(jié)點生成的解不會比目前已經(jīng)得到的解更好；否則，將其加入待處理結(jié)點表（以下簡稱表PT）中。依次從表PT中選取使目標(biāo)函數(shù)的值取得極值的結(jié)點成為當(dāng)前擴展結(jié)點，重復(fù)上述過程，直到找到最優(yōu)解。分治法總體思想將一個難以解決的大問題分割為k個子問題,對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。?將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解分治法的設(shè)計思想是將一個難以直接解決的大問題，分割成一些規(guī)模較小的子問;這些子問題互相獨立且與原問題相同;2)遞歸地解子問題;3)將各個子問題的解合并得到原問題的解.直接或間接地調(diào)用自身的算法稱為遞歸算法合并排序基本思想?將待排序元素分成大小大致相同的2個子集合分別對2個子集