Pages

Friday, March 26, 2010

Algorithm lecture 2

這一章節主要先以之前所學過的insertion sort當例子。開始解說如何分析一個程式的演算法。

首先,先從分析迴圈開始。initialization, maintenance, termination。三個部分構成一個迴圈。

以一個for迴圈為例:

for(j = 2 to A.length)
key = A[j]
i = j-1

Initialization: j等於2是否小於A這個陣列的長度。是第一次跑這迴圈。

Maintenance:每做一次迴圈,迴圈都會指向下一個陣列。

Termination:當A[j]超過陣列長度時會終止這個迴圈。

分析一個程式分析他的best case, worst case, average case。程式在執行的時候,當然有很多因素在影響。包括電腦的硬體,輸入的值...等等。worst case顧名思義,也就是說一個upper bound on the running time。而average case也往往跟worst case 的結果是一樣的。

設計一個演算法。這章節先大概介紹divide and conque。簡單的概念是把大問題劃分成小問題。解決小問題當然比大問題還簡單。等都解決之後再把結果湊起來,而大問題的解答也因此拼起來了。本章節是以merge sort來做範例說明。

最後用tree的概念。大致分析merge sort。(附在我下面的筆記)





0 comments:

Post a Comment

 
Copyright (c) 2010 All About Icelorc. Design by WPThemes Expert

Themes By Buy My Themes and Web Design.