一、補充：遞回相關知識
1.1 遞回定義
? 程式呼叫自身的編程技巧稱為遞回（ recursion），
1.2 斐波那鍥數列
0 1 1 2 3 5 8 13 21 34 .......
fi??(??) ::= ??????(?? ? 1) + ??????(?? ? 2), ?? > 1
| 1 ,?? = 1
| 0 ,?? = 0
int Fib(n)
{
if(n<=1)
return n;
else
return Fib(n-1)+Fib(n-2);
}
二、演算法的基本概念
2.1 定義
? 演算法是對特定問題求解步驟的一種描述，是指令的有限序列
2.2 演算法的五個基本特征
| 有窮性：演算法運行的步數是有限的，運行的時間也是有限的 |
| 確定性：對同一輸入每次都有相同的輸出 |
| 可行性：演算法中描述的操作都是可以通過已實作的基本運算執行有限次實作 |
| 輸入：有0個或多個輸入 |
| 輸出：有1個或多個輸出 |
三、好的演算法應考慮的目標
| 正確性：演算法能正確的解決問題 |
| 可讀性：演算法應具有良好的可讀性，以便于人們理解 |
| 健壯性：也稱魯棒性，當輸入非法資料時演算法也能適當做出反應或進行處理 |
| 效率：演算法執行的時間盡可能短 |
| 低存盤：演算法執行程序中所需要的最大存盤空間應盡可能小 |
四、演算法的效率度量：時間復雜度和空間復雜度
4.1 時間復雜度
? 一個陳述句的頻度指陳述句在演算法中被重復執行的次數
? 演算法中所有陳述句的頻度之和記作T(n)
? 時間復雜度主要分析T(n)的數量級
? 通常采用演算法中基本運算的頻度f(n)來分析演算法的時間復雜度
? T(n) = O(f(n)
4.2 空間復雜度
? 演算法所耗費的存盤空間g(n)
? 它是問題規模n的函式，記為S(n)
? S(n) = O(g(n))
4.3 注意
注意：演算法原地作業指演算法所需輔助空間是常量，即S(n) = O(1)
4.4 非遞回程式的時間復雜度分析
計算陳述句頻度之和f(n)
4.5 遞回程式的時間復雜度分析
分治法主定理：T(n) = aT(n/b)+f(n)，n為問題規模，a>=1和b>1是常量，f(n)是遞回以外的計算時間
| 若f(n) = O(??^logb^(?????))對于某個?? >0成立，那么T(n) = O(??^log??^??) |
| 若f(n) = O(??log??^??)，那么T(n) = O(??^log??^?? * logn) |
| 若f(n) = O(??log??^(??+??))對于某個?? >0成立，并且af(n/b)≤cf(n),對于某個常量c<1(n足夠大)成立，那么T(n) = O(f(n)) |
//no1
理解：比較f(n)與??^log??^??的大小
誰大T(n)就取它,相等時T(n) = O(??^log??^?? * logn)
T(n) = aT(n/b)+f(n)
T(n/b) = aT(n/??^2)+f(n/b)
T(n) = a[ aT(n/??^2)+f(n/b) ]+f(n)
=??2T(n/??^2)+af(n/b)+f(n)
//no2
例子：迭代運算式T(n) = 3T(n/2)+n^2
決議：
1.驗證是否滿足主定理
2.驗證滿足哪種情況
3.根據主定理求解
該迭代式滿足主方法
比較f(n)與??^log??^??的大小有n^log2^3 < ??^2
滿足情況第三種且3(??^2)/4 < ????^2
故T(n) = O(??^2)
【例子】（2012華中科技大學887）漢諾塔問題
假定move()的時間復雜度為O(1),則下列演算法的時間復雜度是 （ ）
void hanoi(int n,char x,char y,char z)
{
if(n==1)
move(x,1,z);
else
{
hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,x,z,y);
}
}
4.5 常見的時間復雜度
常數階O(1)<對數階O(logn)<線性階O(n)<線性對數階O(nlogn)<平方階O(n2)<方階O(n3)<k次方階O(nk)<指數階O(2n)<O(n!)<O(n^n)
查看更多
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/75843.html
標籤：其他
上一篇：資料結構導論之第二章(線性表)
下一篇：五大常見演算法策略之——回溯策略