递推方程的实例(续) 例3哪种排序算法在最坏情况下复杂度比较低? 插入排序、归并排序 插入排序 W(n)=W(n-1)+n-1 W(1)=0 解得W(n)=On 归并排序,不妨设n=2k W(n)=2W(m/2)+n-1 W(1)=0 解得Wn)=O( nlogn)
6 例 3 哪种排序算法在最坏情况下复杂度比较低？ 插入排序、归并排序 插入排序 W(n) = W(n −1) + n −1 W(1) = 0 解得 W(n) = O(n2). 归并排序，不妨设 n = 2k. W(n) = 2W(n/2) + n－1 W(1) = 0 解得 W(n) = O(nlogn) 递推方程的实例（续）
常系数线性齐次递推方程求解 常系数线性齐次递推方程的定义 H(m)-a1H(n-1)-a2H(n-2)-…-akH(n-k)=0 lH(0)=b,H()=b,H(2)=b2…,H(k-1)=b 其中a1,a2…,ak为常数,ak≠0 称为k阶常系数线性齐次递推方程 b,b1,…,bk1为k个初值 实例: fibonacci数列的递推方程
7 常系数线性齐次递推方程的定义 = = = − = − − − − − − − = 0 1 2 − 1 1 2 ( 0 ) , ( 1 ) , ( 2 ) , ... , ( 1 ) ( ) ( 1 ) ( 2 ) ... ( ) 0 k k H b H b H b H k b H n a H n a H n a H n k 其中 a 1 , a 2,…, a k为常数， a k ≠ 0 称为 k 阶常系数线性齐次递推方程 b 0, b 1, …, b k-1 为 k 个初值 实例：Fibonacci 数列的递推方程 常系数线性齐次递推方程求解
常系数线性齐次递推方程的公式解法 特征方程、特征根 ■递推方程的解与特征根的关系 ■解的线性性质 无重根下通解的结构 ■求解实例 ■有重根下通解结构 求解实例
8 常系数线性齐次递推方程的公式解法 特征方程、特征根 递推方程的解与特征根的关系 解的线性性质 无重根下通解的结构 求解实例 有重根下通解结构 求解实例
特征方程与特征根 H(m)-a1H(n-1)-a2H(n-2) H(n-k)=0 H(0)=b0,H(1)=b1,H(2)=b2,…,H(k-1)=bk-1 特征方程x-a1x1 ak 0 特征方程的根称为递推方程的特征根 实例 递推方程fn=fn1+fm2 特征方程x2x1=0 特征根 +√51-√5 2 2
9 特征方程与特征根 = = = − = − − − − − − − = 0 1 2 − 1 1 2 ( 0 ) , ( 1 ) , ( 2 ) , ... , ( 1 ) ( ) ( 1 ) ( 2 ) ... ( ) 0 k k H b H b H b H k b H n a H n a H n a H n k 特征方程 xk − a 1 xk-1 − … − a k = 0， 特征方程的根称为递推方程的特征根 实例 递推方程 fn = fn-1 + fn-2 特征方程 x 2 −x−1= 0 特征根 2 1 5 , 2 1 + 5 −
递推方程解与特征根的关系 定理1q是非零复数,则q是递推方程的解 兮q是它的特征根 证:q是递推方程的解 n-2 n-k 分q-1q-m2q 0 n-k, k -1 -2 兮q(q-01q 2 k)=0 -2 分q-1q k=0 台q是它的特征根
10 定理 1 q 是非零复数，则 qn是递推方程的解 ⇔ q 是它的特征根 证： qn是递推方程的解 ⇔ q n −a1q n-1 − a2q n-2 − … − akq n-k = 0 ⇔ q n-k(qk −a1qk-1− a2qk-2 − …− ak) = 0 ⇔ q k − a1q k-1 − a2q k-2 − … − ak = 0 ⇔ q 是它的特征根 递推方程解与特征根的关系