計(jì)算機(jī)算法分析與設(shè)計(jì)第2章

計(jì)算機(jī)算法分析與設(shè)計(jì)第2章算法分析基礎(chǔ)分治策略與應(yīng)用動(dòng)態(tài)規(guī)劃原理及實(shí)例貪心算法原理及實(shí)例回溯法原理及實(shí)例分支限界法原理及實(shí)例contents目錄算法分析基礎(chǔ)CATALOGUE01時(shí)間復(fù)雜度的定義描述算法運(yùn)行時(shí)間隨問(wèn)題規(guī)模增長(zhǎng)的速度。大O表示法表示算法時(shí)間復(fù)雜度的漸近上界。常見(jiàn)時(shí)間復(fù)雜度常數(shù)時(shí)間復(fù)雜度O(1)、線性時(shí)間復(fù)雜度O(n)、對(duì)數(shù)時(shí)間復(fù)雜度O(logn)、線性對(duì)數(shù)時(shí)間復(fù)雜度O(nlogn)、平方時(shí)間復(fù)雜度O(n^2)、立方時(shí)間復(fù)雜度O(n^3)、指數(shù)時(shí)間復(fù)雜度O(2^n)。算法時(shí)間復(fù)雜度123描述算法在運(yùn)行過(guò)程中所需額外空間的數(shù)量級(jí)?？臻g復(fù)雜度的定義常數(shù)空間復(fù)雜度O(1)、線性空間復(fù)雜度O(n)、平方空間復(fù)雜度O(n^2)。常見(jiàn)空間復(fù)雜度在算法設(shè)計(jì)中，通常需要權(quán)衡時(shí)間復(fù)雜度和空間復(fù)雜度的關(guān)系，以達(dá)到最優(yōu)的算法性能?？臻g復(fù)雜度與時(shí)間復(fù)雜度的關(guān)系算法空間復(fù)雜度最好情況分析：指算法在最佳情況下的性能表現(xiàn)，通常對(duì)應(yīng)時(shí)間復(fù)雜度的下界。最壞情況分析：指算法在最差情況下的性能表現(xiàn)，通常對(duì)應(yīng)時(shí)間復(fù)雜度的上界。平均情況分析：指算法在所有可能輸入下的平均性能表現(xiàn)，通常用于評(píng)估算法的實(shí)際性能。最好、最壞和平均情況分析的意義：對(duì)于某些算法，其在最好和最壞情況下的性能差異可能非常大，因此需要對(duì)算法在不同情況下的性能表現(xiàn)進(jìn)行全面評(píng)估。同時(shí)，平均情況分析可以幫助我們更好地了解算法在實(shí)際應(yīng)用中的性能表現(xiàn)。最好、最壞和平均情況分析分治策略與應(yīng)用CATALOGUE02分治策略思想將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；遞歸地解這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題的解。歸并排序是采用分治法的一個(gè)非常典型的應(yīng)用；歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組；將數(shù)組分解成兩個(gè)較小的子數(shù)組，直到子數(shù)組的大小為1，然后將子數(shù)組兩兩合并。典型問(wèn)題：歸并排序快速排序是C.R.A.Hoare于1960年提出的一種劃分交換排序；快速排序的基本思想是，通過(guò)一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。它采用了一種分治的策略，通常稱其為分治法；典型問(wèn)題：快速排序動(dòng)態(tài)規(guī)劃原理及實(shí)例CATALOGUE03最優(yōu)子結(jié)構(gòu)性質(zhì)大問(wèn)題的最優(yōu)解可以由小問(wèn)題的最優(yōu)解推出，即問(wèn)題的最優(yōu)解具有子問(wèn)題的最優(yōu)解組合而成的性質(zhì)。邊界條件確定動(dòng)態(tài)規(guī)劃問(wèn)題的邊界條件，即子問(wèn)題的最小規(guī)模，以便從邊界條件開(kāi)始逐步求解更大規(guī)模的問(wèn)題。狀態(tài)轉(zhuǎn)移方程根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)，建立狀態(tài)轉(zhuǎn)移方程，描述子問(wèn)題之間的遞推關(guān)系，從而可以通過(guò)迭代或遞歸的方式求解原問(wèn)題。動(dòng)態(tài)規(guī)劃原理給定一組物品，每種物品都有一定的重量和價(jià)值，背包的總?cè)萘坑邢?。如何選擇物品放入背包，使得背包內(nèi)物品的總價(jià)值最大？問(wèn)題描述定義狀態(tài)dp[i][j]表示前i個(gè)物品放入容量為j的背包中所能獲得的最大價(jià)值。根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)，可以得到狀態(tài)轉(zhuǎn)移方程dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}，其中w[i]和v[i]分別表示第i個(gè)物品的重量和價(jià)值。通過(guò)迭代計(jì)算dp數(shù)組，最終得到dp[n][m]即為背包問(wèn)題的最優(yōu)解，其中n為物品數(shù)量，m為背包容量。動(dòng)態(tài)規(guī)劃解法背包問(wèn)題VS給定兩個(gè)字符串X和Y，找出它們的最長(zhǎng)公共子序列。最長(zhǎng)公共子序列是指這樣一個(gè)序列，它是X和Y的公共子序列（即可以從X和Y中刪除一些字符得到），且它的長(zhǎng)度是所有公共子序列中最長(zhǎng)的。動(dòng)態(tài)規(guī)劃解法定義狀態(tài)dp[i][j]表示字符串X的前i個(gè)字符和字符串Y的前j個(gè)字符的最長(zhǎng)公共子序列長(zhǎng)度。根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)，可以得到狀態(tài)轉(zhuǎn)移方程dp[i][j]=dp[i-1][j-1]+1（當(dāng)X[i]==Y[j]時(shí)），或者dp[i][j]=max{dp[i-1][j],dp[i][j-1]}（當(dāng)X[i]!=Y[j]時(shí)）。通過(guò)迭代計(jì)算dp數(shù)組，最終得到dp[n][m]即為最長(zhǎng)公共子序列的長(zhǎng)度，其中n和m分別為字符串X和Y的長(zhǎng)度。問(wèn)題描述最長(zhǎng)公共子序列貪心算法原理及實(shí)例CATALOGUE04貪心算法原理貪心算法在每一步都采取當(dāng)前狀態(tài)下最好或最優(yōu)（即最有利）的選擇，從而希望導(dǎo)致結(jié)果是全局最好或最優(yōu)的。不可回溯貪心算法在有多個(gè)可選方案時(shí)，總是選擇當(dāng)前看來(lái)最好的方案，而不考慮其他可能更優(yōu)的方案。因此，一旦做出選擇，就不能回溯。適用于優(yōu)化問(wèn)題貪心算法通常用于解決優(yōu)化問(wèn)題，如求最大值、最小值或最優(yōu)解等。局部最優(yōu)選擇010203問(wèn)題描述給定一個(gè)由活動(dòng)的集合，每個(gè)活動(dòng)都有一個(gè)開(kāi)始時(shí)間和一個(gè)結(jié)束時(shí)間?；顒?dòng)選擇問(wèn)題要求選擇出最大的相互兼容的活動(dòng)子集，即這些活動(dòng)的時(shí)間不會(huì)相互沖突。貪心策略在活動(dòng)選擇問(wèn)題中，貪心算法的策略是按照活動(dòng)的結(jié)束時(shí)間進(jìn)行排序，然后選擇結(jié)束時(shí)間最早的活動(dòng)，再依次選擇與已選活動(dòng)不沖突的活動(dòng)。實(shí)例假設(shè)有4個(gè)活動(dòng)，其開(kāi)始時(shí)間和結(jié)束時(shí)間分別為(1,3)，(2,4)，(3,5)，(1,2)。按照結(jié)束時(shí)間排序后得到(1,2)，(1,3)，(2,4)，(3,5)。首先選擇(1,2)，然后選擇(2,4)，因?yàn)檫@兩個(gè)活動(dòng)的時(shí)間不沖突。因此，最大相互兼容的活動(dòng)子集為{(1,2)，(2,4)}?；顒?dòng)選擇問(wèn)題問(wèn)題描述給定一個(gè)連通的無(wú)向圖，最小生成樹(shù)問(wèn)題是要求出該圖的一棵包含所有頂點(diǎn)的樹(shù)，且樹(shù)上各邊的權(quán)值之和最小。貪心策略在最小生成樹(shù)問(wèn)題中，貪心算法的策略是每次選擇權(quán)值最小的邊加入生成樹(shù)中，但要保證加入后不會(huì)形成環(huán)。實(shí)例假設(shè)有一個(gè)包含4個(gè)頂點(diǎn)的無(wú)向圖，其邊的權(quán)值分別為{1,2}，{2,3}，{3,4}，{4,1}的權(quán)值分別為1，2，3，4。按照權(quán)值從小到大排序后得到{1,2}，{2,3}，{3,4}，{4,1}。首先選擇{1,2}，然后選擇{2,3}，再選擇{3,4}。因此，最小生成樹(shù)為{{1,2}，{2,3}，{3,4}}，權(quán)值之和為6。最小生成樹(shù)回溯法原理及實(shí)例CATALOGUE05回溯法是一種基于試探和逐步回退的搜索算法，通過(guò)不斷嘗試和撤銷操作來(lái)尋找問(wèn)題的解?；厮莘ǖ幕舅枷胧菑膯?wèn)題的某一初始狀態(tài)出發(fā)，通過(guò)逐步改變狀態(tài)來(lái)試探所有可能的解。當(dāng)試探到某一步時(shí)，如果發(fā)現(xiàn)當(dāng)前狀態(tài)不能達(dá)到問(wèn)題的目標(biāo)或無(wú)法滿足問(wèn)題的約束條件時(shí)，就“回溯”到上一步或若干步之前的狀態(tài)，重新試探其他的可能解。回溯法通過(guò)遞歸或迭代的方式實(shí)現(xiàn)，可以系統(tǒng)地搜索問(wèn)題的所有可能解，適用于求解組合數(shù)較多的問(wèn)題?；厮莘ㄔ鞱皇后問(wèn)題010203N皇后問(wèn)題是一個(gè)經(jīng)典的回溯問(wèn)題，其目標(biāo)是在N×N的棋盤上放置N個(gè)皇后，使得它們不能互相攻擊?；厮莘ㄇ蠼釴皇后問(wèn)題的基本思路是從第一行開(kāi)始逐行放置皇后，每次放置一個(gè)皇后后檢查是否與其他已放置的皇后沖突。如果沖突，則回溯到上一行重新放置；如果不沖突，則繼續(xù)放置下一行的皇后。在實(shí)現(xiàn)上，可以使用一個(gè)數(shù)組來(lái)表示每行皇后的位置，同時(shí)使用兩個(gè)數(shù)組分別記錄每列和每條對(duì)角線上是否有皇后。通過(guò)遍歷數(shù)組和檢查沖突，可以逐步找到所有可能的解。圖的著色問(wèn)題是一個(gè)著名的NP完全問(wèn)題，其目標(biāo)是對(duì)給定的圖進(jìn)行著色，使得相鄰的頂點(diǎn)顏色不同，且使用的顏色數(shù)最少。回溯法求解圖的著色問(wèn)題的基本思路是從第一個(gè)頂點(diǎn)開(kāi)始著色，每次為當(dāng)前頂點(diǎn)選擇一種顏色，然后遞歸地對(duì)與當(dāng)前頂點(diǎn)相鄰的未著色頂點(diǎn)進(jìn)行著色。如果當(dāng)前頂點(diǎn)無(wú)法著色，則回溯到上一個(gè)頂點(diǎn)重新選擇顏色。在實(shí)現(xiàn)上，可以使用一個(gè)數(shù)組來(lái)表示每個(gè)頂點(diǎn)的顏色，同時(shí)使用一個(gè)鄰接矩陣來(lái)表示圖的結(jié)構(gòu)。通過(guò)遍歷頂點(diǎn)和遞歸著色，可以逐步找到所有可能的解。同時(shí)，可以使用一些優(yōu)化策略來(lái)減少搜索空間，如優(yōu)先選擇顏色數(shù)較少的頂點(diǎn)進(jìn)行著色等。圖的著色問(wèn)題分支限界法原理及實(shí)例CATALOGUE06采用廣度優(yōu)先或深度優(yōu)先策略，遍歷問(wèn)題的解空間樹(shù)。搜索策略對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行評(píng)估，根據(jù)評(píng)估結(jié)果和已找到的最優(yōu)解，決定是否繼續(xù)搜索該節(jié)點(diǎn)及其子樹(shù)。限界操作在解空間樹(shù)的每個(gè)節(jié)點(diǎn)處，根據(jù)問(wèn)題的約束條件進(jìn)行分支，生成子節(jié)點(diǎn)。分支操作在搜索過(guò)程中，及時(shí)剪去不可能得到最優(yōu)解的分支，減少搜索量。剪枝操作01030204分支限界法原理剪枝策略在搜索過(guò)程中，如果某個(gè)分支的總重量已經(jīng)超過(guò)背包容量，或者總價(jià)值已經(jīng)小于當(dāng)前最優(yōu)解，則直接剪去該分支。問(wèn)題描述給定一組物品，每種物品都有自己的重量和價(jià)值，背包的總?cè)萘坑邢?。要求選擇一些物品裝入背包，使得背包內(nèi)物品的總價(jià)值最大。分支策略對(duì)每個(gè)物品，選擇裝入背包或不裝入背包，生成兩個(gè)子節(jié)點(diǎn)。限界策略根據(jù)當(dāng)前背包剩余容量和已選物品的總價(jià)值，估算繼續(xù)搜索可能得到的最大價(jià)值。如果估算價(jià)值小于當(dāng)前最優(yōu)解，則停止搜索該分支。0-1背包問(wèn)題第二季度第一季度第四季度第三季度問(wèn)題描述分支策略限界策略剪枝策略旅行商問(wèn)題給定一組城市和每對(duì)城市之間的距離，要求旅行商從某個(gè)城市出發(fā)，訪問(wèn)所有