CS 341 Algorithm 复习小记
Author: 咳嗽di小鱼 Date: December 15, 2011 Category: Sum Up 1 Comment
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) <= 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.