數組求和-疊代
**時間複雜度一知半解，繼續學習 **
int Sum(int A[],int n){
int sum=0; //O(1)
for(int i = 0;i < n; i++){ //O(n)
sum += A[i]; //O(1)
}
return sum; //O(1)
}
時間複雜度：O(n)
空間複雜度：計算除輸入外，循環中需要的空間，在此包括累加器sum和内部循環的控制變量i，是以空間複雜度為O(2)
減而治之政策
思想：将n看作疊代的規模，循環每經過一次疊代，尚未參與統計的元素個數，即剩餘的有效問題的規模就遞減一個元素，這種不斷蠶食，削弱有效問題規模的大小，稱為減而治之政策。
數組求和-線性遞歸 / 遞歸跟蹤
int Sum(int A[],int n){
return n < 1 ? 0 : Sum(A,n-1) + A[n-1];
//A[n-1]為平凡的問題，sum(A,n-1)為更小規模的問題
}
時間複雜度：遞歸執行個體sum(A,n-1)可以忽視掉，因為本身消耗為O(1)，可以歸納到它所調用的遞歸執行個體中。是以計算其複雜度，即O(1) * (n + 1)；也就是漸近的O(n)；
每一個遞歸執行個體隻會生成一個遞歸執行個體，可以組成線性次序，稱為線性遞歸。簡單直覺，隻适用于簡單的遞歸模式。
“遞歸基”是遞歸函數的一種平凡情況，隻有有遞歸基，遞歸才不會一直進行下去。
遞歸方程：
将規模為n的問題，劃分為規模為n-1的縮減問題，與O(1)的平凡問題之和。
數組倒置-遞歸
void reserve( int * A ; int lo ; int hi){
if( lo < hi){
swap( A[lo] , A[hi] );
reserve(A; lo + 1; hi -1);
}
else {
}
}
思想：
-疊代原始版：
void reserve( int * A ; int lo ; int hi){
if( lo < hi){ //判斷遞歸基
swap( A[lo] , A[hi] );
lo++;
hi--;
goto next;
}
else {
}
}
-疊代精簡版：
while(lo < hi){
swap(A[lo ++] ;A[hi--]);
}
分而治之政策
數組求和-二分遞歸
int Sum(int A[],int lo; int hi){
if(lo = hi)
{
return A[lo];
}
int mid = (lo + hi) >> 1;
return Sum(A. lo, mid) + Sum(A, mid + 1; hi);
}
時間複雜度：T(n) = O(1)*n = O(n)
數組中最大的兩個整數值，要求元素比較的次數盡可能少
雙指針思想
指定兩個指針存儲最大值及次大值索引，疊代數組，先于次大值x2比較，再與最大值x1比較
比較次數：最好情況 1+(n-2)*1 = n-1
最壞情況 1+(n-2)*2 = 2n-3
public int[] max2(int A[],int lo,int hi)
{
int x1 = lo,x2 = lo +1; //初始化x1,x2;x1存儲最大值，x2存儲次大值
if(A[x1 = lo] < A[x2 = lo +1])
{
int i = x1;
x1 =x2 ;
x2 = i;
}
//從lo+2即第三個元素開始比較，先與x2次大值比較，在于最大值比較
for(int i=lo + 2;i < hi;i++)
{
if(A[i] > A[x2]) {
x2 = i;
if(A[i]>A[x1])
{
x1 = i;
}
}
}
int [] Res = {A[x1],A[x2]};
return A[x2];
}
遞歸的分而治之政策求兩個最大值
将數組分為左右部分，分别求出最大值和次大值，再将兩個最大值進行比較求出整體最大值，将次大值與較小最大值比較得出次大值。
動态規劃
在效率上講，遞歸并不總是能讓我們滿意。
動态規劃：通過遞歸找到問題的本質，并給出初步的解之後，再将其等效的轉化為疊代的形式。
Fib()函數
1、遞歸思想
當計算不超過100項時，計算時間就已經超過了三生三世，是以算法雖然在邏輯上沒有問題，但是在計算時間上存在問題。
分析低效率原因：各遞歸執行個體被重複多次的調用
2、解決思路：令每一個遞歸執行個體隻計算一次，先檢查是否已經對此進行過計算，若計算過則直接取值，進而減少計算次數。
解決方法A（記憶）:将已計算過結果的執行個體制表備查；空間複雜度為O(n)
解決方法B（動态規劃）:颠倒計算方向，由自頂而下遞歸改為自下而上疊代。
int g = 1, f = o; //f(1)和f(0)
while(o < n--)
{
g = g + f;
f = g - f;
}
return g;
複雜度分析：時間複雜度與n有關，為O(n)；空間複雜度隻占用了g和f兩個存儲空間，即兩個常數複雜度O(1)
最長公共子序列LCS
兩個序列公共子序列中的最長者
遞歸求解：
1、通過序列長度确定遞歸基；
2、減而治之政策：首先對末端字元比較，若相等，則去除末端，變成更小規模的子問題與平凡問題。
3、分而治之政策：若末端字元不相等，則分為兩種情況，去除任一序列的末端字元與另一完整序列繼續比較。
複雜度分析：每經過一次對比，原問題規模減一，即至少一個序列的長度減一。
最好的情況是隻出現減而治之，則複雜度為O(n+m)
最壞情況如下，出現大量重複的子問題，複雜度為O(2n)
引入動态規劃：消除重複計算，提高效率