演算法

①基本概念題(一切為了期末考試！)

.

1. 計算機求解問題的步驟：問題分析、數學模型建立、演算法設計與選擇、演算法的表示分析實作、編制結果檔案，
2. 演算法設計是解決問題的核心，
3. 演算法的定義：解決問題方法和步驟的描述是指令的有限序列，
4. 演算法三要素：控制結構、資料結構、操作，
5. 演算法的基本特征：有窮性、可行性、確定性、輸入、輸出
6. 評價演算法質量的指標：正確性、可讀性、健壯性、高效率與低存盤需求，
7. 演算法設計方法：結構化方法、面向物件方法
8. 表示演算法的方式：自然語言、盒圖、流程圖、PAD圖、偽代碼、計算機程式設計語言
9. 評價演算法的兩個方面：人對演算法維護的方便性、演算法運行時占用機器資源得多少（時間效率與空間效率），
10. 評價演算法的三個標準：演算法實作所耗費時間、所耗費空間（主要考慮輔助變數）、演算法應該易于理解易于編碼易于除錯，
11. 可以在多項式時間內解決的判定性問題叫P類問題，在多項式時間內可以驗證一個解是否正確的叫NP問題，

.
.
.
.
.
.

②遞回與遞推

--------------------------------------------------遞回演算法--------------------------------------------------

一、思想：自己呼叫自身函式的演算法，

二、特點：

（1）在使用遞回策略時，必須有一個明確的遞回結束條件，稱為遞回出口，

（2）在遞回呼叫的程序當中系統為每一層的回傳點、區域量等開辟了堆疊來存盤，遞回次數過多容易造成堆疊溢位等，所以一般不提倡用遞回演算法設計程式，

三、例題
（1）漢諾塔等

--------------------------------------------------遞推演算法-----------------------------------------------------

一、思想：即通過已知條件，利用特定關系得出中間推論，直至得到結果的演算法，

二、特點

（1）相對于遞回演算法,遞推演算法免除了資料進出堆疊的程序，也就是說,不需要函式不斷的向邊界值靠攏,而直接從邊界出發,直到求出函式值，

（2）順推法是從已知條件出發，逐步推算出要解決的問題的方法叫順推，

（3）逆推法從已知問題的結果出發，用迭代運算式逐步推算出問題的開始的條件，即順推法的逆程序，稱為逆推，

三、例題
（1）兔子生崽（斐波那契數列）

.-----------------------------------------------------------------------------------------------------------------------------------------------
.
.
.
.
.

③列舉法/蠻力法/窮舉法/暴力法

一、演算法思想：列舉所有可能的解，

二、特點（優劣）：

（1）程序簡單且得到的結果一定正確，

（2）可能做了很多的無用功，浪費時間空間，效率低，

三、列舉演算法解題的基本思路：

（1）確定列舉物件、范圍和判定條件，

（2）逐一列舉可能的解并驗證是否是問題的解，

四、列舉演算法步驟：

（1）確定解題的可能范圍，不能遺漏任何一個真正解，同時避免重復，

（2）判定是否是真正解的方法，

（3）為了提高解決問題的效率，使可能解的范圍將至最小，

五、例題

（1）百錢買百雞（偷懶不自己寫了） java版代碼

.
.
.
.
.

④回溯演算法/試探法

一、演算法思想：在問題的解空間樹中，按深度優先策略DFS，從根節點出發搜索解空間樹，演算法搜索至解空間樹的任一結點時，先判斷該結點是否包含問題的解，如果不包含，則跳過對以該結點為根的子樹的搜索，逐層向其祖先結點回溯，否則進入該子樹，繼續按深度優先策略搜索，

二、特點（優劣）：

（1）與深度優先演算法不同的是搜索程序伴隨著“剪枝操作”即當判斷當前節點下無所需解時不再向下搜索，節省了空間提高了效率，

（2）剪枝函式：為了避免無效搜索，提高回溯法的搜索效率而存在的函式，通常可以用兩種方式進行剪枝：

1. 用約束函式在擴展結點處減去不滿足約束條件的子樹，
2. 用限界函式減去得不到最優解的子樹，

（3）回溯演算法求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束，回溯法求問題的一個解時，只要搜索到問題的一個解就可結束，

（4）是一種一遍搜索一邊構造空間樹的演算法

