計(jì)算機(jī)軟件基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)之算法

計(jì)算機(jī)軟件基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)之算法算法概述基本數(shù)據(jù)結(jié)構(gòu)排序算法查找算法圖論算法動(dòng)態(tài)規(guī)劃算法算法優(yōu)化與復(fù)雜度分析算法概述01算法的定義與特性算法是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算步驟。算法具有五個(gè)基本特性：有窮性、確定性、可行性、輸入和輸出。123枚舉算法、解析算法、查找算法、排序算法、圖論算法等。按照設(shè)計(jì)方法分類精確算法、近似算法、啟發(fā)式算法等。按照問(wèn)題求解模式分類數(shù)值計(jì)算算法、非數(shù)值計(jì)算算法、數(shù)據(jù)處理算法等。按照問(wèn)題類型分類算法的分類健壯性評(píng)估算法對(duì)于異常情況的處理能力和穩(wěn)定性。可讀性評(píng)估算法的易讀性和易理解性，對(duì)于代碼維護(hù)和團(tuán)隊(duì)協(xié)作至關(guān)重要。正確性評(píng)估算法是否能正確地解決給定的問(wèn)題。時(shí)間復(fù)雜度評(píng)估算法執(zhí)行時(shí)間隨問(wèn)題規(guī)模增長(zhǎng)的變化情況，常用大O表示法表示?？臻g復(fù)雜度評(píng)估算法執(zhí)行過(guò)程中所需存儲(chǔ)空間隨問(wèn)題規(guī)模增長(zhǎng)的變化情況。算法的評(píng)價(jià)指標(biāo)基本數(shù)據(jù)結(jié)構(gòu)0203線性表的存儲(chǔ)結(jié)構(gòu)包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其中順序存儲(chǔ)結(jié)構(gòu)通過(guò)數(shù)組實(shí)現(xiàn)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通過(guò)鏈表實(shí)現(xiàn)。01線性表的定義線性表是一種具有n個(gè)元素的有限序列。02線性表的邏輯結(jié)構(gòu)線性表中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。線性表?xiàng)５亩x棧是一種特殊的線性表，其插入和刪除操作限定在表的一端進(jìn)行，該端稱為棧頂，另一端稱為棧底。包括入棧、出棧、取棧頂元素等。隊(duì)列是一種特殊的線性表，其插入操作在表的一端進(jìn)行，而刪除操作在表的另一端進(jìn)行，插入元素的一端稱為隊(duì)尾，刪除元素的一端稱為隊(duì)頭。包括入隊(duì)、出隊(duì)、判斷隊(duì)列是否為空等。棧的基本操作隊(duì)列的定義隊(duì)列的基本操作棧與隊(duì)列串的定義串的基本操作數(shù)組的定義數(shù)組的基本操作串與數(shù)組01020304串是由零個(gè)或多個(gè)字符組成的有限序列。包括串的賦值、串的比較、串的連接、串的求長(zhǎng)、子串的查找等。數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)，它用一組連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)具有相同類型的數(shù)據(jù)元素。包括數(shù)組的創(chuàng)建、數(shù)組的訪問(wèn)、數(shù)組的遍歷、數(shù)組的排序等。樹(shù)的基本術(shù)語(yǔ)包括根節(jié)點(diǎn)、子節(jié)點(diǎn)、父節(jié)點(diǎn)、兄弟節(jié)點(diǎn)、葉子節(jié)點(diǎn)等。樹(shù)的定義樹(shù)是一種非線性數(shù)據(jù)結(jié)構(gòu)，由n個(gè)節(jié)點(diǎn)組成的有限集合。二叉樹(shù)的定義二叉樹(shù)是一種特殊的樹(shù)形結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)，通常子節(jié)點(diǎn)被稱作“左子節(jié)點(diǎn)”和“右子節(jié)點(diǎn)”。二叉樹(shù)的遍歷包括前序遍歷、中序遍歷和后序遍歷三種方式。二叉樹(shù)的性質(zhì)包括二叉樹(shù)的形態(tài)、二叉樹(shù)的深度、二叉樹(shù)的葉子節(jié)點(diǎn)數(shù)等。樹(shù)與二叉樹(shù)排序算法03將未排序的元素插入到已排序的序列中，從而得到一個(gè)新的、更長(zhǎng)的已排序序列。從第一個(gè)元素開(kāi)始，認(rèn)為該元素已經(jīng)被排序；取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；如果該元素（已排序）大于新元素，將該元素移到下一位置；重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；將新元素插入到該位置后；重復(fù)步驟2~5。穩(wěn)定排序，適用于少量數(shù)據(jù)的排序。原理實(shí)現(xiàn)特性插入排序原理在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ɑ蜃畲螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。實(shí)現(xiàn)在未排序序列中找到最小元素，存放到排序序列的起始位置；從剩余未排序元素中繼續(xù)尋找最小元素，然后放到已排序序列的末尾；重復(fù)步驟2，直到所有元素均排序完畢。特性不穩(wěn)定排序，適用于少量數(shù)據(jù)的排序。選擇排序原理：通過(guò)不斷地交換兩個(gè)相鄰的不等元素的位置，使得整個(gè)序列變得有序。實(shí)現(xiàn)：從第一個(gè)元素開(kāi)始，比較相鄰的兩個(gè)元素，如果前一個(gè)比后一個(gè)大，則交換它們的位置；對(duì)每一對(duì)相鄰元素做同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)；這步做完后，最后的元素會(huì)是最大的數(shù)；針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。特性：不穩(wěn)定排序，適用于少量數(shù)據(jù)的排序。交換排序采用分治法，將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。原理把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列；對(duì)這兩個(gè)子序列分別采用歸并排序；將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。實(shí)現(xiàn)穩(wěn)定排序，適用于大量數(shù)據(jù)的排序。特性歸并排序查找算法04原理從數(shù)據(jù)結(jié)構(gòu)的一端開(kāi)始，順序掃描，直到找到所查元素為止。時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度都是O(n)，其中n是數(shù)據(jù)結(jié)構(gòu)中元素的個(gè)數(shù)。適用場(chǎng)景適用于數(shù)據(jù)量較小或數(shù)據(jù)無(wú)序的情況。順序查找原理在有序數(shù)組中，取中間元素與目標(biāo)元素比較，若相等則查找成功；若目標(biāo)元素小于中間元素，則在左半部分繼續(xù)查找；若目標(biāo)元素大于中間元素，則在右半部分繼續(xù)查找。時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度都是O(logn)，其中n是數(shù)據(jù)結(jié)構(gòu)中元素的個(gè)數(shù)。適用場(chǎng)景適用于數(shù)據(jù)量較大且數(shù)據(jù)有序的情況。二分查找通過(guò)哈希函數(shù)將元素的關(guān)鍵字轉(zhuǎn)化為數(shù)組的索引，然后在對(duì)應(yīng)的數(shù)組位置上進(jìn)行查找。原理平均時(shí)間復(fù)雜度可以達(dá)到O(1)，最壞時(shí)間復(fù)雜度取決于哈希函數(shù)的設(shè)計(jì)和沖突處理方法。時(shí)間復(fù)雜度適用于需要快速查找且元素關(guān)鍵字與數(shù)組索引存在映射關(guān)系的情況。適用場(chǎng)景哈希表查找樹(shù)形查找在樹(shù)形數(shù)據(jù)結(jié)構(gòu)中，從根節(jié)點(diǎn)開(kāi)始，根據(jù)目標(biāo)元素與節(jié)點(diǎn)值的比較結(jié)果，沿著相應(yīng)的分支繼續(xù)查找，直到找到目標(biāo)元素或查找失敗。時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度取決于樹(shù)的高度和平衡性，對(duì)于平衡樹(shù)如AVL樹(shù)和紅黑樹(shù)，平均時(shí)間復(fù)雜度可以達(dá)到O(logn)，其中n是樹(shù)中節(jié)點(diǎn)的個(gè)數(shù)。適用場(chǎng)景適用于數(shù)據(jù)量較大且需要保持?jǐn)?shù)據(jù)有序的情況，如數(shù)據(jù)庫(kù)索引、文件系統(tǒng)等。原理圖論算法05鄰接表使用鏈表或數(shù)組來(lái)表示圖，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)鏈表或數(shù)組，存儲(chǔ)與該頂點(diǎn)相鄰的頂點(diǎn)信息。邊的集合使用一組邊來(lái)表示圖，每條邊包含起點(diǎn)、終點(diǎn)和權(quán)重等信息。鄰接矩陣使用一個(gè)二維數(shù)組來(lái)表示圖，數(shù)組中的每個(gè)元素表示對(duì)應(yīng)兩個(gè)頂點(diǎn)之間是否存在邊以及邊的權(quán)重。圖的表示與存儲(chǔ)最短路徑算法適用于所有類型的圖，通過(guò)動(dòng)態(tài)規(guī)劃的思想，不斷更新任意兩點(diǎn)之間的最短路徑估計(jì)值，最終得到所有頂點(diǎn)之間的最短路徑。Floyd算法適用于沒(méi)有負(fù)權(quán)重的有向圖，通過(guò)不斷選擇當(dāng)前距離起點(diǎn)最短的頂點(diǎn)，并更新其相鄰頂點(diǎn)的距離，最終得到起點(diǎn)到所有其他頂點(diǎn)的最短路徑。Dijkstra算法適用于有負(fù)權(quán)重的有向圖，通過(guò)對(duì)所有邊進(jìn)行松弛操作，不斷更新頂點(diǎn)的最短路徑估計(jì)值，最終得到起點(diǎn)到所有其他頂點(diǎn)的最短路徑。Bellman-Ford算法從任意一個(gè)頂點(diǎn)開(kāi)始，每次選擇連接已選頂點(diǎn)和未選頂點(diǎn)中權(quán)重最小的邊，將對(duì)應(yīng)的頂點(diǎn)加入已選集合，直到所有頂點(diǎn)都被選中。將所有邊按照權(quán)重從小到大排序，從輕到重依次選擇邊，每次選擇一條連接兩個(gè)未連通集合的邊，直到所有頂點(diǎn)都在同一個(gè)連通集合中。最小生成樹(shù)算法Kruskal算法Prim算法對(duì)于有向無(wú)環(huán)圖（DAG），通過(guò)不斷刪除入度為0的頂點(diǎn)并更新相關(guān)頂點(diǎn)的入度，最終得到一個(gè)線性序列，使得對(duì)于任意一條有向邊(u,v)，u在序列中都出現(xiàn)在v之前。拓?fù)渑判蛟趲?quán)有向無(wú)環(huán)圖中，從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑稱為關(guān)鍵路徑。通過(guò)計(jì)算每個(gè)頂點(diǎn)的最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間，可以確定關(guān)鍵路徑以及關(guān)鍵活動(dòng)（即位于關(guān)鍵路徑上的活動(dòng)）。關(guān)鍵路徑拓?fù)渑判蚺c關(guān)鍵路徑動(dòng)態(tài)規(guī)劃算法06大問(wèn)題的最優(yōu)解可以由小問(wèn)題的最優(yōu)解推出。最優(yōu)子結(jié)構(gòu)遞歸的終止條件。邊界描述子問(wèn)題之間是如何轉(zhuǎn)化的，即如何由小問(wèn)題的最優(yōu)解推出大問(wèn)題的最優(yōu)解。狀態(tài)轉(zhuǎn)移方程動(dòng)態(tài)規(guī)劃原理01背包每個(gè)物品只有一件，可以選擇放或不放。完全背包每個(gè)物品有無(wú)限件，可以選擇放多件。多重背包每個(gè)物品有多件，可以選擇放多件但不超過(guò)數(shù)量限制。背包問(wèn)題030201問(wèn)題描述給定兩個(gè)序列，求出它們的最長(zhǎng)公共子序列的長(zhǎng)度。解決方案使用動(dòng)態(tài)規(guī)劃，定義一個(gè)二維數(shù)組dp，其中dp[i][j]表示第一個(gè)序列的前i個(gè)字符與第二個(gè)序列的前j個(gè)字符的最長(zhǎng)公共子序列的長(zhǎng)度。狀態(tài)轉(zhuǎn)移方程為dp[i][j]=dp[i-1][j-1]+1(ifs1[i]==s2[j])，dp[i][j]=max(dp[i-1][j],dp[i][j-1])(ifs1[i]!=s2[j])。最長(zhǎng)公共子序列問(wèn)題給定兩個(gè)字符串，求將一個(gè)字符串轉(zhuǎn)換成另一個(gè)字符串所需的最少編輯操作次數(shù)（插入、刪除或替換一個(gè)字符）。最短編輯距離給定一個(gè)矩陣鏈，求出最優(yōu)的乘法順序使得乘法運(yùn)算次數(shù)最少。矩陣鏈乘法其他典型問(wèn)題及應(yīng)用場(chǎng)景算法優(yōu)化與復(fù)雜度分析07時(shí)間復(fù)雜度概念衡量算法執(zhí)行時(shí)間隨問(wèn)題規(guī)模增長(zhǎng)的速度，常用大O表示法。常見(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í)間復(fù)雜度分析方法通過(guò)計(jì)算算法中基本操作執(zhí)行次數(shù)與問(wèn)題規(guī)模的關(guān)系，確定算法的時(shí)間復(fù)雜度。時(shí)間復(fù)雜度分析常見(jiàn)空間復(fù)雜度類型常數(shù)空間復(fù)雜度O(1)、線性空間復(fù)雜度O(n)等。空間復(fù)雜度分析方法通過(guò)分析算法中所需存儲(chǔ)空間的數(shù)量級(jí)與問(wèn)題規(guī)模的關(guān)系，確定算法的空間復(fù)雜度?？臻g復(fù)雜度概念衡量算法所需存儲(chǔ)空間隨問(wèn)