算法基礎(chǔ)知識(shí)培訓(xùn)課件

算法基礎(chǔ)知識(shí)培訓(xùn)課件算法概述與分類基本數(shù)據(jù)結(jié)構(gòu)排序算法查找算法圖論算法動(dòng)態(tài)規(guī)劃貪心算法與分治策略contents目錄算法概述與分類01CATALOGUE算法是一系列解決問(wèn)題的清晰指令，代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制。算法定義算法在計(jì)算機(jī)科學(xué)中扮演著核心角色，用于指導(dǎo)計(jì)算機(jī)如何執(zhí)行特定任務(wù)或解決特定問(wèn)題。算法作用算法定義及作用輸出項(xiàng)有限性算法必須能在執(zhí)行有限個(gè)步驟之后終止?？尚行运惴ǖ拿恳徊蕉急仨毷强尚械?，也就是說(shuō)，每一步都能夠通過(guò)執(zhí)行有限次數(shù)完成。輸入項(xiàng)一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫(huà)運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定出了初始條件。包括排序算法、搜索算法、圖論算法、動(dòng)態(tài)規(guī)劃等?；舅惴ǚ诸惔_定性算法的每一步驟必須有確切的定義。一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒(méi)有輸出的算法是毫無(wú)意義的。算法分類與特點(diǎn)健壯性當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能做出相關(guān)處理，而不是產(chǎn)生異?；蚰涿畹慕Y(jié)果?？勺x性算法設(shè)計(jì)的另一目的是為了便于閱讀、理解和交流。正確性算法的正確性是評(píng)價(jià)一個(gè)算法優(yōu)劣的最重要的標(biāo)準(zhǔn)。時(shí)間復(fù)雜度評(píng)估執(zhí)行程序所需的時(shí)間?？梢怨浪愠龀绦?qū)μ幚砥鞯氖褂贸潭取？臻g復(fù)雜度評(píng)估執(zhí)行程序所需的存儲(chǔ)空間?？梢怨浪愠龀绦?qū)τ?jì)算機(jī)內(nèi)存的使用程度。算法評(píng)價(jià)標(biāo)準(zhǔn)基本數(shù)據(jù)結(jié)構(gòu)02CATALOGUE線性表的定義與性質(zhì)線性表是一種具有n個(gè)元素的有限序列線性表中的數(shù)據(jù)元素具有相同的類型線性表相鄰元素之間具有前驅(qū)和后繼關(guān)系線性表的順序存儲(chǔ)結(jié)構(gòu)用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素線性表通過(guò)數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素（這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通過(guò)指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系線性表?xiàng)５亩x與性質(zhì)棧是一種特殊的線性表，其插入和刪除操作限定在表的一端進(jìn)行，該端稱為棧頂，另一端稱為棧底棧與隊(duì)列棧中沒(méi)有元素時(shí)稱為空棧棧具有后進(jìn)先出（LIFO）的特性隊(duì)列的定義與性質(zhì)棧與隊(duì)列隊(duì)列是一種特殊的線性表，其插入操作在表的一端進(jìn)行，而刪除操作在表的另一端進(jìn)行，插入元素的一端稱為隊(duì)尾，刪除元素的一端稱為隊(duì)頭棧與隊(duì)列隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列隊(duì)列具有先進(jìn)先出（FIFO）的特性棧與隊(duì)列樹(shù)的基本概念與性質(zhì)樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，由n（n>=0）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合樹(shù)中的節(jié)點(diǎn)具有父節(jié)點(diǎn)、子節(jié)點(diǎn)、兄弟節(jié)點(diǎn)等概念樹(shù)與二叉樹(shù)樹(shù)的高度、深度、葉子節(jié)點(diǎn)、路徑等概念二叉樹(shù)的基本概念與性質(zhì)二叉樹(shù)是一種特殊的樹(shù)，每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)樹(shù)與二叉樹(shù)二叉樹(shù)的五種基本形態(tài)空二叉樹(shù)、只有一個(gè)根節(jié)點(diǎn)的二叉樹(shù)、只有左子樹(shù)或右子樹(shù)的二叉樹(shù)、具有左右子樹(shù)的二叉樹(shù)二叉樹(shù)的性質(zhì)第i層上至多有2^(i-1)個(gè)節(jié)點(diǎn)（i>=1）、深度為k的二叉樹(shù)至多有2^k-1個(gè)節(jié)點(diǎn)（k>=1）等樹(shù)與二叉樹(shù)123圖的基本概念與性質(zhì)圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為G（V,E）圖中的頂點(diǎn)表示對(duì)象，邊表示對(duì)象之間的關(guān)系圖及其應(yīng)用010204圖及其應(yīng)用圖中的邊有方向和無(wú)方向之分，分別稱為有向圖和無(wú)向圖圖的應(yīng)用場(chǎng)景與實(shí)例分析圖論在計(jì)算機(jī)科學(xué)、電子工程、運(yùn)籌學(xué)等領(lǐng)域有著廣泛的應(yīng)用實(shí)例分析：最短路徑問(wèn)題、最小生成樹(shù)問(wèn)題、拓?fù)渑判騿?wèn)題等03排序算法03CATALOGUE通過(guò)相鄰元素之間的比較和交換，使得每一輪比較后最大（或最?。┑脑啬軌颉懊芭荨钡叫蛄械囊欢?。原理最好情況為O(n)，最壞和平均情況為O(n^2)。時(shí)間復(fù)雜度O(1)?？臻g復(fù)雜度穩(wěn)定。穩(wěn)定性冒泡排序原理時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性選擇排序01020304每次從未排序的元素中選出最?。ɑ蜃畲螅┑脑兀诺揭雅判蛐蛄械哪┪?。無(wú)論最好、最壞還是平均情況，均為O(n^2)。O(1)。不穩(wěn)定。原理時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性插入排序?qū)⑽磁判虻脑夭迦氲揭雅判蛐蛄械暮线m位置中，以達(dá)到排序的目的。O(1)。最好情況為O(n)，最壞和平均情況為O(n^2)。穩(wěn)定。時(shí)間復(fù)雜度無(wú)論最好、最壞還是平均情況，均為O(nlogn)。穩(wěn)定性穩(wěn)定?？臻g復(fù)雜度O(n)。原理采用分治策略，將序列不斷拆分為子序列，直到子序列長(zhǎng)度為1，然后將相鄰子序列進(jìn)行歸并排序。歸并排序原理：通過(guò)一趟排序?qū)⒋判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另一部分的所有數(shù)據(jù)要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。時(shí)間復(fù)雜度：最好情況為O(nlogn)，最壞情況為O(n^2)，平均情況為O(nlogn)?？臻g復(fù)雜度：O(logn)。穩(wěn)定性：不穩(wěn)定?？焖倥判虿檎宜惴?4CATALOGUE從數(shù)據(jù)結(jié)構(gòu)的一端開(kāi)始，順序掃描，直到找到所查元素為止。原理時(shí)間復(fù)雜度適用場(chǎng)景平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度都是O(n)，其中n是數(shù)據(jù)結(jié)構(gòu)中元素的數(shù)量。適用于數(shù)據(jù)量較小或數(shù)據(jù)無(wú)序的情況。030201順序查找原理在有序數(shù)組中，取中間元素與目標(biāo)值進(jìn)行比較，若相等則查找成功；若目標(biāo)值小于中間元素，則在數(shù)組的前半部分繼續(xù)查找；若目標(biāo)值大于中間元素，則在數(shù)組的后半部分繼續(xù)查找。重復(fù)上述過(guò)程，直到找到目標(biāo)值或確定目標(biāo)值不存在于數(shù)組中。時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度都是O(logn)，其中n是數(shù)據(jù)結(jié)構(gòu)中元素的數(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ù)雜度為O(n)，其中n是哈希表中元素的數(shù)量。時(shí)間復(fù)雜度適用于需要快速查找且元素?cái)?shù)量較多的情況。適用場(chǎng)景哈希表查找

