Insertion Sort(插入排序)
array的排序方式
假設arry[8,2,4,9,3,6]
j以2為開始
第一步找到合適插入位置
移動2
為[2,8,4,9,3,6]
移動4
[2,4,8,9,3,6]
移動9但發現已比8大
所以不動
移動3
[2,3,4,8,9,6]
移動6
[2,3,4,6,8,9]
算法分析
A.Running time
(1)資料狀況
例:是否有經過排序
如果已經是排序過狀況
例如8,9
代表時間花費會很少
從大到小(逆序)
時間會花費最多因為需從頭比較
(2)資料規模
例子只需處理6個元素
但如果處理六十億?
解決方式:參數化
(3)所需計算時間上限
例:程式運行時間
用戶承諾
B.kind of analys
最壞情況
T(n)輸入規模為n時最長的運行時間
平均時間
T(n)輸入規模為n時所有可能下的期望時間
期望值=所有輸入時間總和求加權平均
C.插入排序最壞情況?
(1)計算機能力
64 bit V.S. 32 bit
相對速度
絕對速度
D. BIG IDEA(大局觀)
漸近分析
(1)忽略依賴機器的常量
(2)不關心運行時間但關注運行時間的增長
使用漸近符號
θ
例:n³-3n²+2=θ(n³)
你要理解當n無窮大時
θ(n²)的算法運行時間會比θ(n³)算法少
E.回到插入排序
T(n)=Σθ(j) n j=2(因第一個不用比較)
可以簡化成θ(n²) 算術級數:1+2+3+4+....
如何更快?
Merge Sort(合併排序)
沿用上例將資料分成
[1...n/2]和[n/2-1....n]
再合併排序
關鍵在Merge
[2,7,13,20]
[1,9,11,12]
比較兩數列最小值
得1再看2,9
得2再看7,9
得7再看13,9
[1,2,7...]
運行時間T(n)=θ(n) 簡稱線性時間
分析
-----------------------
T(n) | A[1..n]
θ(1) | n=1 ,完成
2T(n/2) | [1...n/2]和[n/2-1....n]
θ(n) | 合併
T(n)=
if n=1,θ(1) (通常省略)
if n>1,2T(n/2) +θ(n)
遞迴解法
T(n)=2T(n/2) +cn (c>0) cn取代θ(n)
T(n)= cn
T(n/2) T(n/2)
= cn
cn/2 cn/2
T(n/4) T(n/4) T(n/4) T(n/4)
逐漸遞迴得到二叉樹
直到最底層
θ(1)
問這個二叉樹多高?
log n 指的是log(2)n
問這個二叉樹節點數是多少?
n
第一層花多少時間?cn
第二層花多少時間?cn
.
.
.
.
最後一層花多少時間?θ(n)
T(n)=cn*log n +θ(n) (常數項可以捨去)
=θ(nlog n)
θ(nlog n)運行時間又比θ(n²) 少
參考補充:
漸進符號
插入排序
達人
