# 某储备粮的“学习笔记”

by 咳嗽di小鱼

## Master Theorem

``````T(n) = a * T(n / b) + f(n)
x    = log_b(a)
T(n) = θ(n^x)          if f(n) = O(n^(x-ε))
θ(n^x * lg(n))  if f(n) = θ(n^x)
θ(f(n))         if f(n) = Ω(n^(x+ε))
and a * f(n/b) &lt;= c * f(n)
``````

## Greedy

• At each step, make the "best" next choice.
• Never backtrack or change past choices.
• Never look ahead to see if this choice has negative consequences.

### Greedy Proof, Type 1

1. Describe a greedy local choice strategy
2. Setup the configurations of the greedy solution G and the optimal solution O
3. Argue that O can become G by replacing each entry in O
For each replacement, show it is possible, because it consist the compatibilty and optimality The last two step involves induction
• In basecase, focusing on how the first greedy choice can be used in an optimal solution
• During induction,
assume the first k choices in an optimal solution are made by the greedy algorithm, show that the k+1 choice can be made by the greedy algorithm as well

### Greedy Proof, Type 2

1. Describe a greedy local choice strategy
2. Setup the configurations of the greedy solution G and the optimal solution O
3. Find out the difference between O and G
4. Try to reorder O to G and consists the optimality

## Dynamic Programming

Dynamic Programming calculates a solution based on the result of a previous calculation. It saves the previous result so that no duplicate calculation needed. Dynamic Programming Design Recipe

1. Find out the subproblem

• give a score evaluation function
• give a recursive difinition
2. State how an array can be used to evaluate the scores

• dimension
• evaluation order
• basecase
• final result
3. How to recover the solution

## Graph

### Representations of Graphs

• Pointers

• vertices have pointers to adjacent vertices
• Cannot determine whether an edge exists directly

• A matrix M, M[i, j] = 1 iff exists edge from i to j
• waste a lot of space

1. 吉他 