T(n) = T(n/2) + O(1)
T(n) = 2T(n/2) + O(n)
T(n) = a*T(n/b) + f(n), a >=1 , b >=1
c = ㏒b(a) [h]
- f(n) = O(nc-ͼ), then T(n) = θ(n2) for ͼ>0
- f(n) = θ(nc㏒kn), k>=0, then T(n) θ(nc㏒k+1n)
- f(n) = Ω(nc+ͼ), then T(n) = θ(f(n)) for ͼ>0
Note: k must >= 0 and f(n) must be positive.
- amount to change
- denominations: 1, 4 & 6
k is the first k denomiation.
x is the amount need to change.
dx is the lagest denomination in k.
- c[k, 0] = 0 #1row
- c[d1, x] = x #1col
- c[k, x] = c[k-1, x] if x < dx
- c[k, x] = min(1 + c[k, x-dx], c[k-1, x])
Time: O(n, m)
w is the item weight, k is the first k denomiation, v is the item biggest value in k,
- opt[k, w] = 0, if k = 0 or w = 0
- opt[k, w] = opt[k-1, w], can not take, if w < dw
- opt[k, w] = max(v + opt[k-1, w-dw], opt[k-1, w])
i, j is number of order letter in two sequence
- LCS[i, 0] = LCS[0, j] = 0
- LCS[i, j] = 1 + LCS[i-1, j-1], if S[i] = T[j]
- LCS[i, j] = max(LCS[i-1, j], LCS[i, j-1]), if S[i] != T[j]
Only half table is needed but that way we can not reconstruct the solution.
- Sort edge with weights - O(E×㏒E)
- Choose all minimum weight edges
- Grow the forest / repeat cycle detection for each edge - O(V)
Time: O(V×E + E×㏒E)
Build a tree one vertex at a time.
- Start with a arbitrary vertex
- Expand vertex checking the minimum weight dege
- Update distances from adjacent vertices
- Grow the tree
findMin/deleteMin - O(V) V times
update - O(1) E times
Total = O(V2 + E)
deleteMin - O(㏒V) V times
update(decreaseKey) - O(㏒V) E times
Total = O(V㏒V + E㏒V)
deleteMin - O(㏒V) V times
update(decreaseKey) - O(1) E times
Total = O(V㏒V + E)
Not work when having negative cycle.
- Dijkstra for get minimum path cost from source to all other
- Prim for get the MST
- Dijkstra you can go from the selected node to any other with the minimum cost, you don’t get this with Prim’s source
- UCS is only stop at when reach the goal status, similar with the Dijkstra.
Maintaining a array of vertices: Total = O(V2 + E) -> O(V2)
Maintaining a binary heap(PQ - Priority Queues) of vertices: Total = O(V㏒V + E㏒V) -> O(E㏒V)
LAZIEST| Maintaining a Fibonacci heap: Total = O(V㏒V + E)
- Topological -> linear
- Check edge -> linear
- Case 1: Path uses at most k-1 edges: D[v, k] = D[v, k-1]
- Case 2: Path uses at most k edges: D[v, k] = min(D[w, k-1] + c(wv))
for k = 1 ...V -1 do //detect negative change to 1 to V
- Do not stop after V-1 iteration. If anything changes, there is negative.
Time: O(VE * V) / Time: O(VE) in SSSP
for k = 1 ...V do
- Check diagonal in table, if have negative then have find the negative cycyle.
Bellman-Ford: O(VE * V)
Dijikstra(Fibonacci): O(V(V㏒V + E))
- FW is same BF for running, but implement is easy
- Dijikstra is fater but not work in negative.