0主定理求递归公式.pdf

2013/4/14 递归关系（Recurrence Relations ） 算法设计与分析  Recurrence relations describe functions Algorithms Design Analysis over the natural numbers.(递归关系描述 的是自然数上的函数关系) 第三讲：递归关系  They express the value of a function for a given integer n0 as functions of the values of the function for arguments less than n.(对于某个n0 的 函数值，通过小于n的函数值表示出来) 1 递归实例(Recurrence Examples) 为什么要分析递归关系？  The running times of many algorithms (especially recursive algorithms) are easily expressed using recurrence relations。(许多算法，特别是递归算法，时间开  0 n 0  0 n 0 销函数都可以用递归关系来描述） s(n)  s(n)  c s(n 1) n 0 n s(n 1) n 0  We need to solve them, that is, derive closed   expressions of the functions expressed by recurrences using O-, Ω-,