目录
渐近记号
O记号
渐近上界记号O (大O)
渐近地给出了一个函数在常量因子内的上界:
O(g(n)) = { f(n) : 存在正常量c和n0，使得对所有n ≥ n0，有0 ≤ f(n) ≤ cg(n)}
f(n) = Θ(g(n))蕴含着f(n) = O (g(n))
O可用于标识最坏情况运行时间
Ω记号
渐近下界记号Ω (大Ω)
渐近地给出了一个函数在常量因子内的下界:
Ω(g(n)) = { f(n) :存在正常量 c 和 n0，使得对所有 n>= n0，有 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }
f(n) = Ω(g(n))蕴含着f(n) = Ω(g(n))
Ω可用于标识最佳情况运行时间
Θ记号
渐近紧确界记号Θ
渐近地给出了一个函数的上界和下界:
Θ(g(n)) = { f(n) : 存在正常量c1, c2和n0，使得对所有n ≥ n0，有0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)}
分治策略
三个步骤：
- 分解
将问题划分为若干个子问题 - 求解
递归地解这些子问题；若子问题Size足够小，则直接解决之 - 组合
将子问题的解结合成原问题的解
分治算法的效率分析
一个递归式是一个函数，它由一个或多个基本情况（base case），它自身，以及小参数组成。
递归式的解可以用来近似算法的运行时间。
迭代法求运行时间
递归树法求运行时间
主定理法求运行时间
该方法可解如下形式的递归式
T(n) = aT(n/b) + f(n)
其中 a >=1 和 b >1 是两个常数, f(n) 是一个渐进非负函数（当n趋于无穷时， f(n) 是非负的. 如果 n/b 不是整数, 取整 n/b
主方法可解包含三种类型 f(n) 的递归式 T(n)
关键是看 f(n) 和 nlogba 谁比较大。
