15 數據結構及算法應用
15.1 算法策略區分
15.1.1、分治法
????????特征:把一個問題拆分成多個小規模的相同子問題，一般可用遞歸解決。
????????經典問題:斐波那契數列、歸并排序、快速排序、矩陣乘法、二分搜索、大整數乘法、漢諾塔。
15.1.2、貪心法
(一般用于求滿意解)???????
????????特征:局部最優，但整體不見得最優。每步有明確的，既定的策略。
????????經典問題:背包問題(如裝箱)、多機調度、找零錢問題。
15.1.3、動態規劃法
(用于求最優解)--“最優子結構”和遞歸式????
????????特征:劃分子問題，并把子問題結果使用數組存儲，利用查詢子問題結果構造最終問題結果。(一般自頂向下時間復雜度為O(2^n)，自底向上時間復雜度為O(n^a)效率更高)
????????經典問題:斐波那契數列、矩陣乘法、背包問題、LCS最長公共子序列
15.1.4、回溯法
????????特征:系統的搜索一個問題的所有解或任一解。
????????經典問題:N皇后問題、迷宮、背包問題
15.1.5 特征總結
?
算法策略判斷:
????????1、回溯，大家比較熟悉，有嘗試探索和回退的過程。這個比較好識別。????????2、分治，分治與動態規劃法其實最難區分，分治不好解決問題，從而記錄中間解解決問題，有了動態規劃法，但是在軟設考試中，分治目前只有二分的思想，二分以外的思想都用動態規劃法解決了。二分的時間復雜度，與O(
)相關，注意有沒有外層嵌套循環。(結合歸并排序、快速排序的過程，也是二分的)
????????3、動態規劃法，有遞歸式，經常考查遞歸式，此時自底向上實現時，中間解基本上是查表可得的，所以時間復雜度一般是O(n^k)，具體k是多少，根據for循環的嵌套。此時循環變量能夠看到，是從0或1開始，到n結束，這種情況就是從小規模到大規模，自底向上的。如果用到自頂向下，其實跟分治的實現就差不多了，查表的意義基本上可以忽略不計了，時間復雜度為O(2^n)，遞歸的變量一般由n開始，向1縮小，所以是大規模到小規模，也就是自頂向下的。(一般動態規劃法涉及遞歸式，遞歸式還會經常用在代碼填空中讓大家補充缺失的填空，然后會有“最優子結構”的描述，會有表(數組)記錄中間解。)
????????4、貪心法，有時候也會出現“最優子結構”的描述，但是沒有遞歸式。考慮的是當前最優，求得的是滿意解。(特殊情況下，貪心法有時候得到的也可以是最優解，比如部分背包問題)?
15.2 時間復雜度與空間復雜度
????????時間復雜度是指程序運行從開始到結束所需要的時間。通常分析時間復雜度的方法是從算法中選取一種對于所研究的問題來說是基本運算的操作，以該操作重復執行的次數作為算法的時間度量。
常見的對算法執行所需時間的度量:????????
????????空間復雜度是指對一個算法在運行過程中臨時占用存儲空間大小的度量。一個算法的空間復雜度只考慮在運行過程中為局部變量分配的存儲空間的大小
15.3 代碼填空技巧
仔細審題:
????????1、檢查所有用到的變量是否有聲明，是否賦初值;
????????2、檢查是否有返回值，與題干要求返回變量名或上下文是否一致;????????3、檢查for循環是否有計數變量的賦值、初值和終止條件;
????????4、注意while循環的開始和結束;????????5、有一些變量名具有特殊含義，比如一般用max/min保存最大值/最小值，temp作為中間變量，一般用來存儲中間值或用來做數值交換的中間過渡。x>max，則修正max=x
x<min，則修正min=x。????????6、對特殊的算法策略:回溯法是否有回退k=k-1;對分治法遞歸的遞歸調用(調用自身函數名);對動態規劃法的查表操作。
????????7、注意題干描述和代碼說明、遞歸式(條件和等式)、代碼中的注釋、代碼上下文。一般特殊數據結構調用方式會在代碼說明或代碼上下文中給出。????????(1)題干公式很重要，一般公式體現在代碼中，會有循環邊界、判斷條件等;
????????(2)代碼說明很重要，一般代碼說明會指出一些變量的定義，初始值和邊界值;
????????(3)代碼上下文很重要，可以根據上下文判斷有沒有缺失變量聲明、變量賦值;
????????(4)題干說明很重要，題干有時候也會給出循環邊界、判斷條件等內容，還可以根據題干描述，判斷使用的算法策略，不同的算法策略，一般會有一些典型的代碼缺失，比如:動態規劃法可能會考查題干給出的遞歸式以及最優解的判斷，分治法一般也會考查到遞歸式以及問題的劃分，貪心法一般會考查滿意解的當前最優判斷條件，回溯法一般會考查找和回退的過程。
