Chapter2: 時(shí)間復(fù)雜度分析、遞歸、查找與排序
1. 遞歸
1. 什么是遞歸
表現(xiàn)：
在函數(shù)內(nèi)部調(diào)用函數(shù)本身
應(yīng)用遞歸的問題特征：
一個(gè)問題能夠劃分為更小規(guī)模的子問題求解笔喉，通過求解更小規(guī)模的子問題最終得到問題的答案铝耻。更具體地來說祠汇，即在本次函數(shù)調(diào)用中執(zhí)行一小部分任務(wù)，然后傳遞一個(gè)變化了的參數(shù)蛋褥，調(diào)用該函數(shù)本身執(zhí)行接下來的任務(wù)。
組成：
- 函數(shù)內(nèi)的自我調(diào)用
- 出口條件
設(shè)計(jì)經(jīng)驗(yàn)：
找重復(fù)(子問題)
找重復(fù)中的變化量（參數(shù)）
-
找參數(shù)的變化趨勢(shì)和邊界(出口)
注意設(shè)計(jì)遞歸時(shí)睛驳，變化趨勢(shì)是大問題 >> 小問題烙心，函數(shù)執(zhí)行時(shí)，變化趨勢(shì)是解決小問題 >> 解決大問題
練習(xí)策略：
- 循環(huán)改遞歸
- 了解經(jīng)典遞歸
- 大量聯(lián)系乏沸，總結(jié)規(guī)律淫茵，掌握套路
- 找到感覺，挑戰(zhàn)更高難度的遞歸(深度優(yōu)先蹬跃、廣度優(yōu)先等)
2. 簡(jiǎn)單的遞歸問題示例
2.1 單分支遞歸
使用遞歸求階乘
設(shè)計(jì)思路：
- 找重復(fù): n! = n * (n-1)!, 求 (n-1)! 是原問題的重復(fù)(規(guī)模更小)
- 找變化: 變化的量應(yīng)該作為參數(shù)
- 找邊界: 即出口痘昌，n>=1
代碼：
int f(int n){
if(n==1){
return 1;
}
return n*f(n-1);
}
打印 [ i , j ] 之間的整數(shù)
即打印 i, i+1 ,..., j
當(dāng)然這個(gè)用一個(gè)循環(huán)就能解決，這里主要是為了講解遞歸的規(guī)律
設(shè)計(jì)思路:
- 找重復(fù): 每次都是打印操作
- 找變化: 第一次執(zhí)行打印
i, 第二次執(zhí)行打印i+1,..., 直至i>j - 找邊界: 即出口，從i開始辆苔，到j(luò)結(jié)束
代碼:
void printItoJ(int i,int j){
if(i<j){
return;
}
printf("%d ",i);
printItoJ(i+1);
}
數(shù)組求和
- 找重復(fù): 實(shí)際上是不斷地執(zhí)行求和操作
- 找變化: 前邊的求和結(jié)果+下一個(gè)數(shù)算灸，下一個(gè)數(shù)的下標(biāo)在遞增
- 找邊界: 直至數(shù)組最后一個(gè)元素，即
i==arr.length-1為最后一次加法
求數(shù)組第 i 個(gè)元素到最后一個(gè)元素的和
int sumArray(int[] arr,int i){
if(i==arr.length){
return 0;
}
return arr[i]+sumArray[i+1]驻啤；
}
遞歸求最大公約數(shù)(輾轉(zhuǎn)相除法)
int gcd(int a,int b){
if(a%b==0){
return b;
}
return gcd(b,a%b);
}
遞歸進(jìn)行插入排序
插入排序原理示意
- 從第一個(gè)元素開始菲驴，該元素可以認(rèn)為已經(jīng)被排序
- 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素骑冗，將該元素移到下一位置
- 重復(fù)步驟 3赊瞬，直到找到小于或等于新元素的已排序的元素
- 將新元素插入到該元素的位置后
- 重復(fù)步驟 2~5
非遞歸的插入排序?qū)崿F(xiàn)
以從小到大的排序?yàn)槔?/p>
就是不斷把新元素與已排序元素從右到左進(jìn)行比較
- 如果新元素比已排序元素大就不用挪動(dòng)
- 如果新元素比已排序元素小
- 將該新元素用
tmp變量保存 - 將已排序元素挨個(gè)往后挪，直至新元素比已排序元素大贼涩，將新元素插入到該元素后
- 將該新元素用
/*按從小到大的插入排序巧涧，非遞歸 */
/*
C++中數(shù)組作為函數(shù)參數(shù)是傳址
*/
void insSort(int arr[],int arrLen){
//int arrLen = sizeof(arr)/sizeof(arr[0]); 不能在這里計(jì)算數(shù)組元素個(gè)數(shù)，因?yàn)閭魅氲牟皇菙?shù)組而是其地址
for(int i=1;i<arrLen;i++){//第一個(gè)元素當(dāng)作已排列序列遥倦，從第二個(gè)元素開始排列
int tmp=arr[i];//未排序的最靠左的元素
int j=i-1;//已排序元的最靠后素的下標(biāo)
while(j>=0 && tmp<arr[j]){//當(dāng)新元素<已排序元素時(shí)谤绳，已排序元素挨個(gè)往后挪
arr[j+1]=arr[j];
j--;
}
arr[j+1]=tmp;//插入新元素
}
//輸出排序后的數(shù)組
for(int i=0;i<arrLen;i++){
printf("%d ",arr[i]);
}
printf("\n");
}
遞歸的插入排序
問題的解決思路：
- 找重復(fù)：實(shí)質(zhì)就是 "新元素與已排序元素的比較，并在滿足條件的情況進(jìn)行按個(gè)的元素挪動(dòng)再插入新元素" 這一過程的不斷重復(fù)袒哥，隨著已排序元素?cái)?shù)量的增多缩筛，問題規(guī)模是在增大的。
- 找變化：?jiǎn)栴}中每一次排序后堡称，已排序元素?cái)?shù)量+1
- 找邊界：當(dāng)已排序元素等于數(shù)組元素時(shí)結(jié)束
然而設(shè)計(jì)遞歸問題時(shí)瞎抛，函數(shù)的調(diào)用方向應(yīng)該是問題規(guī)模不斷變小的，這樣函數(shù)執(zhí)行時(shí)才是 解決小問題>>解決大問題 的方向,這一點(diǎn)需要注意却紧。
遞歸形式的解決思路
- 找重復(fù)：對(duì)
N個(gè)元素進(jìn)行插入排序桐臊，可以分解為對(duì)N-1個(gè)元素進(jìn)行插入排序的結(jié)果與最后一個(gè)數(shù)進(jìn)行排序 - 找變化：不斷深入遞歸，問題規(guī)模減小晓殊，層次越深断凶，插入排序函數(shù)的參數(shù)越小
- 找邊界：直到下標(biāo)為0時(shí)，不需要再進(jìn)行插入排序挺物，到達(dá)邊界懒浮，函數(shù)返回
代碼
void insSort2(int* arr,int i){
if(i==0){//第1(下標(biāo)為0)個(gè)元素插入排序的結(jié)果
return;
}
insSort2(arr,i-1);//第i個(gè)元素的插入排序需要第i-1個(gè)元素的插入排序的結(jié)果
/*進(jìn)行第i個(gè)元素的插入排序*/
int tmp=arr[i];//保存未排序的新元素
int j=i-1;//最靠右的已排序元素的下標(biāo)
while(j>=0 && tmp<arr[j]){//當(dāng)新元素小于已排序元素時(shí)，不斷將已排序元素挨個(gè)往后挪
arr[j+1]=arr[j];
j--;
}
arr[j+1]=tmp;//插入新元素
}
2.2 多分支遞歸
求斐波那契亞數(shù)列第N項(xiàng)
斐波那契亞數(shù)列
第n項(xiàng)=第n-1項(xiàng)+第n-2項(xiàng)
int fib(int n){
if(n==1||n==2){
return 1;
}
return fib(n-1)+fib(n-2);
}
發(fā)現(xiàn)多分支遞歸會(huì)有很多重復(fù)項(xiàng)识藤，可以進(jìn)行優(yōu)化砚著，之后討論相關(guān)內(nèi)容
參考資料
[2] 插入排序圖文講解
[3] 2.1-2.5 遞歸與排序解法
