这节课的主要知识就是讲诉了使用三种方法去求解递归式。

渐进记号

渐进记号主要有三种，具体定义参考课本。把渐进记号用来描述算法的运行时间。

Θ 记号(上界)

f(n) = Θ(g(n))使得存在正数常量c1、c2、n0,使得对所有 n≥n0,有0≤c1g(n) ≤ f(n)≤ c2g(n)

Ω 记号（下界）

f(n)=Ω(g(n)) 使得存在正数常量c和n0,使得对所有n≥n0有 0 ≤ cg(n) ≤ f(n).

O 记号

Θ记号渐进的给出一个函数的上界和下界，当只有一个渐进上界时，使用O记号。 f(n) = O(g(n)) 使得存在正数常量c,n0，使得对所有n≥n0,有0≤f(n)≤cg(n)

求解递归式

使用递归式来刻画分治算法的运行时间，如下三种方法便是学习如何求解递归式。 递归式如下：

替换法求解递归式

代入法求解递归式分两步： 1、猜测解的形式。需要靠经验，或者借助递归树来得出好的猜测。 2、归纳验证，求解常量。

递归树求解递归式

此方法参考课本内容。

主方法求解递归式

主方法定义了一个通用的递归式求解方法，如下

T(n) = aT(n/b) + f(n)

含义：它将规模为n的问题分解为a个子问题，每个子问题规模为n/b，其中a和b都是正常数，a个子问题递归地进行求解，每个话费时间T(n/b)。函数fn包含了问题分解和子问题解合并的代价。

主方法依赖下面的定理：令a>= 1和b>1是常数，fn是一个函数，Tn是定义在非负整数上的递归式： T(n) = aT(n/b) + f(n) Tn有如下渐进界：

• 1、若对某个常数ε>0有f(n)=O(nlogba–ε)则 T(n) = Θ(nlogba) .
• 2、若f(n) = Θ(nlogba)则T(n) = Θ(nlogba lgk+1n) .
• 3、若某个常数ε>0有f(n)=Ω(nlogba+ε)且对某个常数c<1和所有足够大的n有af(n/b) < cf(n) ,则T(n) = Θ( f (n) )

递归树的高度：h = logbn 叶子结点个数：l = nlogba