樹(shù)形查找結(jié)構(gòu)原理利用樹(shù)形結(jié)構(gòu)進(jìn)行查找，常見(jiàn)的樹(shù)形查找結(jié)構(gòu)包括二叉搜索樹(shù)、平衡二叉樹(shù)、B樹(shù)、B+樹(shù)等。時(shí)間復(fù)雜度不同的樹(shù)形查找結(jié)構(gòu)具有不同的時(shí)間復(fù)雜度，但通常都可以在O(logn)的時(shí)間內(nèi)完成查找操作，其中n是樹(shù)中節(jié)點(diǎn)的數(shù)量。適用場(chǎng)景適用于需要快速查找且元素?cái)?shù)量較多的情況，尤其是當(dāng)元素之間存在某種特定的排序關(guān)系時(shí)。圖論算法05CATALOGUE03Bellman-Ford算法適用于有負(fù)權(quán)邊的有向圖，通過(guò)對(duì)所有邊進(jìn)行松弛操作求解最短路徑。01Dijkstra算法適用于沒(méi)有負(fù)權(quán)邊的有向圖，通過(guò)貪心策略逐步確定起點(diǎn)到各頂點(diǎn)的最短路徑。02Floyd算法適用于任意有向圖，通過(guò)動(dòng)態(tài)規(guī)劃思想求解任意兩點(diǎn)間的最短路徑。最短路徑問(wèn)題適用于稠密圖，通過(guò)逐步構(gòu)建生成樹(shù)的方式求解最小生成樹(shù)。Prim算法適用于稀疏圖，通過(guò)并查集實(shí)現(xiàn)邊的合并，求解最小生成樹(shù)。Kruskal算法最小生成樹(shù)問(wèn)題適用于有向無(wú)環(huán)圖（DAG），通過(guò)不斷刪除入度為0的頂點(diǎn)并更新相關(guān)頂點(diǎn)的入度，最終得到拓?fù)湫蛄小Ｔ谕負(fù)渑判虻幕A(chǔ)上，計(jì)算每個(gè)頂點(diǎn)的最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間，從而確定關(guān)鍵路徑和關(guān)鍵活動(dòng)。拓?fù)渑判蚺c關(guān)鍵路徑關(guān)鍵路徑拓?fù)渑判蚓W(wǎng)絡(luò)流問(wèn)題最大流問(wèn)題求解網(wǎng)絡(luò)中從源點(diǎn)到匯點(diǎn)的最大可行流量，常用算法包括Ford-Fulkerson算法和Edmonds-Karp算法。最小割問(wèn)題求解網(wǎng)絡(luò)中將源點(diǎn)和匯點(diǎn)分離的最小割集，即最小割容量。最小割容量等于最大流量，是網(wǎng)絡(luò)流理論中的基本定理。動(dòng)態(tài)規(guī)劃06CATALOGUE原理動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)中使用的，通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式來(lái)求解復(fù)雜問(wèn)題的方法。思想動(dòng)態(tài)規(guī)劃算法通常用于優(yōu)化遞歸問(wèn)題，如斐波那契數(shù)列，或者用于解決具有重疊子問(wèn)題和最優(yōu)子結(jié)構(gòu)的問(wèn)題。動(dòng)態(tài)規(guī)劃原理及思想背包問(wèn)題、最長(zhǎng)公共子序列、最短路徑問(wèn)題等。典型問(wèn)題從問(wèn)題的整體出發(fā)，逐步細(xì)化問(wèn)題的規(guī)模，直到問(wèn)題的規(guī)模縮小到可以直接求解的程度。自頂向下從問(wèn)題的最小規(guī)模開(kāi)始，逐步擴(kuò)大問(wèn)題的規(guī)模，直到達(dá)到問(wèn)題的整體規(guī)模。自底向上典型問(wèn)題分析與求解方法完全背包問(wèn)題與01背包問(wèn)題類似，但每種物品可以選擇多次。01背包問(wèn)題給定一組物品，每種物品都有自己的重量和價(jià)值，在限定的總重量?jī)?nèi)，如何選擇物品使得物品的總價(jià)值最大。多重背包問(wèn)題與01背包問(wèn)題類似，但每種物品有一個(gè)數(shù)量限制。背包問(wèn)題及其變形最長(zhǎng)公共子序列問(wèn)題給定兩個(gè)序列，找出它們的最長(zhǎng)公共子序列。問(wèn)題描述使用動(dòng)態(tài)規(guī)劃算法，構(gòu)建一個(gè)二維數(shù)組dp，其中dp[i][j]表示第一個(gè)序列的前i個(gè)字符與第二個(gè)序列的前j個(gè)字符的最長(zhǎng)公共子序列長(zhǎng)度。通過(guò)狀態(tài)轉(zhuǎn)移方程dp[i][j]=dp[i-1][j-1]+1(ifs1[i]==s2[j])ormax(dp[i-1][j],dp[i][j-1])(ifs1[i]!=s2[j])來(lái)求解。求解方法貪心算法與分治策略07CATALOGUE貪心選擇性質(zhì)所求問(wèn)題的整體最優(yōu)解只由各個(gè)子問(wèn)題的局部最優(yōu)解組合得到，不需再考慮子問(wèn)題之間的關(guān)系。邊界貪心算法需要明確問(wèn)題的邊界，即問(wèn)題的約束條件，以保證貪心選擇的正確性。貪心策略根據(jù)問(wèn)題性質(zhì)，選擇當(dāng)前狀態(tài)下的最優(yōu)解，以期望達(dá)到全局最優(yōu)。貪心算法原理及思想通過(guò)貪心選擇結(jié)束時(shí)間最早的活動(dòng)，求解最多可進(jìn)行的活動(dòng)個(gè)數(shù)。活動(dòng)選擇問(wèn)題根據(jù)字符出現(xiàn)頻率構(gòu)建哈夫曼樹(shù)，實(shí)現(xiàn)最優(yōu)前綴編碼，達(dá)到壓縮數(shù)據(jù)的目的。哈夫曼編碼問(wèn)題利用Prim算法或Kruskal算法，根據(jù)邊的權(quán)值貪心選擇，構(gòu)建最小生成樹(shù)。最小生成樹(shù)問(wèn)題典型問(wèn)題分析與求解方法分而治之01將原問(wèn)題分解為若干個(gè)規(guī)模較小、結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題，遞歸解決子問(wèn)題，再合并子問(wèn)題的解決方案，從而達(dá)到解決原問(wèn)題的目的。分解與合并02分治策略的關(guān)鍵在于如何合理地將問(wèn)題分解為子問(wèn)題，以及如何將子問(wèn)題的解合并為原問(wèn)題的解。平衡子問(wèn)題03為保證分治策略的效率，需要盡量保證分解