2023算法與數(shù)據(jù)結構解析

算法與數(shù)據(jù)結構解析

算法基礎2023什么是算法算法的復雜度算法的分類一些經(jīng)典算法1234程序=數(shù)據(jù)結構+算法算法——大廠面試的必備主菜算法可以衡量程序員的技術功底算法可以體現(xiàn)程序員的學習能力和成長潛力學習算法有助于提高分析解決問題的能力學習算法是做性能優(yōu)化、成長為架構師的必經(jīng)之路為什么要學習算法前置知識熟練掌握一門編程語言，了解數(shù)據(jù)結構相關知識分類學習按照數(shù)據(jù)結構、應用場景、實現(xiàn)策略學習算法的捷徑——刷題題目來源：LeetCode怎樣學習算法算法（Algorithm）

——解決問題的步驟和方法算法，是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機制。也就是說，能夠對一定規(guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。什么是算法有窮性（Finiteness）算法必須能在執(zhí)行有限個步驟之后終止；確切性（Definiteness）

算法的每一步驟必須有確切的定義；輸入項（Input）一個算法有0個或多個輸入，以描述運算對象的初始情況輸出項（Output）一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結果可行性（Effectiveness）算法中每個計算步驟都可以在有限時間內(nèi)完成（也稱之為有效性）算法的特性如何分析算法的優(yōu)劣求和：1+2+3+...+100時間復雜度執(zhí)行算法所需要的計算工作量空間復雜度算法需要消耗的內(nèi)存空間算法的復雜度我們考慮的問題不同的機器，計算速度不同如果我們的計算機無限快，那只要確定算法能夠終止就可以，所有算法性能沒有比較的必要了如果輸入數(shù)據(jù)量很小，那一般機器也都可以在非常短的時間內(nèi)完成，算法性能也沒有必要比較了計算資源有限，輸入數(shù)據(jù)量很大的情況下，不同算法耗費的時間差異極大基本指令——程序執(zhí)行消耗的時間單位算術指令、數(shù)據(jù)移動指令、控制指令inta=1；運行時間1if(a>1){}運行時間1for(inti=0;i<N;i++){System.out.println(i);}運行時間3N+2算法的時間復雜度不同的算法，運行時間T(n)隨著輸入規(guī)模n的增長速度，是不同的inta=1;

a=2;

a=3;for(inti=0;i<n;i++){

for(intj=0;j<n;j++)

System.out.println(“test");

}for(inti=0;i<n;i++){

System.out.println(“test");

}T(n)=3T(n)=3n+2T(n)=3n2+4n+2時間復雜度T(n)=0.5n2

T(n)=3n+2T(n)=3n+2T(n)=4nT(n)=3nT(n)=O(n)T(n)=O(n2)T(n)=3n2+4n+2T(n)=3n2T(n)=4n2復雜度的大O表示法對于給定的函數(shù)g(n)，用O(g(n))來表示以下函數(shù)的集合：O(g(n))={f(n):存在正常量c和n0，使對所有n≥n0

，有0≤f(n)≤cg(n)}算法分析中，一般用大O符號來表示函數(shù)的漸進上界這表示，當數(shù)據(jù)量達到一定程度時，g(n)的增長速度不會超過O(g(n))限定的范圍復雜度的大O表示法

常見的算法復雜度算法執(zhí)行所占用的空間Array[100]：O(100)Array[N]：O(N)intval=1;空間復雜度O(1)有時候遞歸調(diào)用，需要計算調(diào)用棧所占用的空間空間復雜度搜索算法排序算法字符串算法圖算法最優(yōu)化算法數(shù)學算法按照應用目的按照應用目的暴力法增量法分治法貪心算法動態(tài)規(guī)劃法回溯法分支限界法按照實現(xiàn)策略算法的分類分而治之問題的規(guī)模越小，越容易解決把復雜問題不斷分成多個相同或相似的子問題，直到每個子問題可以簡單地進行求解將所有子問題的解合并起來，就是原問題的解分治和遞歸產(chǎn)生的子問題形式往往和原問題相同，只是原問題的較小規(guī)模表達使用遞歸手段求解子問題，可以很容易地將子問題的解合并，得到原問題的解分治算法基本步驟step1：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題step2：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題step3：將各個子問題的解合并為原問題的解應用場景二分搜索、大整數(shù)乘法、歸并排序、快速排序棋盤覆蓋問題、循環(huán)賽日程表問題、漢諾塔問題等分治算法貪心（Greedy）——總是做出在當前看來是最好的選擇不從整體考慮，只考慮眼前，得到局部最優(yōu)解局部最優(yōu)解和全局最優(yōu)解要保證最終得到的是全局最優(yōu)解，貪心策略必須具備無后效性適用場景用貪心算法直接求解全局最優(yōu)，條件比較苛刻哈夫曼（Huffman）編碼貪心算法

具體實現(xiàn)框架

從問題的某一初始解出發(fā)；

while（能朝給定總目標前進一步）

{

利用可行的決策，求出可行解的一個解元素；

}

由所有解元素組合成問題的一個可行解；貪心算法動態(tài)決策的過程把原問題劃分成多個“階段”，依次來做“決策”，得到當前的局部解每次決策依賴于當前的“狀態(tài)”，隨即引起狀態(tài)的轉移一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的這種多階段決策最優(yōu)化，解決問題的過程就稱為動態(tài)規(guī)劃最優(yōu)化問題動態(tài)規(guī)劃通常用來求解最優(yōu)化問題可以有很多可行解，每個解都對應一個值，我們希望找到具有最優(yōu)值的解動態(tài)規(guī)劃決策1決策2決策n初始狀態(tài)狀態(tài)1狀態(tài)2狀態(tài)n-1結束狀態(tài)階段1階段2階段n…………決策序列應用場景最優(yōu)二叉搜索樹、最長公共子序列、背包問題等等動態(tài)規(guī)劃選優(yōu)搜索法按照一定的選優(yōu)條件，不停向前搜索，直到達到目標如果搜索到某一步，發(fā)現(xiàn)之前的選擇并不優(yōu)，就退回一步重新選擇通用解題方法深度優(yōu)先搜索（DFS）策略在包含問題所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結點出發(fā)、深度搜索解空間樹回溯法就是對隱式圖的深度優(yōu)先搜索算法回溯法廣度優(yōu)先搜索（BFS）策略所謂“分支”，就是采用廣度優(yōu)先的策略，依次搜索當前節(jié)點的所有分支拋棄不滿足約束條件的相鄰節(jié)點，其余節(jié)點加入“活節(jié)點表”然后從表中選擇一個節(jié)點作為下一個擴展節(jié)點，繼續(xù)搜索限界策略為了加速搜索的進程，一般會在每一個活節(jié)點處，計算一個函數(shù)值根據(jù)這些已計算出的函數(shù)值，從當前活節(jié)點表中選擇一個最有利的節(jié)點作為擴展節(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解分支限界法回溯法分支限界法對解空間樹的搜索方式DFSBFS存儲節(jié)點常用數(shù)據(jù)結構堆棧隊列應用場景找出滿足約束條件的所有解；找出全局