（5）缺點是比較慢，遞回求解，排列樹思想要搜索出所有的解，類似于暴力求解，時間復雜度高，

//子集樹 時間復雜度 O(2^n)
void backtrack(int t) {
        if (t > n) {
            Output(x);
        } else {
            for (int i = 0; i <= 1; i++) {
                x[t] = i;
                if (constraint(t) && bound(t)) {    // 剪枝函式　　
                    backtrack(t + 1);
                }
            }
        }
    }


//排列樹 時間復雜度O(n!)
void backtrack(int t) {
        if (t > n) {
            Output(x);
        } else {
            for (int i = t; i <= n; i++) {
                swap(x[t], x[i]);
                if (constraint(t) && bound(t)) {     // 剪枝函式
                    backtrack(t + 1);
                }
                swap(x[t], x[i]);
            }
        }
    }

三、回溯演算法解決問題步驟：

（1）針對所給問題，定義問題的解空間（子集樹，排列樹），

（2）確定易于搜索的解空間結構，

（3）以深度優先方式搜索解空間，并在搜索程序中用剪枝函式避免無效搜索，

四、例題
（1）組合問題看看其他大佬的代碼吧哈哈
（2）皇后問題背包問題

.
.
.
.
.

⑤分治演算法

一、演算法思想：分而治之，把一個復雜的問題分成多個相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單地直接求解，原問題的解即子問題的解的合并，

二、特點（優劣）：

（1）往往伴隨著遞回的使用：分治與遞回經常同時應用在演算法設計中，

（2）可能做了很多的無用功，浪費時間空間，效率低，

（3）最優子結構性質：如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理），

（4）自底向上，各個子問題獨立

三、分治演算法步驟：

（1）分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題

（2）解決：若子問題規模較小而容易被解決則直接解，否則遞回地解各個子問題

（3）合并：將各個子問題的解合并為原問題的解

四、例題
（1）排序演算法(快速排序，歸并排序)
（2）二分搜索
（3）棋盤覆寫
（4）最接近點對問題
（5）回圈賽日程表
（6）漢諾塔
漫畫版學習分治演算法

.
.
.
.
.

⑥貪婪演算法

一、演算法思想：在對問題進行求解時，在每一步選擇中都采取最好或者最優(即最有利)的選擇，從而希望能夠導致結果是最好或者最優的

二、特點（優劣）：

（1）得到的結果是區域最優的，不一定是全域最優的，但結果都與最優解近似，

（2）每一步必須滿足以下條件：
　　1、可行的：即它必須滿足問題的約束，
　　2、區域最優：他是當前步驟中所有可行選擇中最佳的區域選擇，
　　3、不可更改：即選擇一旦做出，在演算法的后面步驟就不可改變了，
　　
（3）選擇的貪心策略必須具備無后效性，即某個狀態以后的程序不會影響以前的狀態，只與當前狀態有關，

三、貪婪演算法步驟：

（1）將最優化問題轉化為這樣的形式：對其做出一次選擇后，只剩下一個子問題需要求解，

（2）證明做出貪心選擇后，原問題總是存在最優解，即貪心演算法總是安全的，

（3）證明做出貪心選擇后，剩余的子問題滿足性質：其最優解與貪心選擇組合即可得到原問題的最優解，這樣就得到了最優子結構，

四、例題

（1）錢幣找零
（2）力扣分糖果
（3）背包問題

.
.
.
.
.

⑦動態規劃（演算法or思想）

一、演算法思想：將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的資訊，在求解任一子問題時，列出各種可能的區域解，通過決策保留那些有可能達到最優的區域解，丟棄其他區域解，依次解決各子問題，最后一個子問題就是初始問題的解，

二、特點（優劣）：

（1）最優子結構性質、重疊子結構、無后效性（“未來與過去無關”，這就是無后效性，）

（2）動態規劃其實就是有條件約束的遞推（更像是一種優化），

三、動態規劃步驟：

（1）描述優解的結構特征，
（2）遞回地定義一個最優解的值，
（3）自底向上計算一個最優解的值，
（4）從已計算的資訊中構造一個最優解，

四、例題
（1）01背包、子陣列和
（2）其他講解
————————————————————以上如有錯誤歡迎指正--------------------------------------------------------------