Master Method:
Def: T(n)=aT(b/n)+f(n) where a>=1 and b>=1 are constants
f(n) is asymptotically function.
此時間函數是 "divide and conquer" 策略下之產物(各個擊破)
ex.quick sort,recursive,merge sort...etc
a : 代表subproblems 之個數
b/n : 代表subproblems 之資料量
T(b/n) : 代表subproblems 之時間(成本)
f(n): 代表切割與合併的時間(成本)
Recursive Tree
Stack and Queue
(一)Stack
1.Def :具有LIFO性質的有序串列,其中插入元素的動作稱為push
刪除 pop
且push,pop的動作發生在同一端,稱為Top
2.應用 : p.3-3~p3-5 (背)
3.Stack 的ADT描述:
ADT: Abstract data Type (抽象資料型態)
DEF: 是一個Data Type 且滿足 the spec of data objects and the spec of operations are independent with the real representation of data objects and the implementation of operations.
Stack permutation
Def:給予n個data,依序執行push,但在過程中可穿插合法的pop輸出data,則可能的順序組合
ex. a,b,c之stack permutation
1.abc:push a ,pop ,push b ,pop ,push c ,pop
2.acb:push a ,pop ,push b ,push c ,pop ,pop
3.bac:push a ,push b ,pop ,pop ,psuh c ,pop
4.bca:push a ,push b ,pop ,push c ,pop ,pop
5.cab: X
6.cba:push a ,push b ,push c ,pop ,pop ,pop (這個地方蠻有趣的...科科)
Infix (中序式)
Postfix (後序式)
Prefix (前序式) 互相轉換要熟練
請先 登入 以發表留言。