Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithm (Divide-and-Conquer (邏輯 (Divide (將原問題拆解成小問題), Combine…
Algorithm
Divide-and-Conquer
The selection Problem(Kth small)
O(n)
prune-and-search
Merge Sort
O(nlogn)
The closest pair Problem
O(nlogn)
The maximun subarray problem
Divide-and-conquer
O(nlogn)
Dynamic Programming
O(n)
邏輯
Divide
將原問題拆解成小問題
Combine
將子問題的解合併成原問題的解
Conquer
遞迴解各個子問題,當子問題購小時則直接解
matirx multiplication
n的log7次方
Dynamic Programming
Divide and Conquer + Memoizatio
http://www.csie.ntnu.edu.tw/~u91029/DynamicProgramming.html
Step
確認每個問題需要哪些子問題來計算答案。（recurrence）
確認總共有哪些問題。（state space）
把問題一一對應到表格。（lookup table）
決定問題的計算順序。（computational sequence）
確認初始值、計算範圍。（initial states / boundary）
implementation
Top-down
Bottom-up
asymptotic notation
BigO
Theta
LittleO
Omega