递归方程复杂度计算公式推导_算法时间复杂度分析中递归方程求解方法综述

- 60- 中国科技信息2006年第3期 CHINA SCIENCE AND TECHNOLOGY INFORMATION Feb.2006 科 技 论 坛 }} }} 引言 在计算机科学中，递归概念经常用于递归调用方面，即函数或过程自己调用自己。用递归调用的算法就是递归算法，递归调用会产生无终止运算的可能性，因此必须在适当的情况下终止递归调用。 计算机算法分析中所需要的资源数量，经常以和的形式或递归公式的形式表示。绝大部分算法的执行，都表现为按某种条件，重复地执行一些循环，而这些循环，又经常可以用递归关系来表达。这就使得递归方程的求解，对算法分析来说，变得非常重要。 1，时间复杂度分析与递归方程算法时间复杂性度量常借助于循环次数的统计、基本操作频率的统计、计算步的统计等来分析。以分治法解最大最小问题为例，问题描述如下：企业老板有一袋金块，要从中挑选最重的一块给他的优秀员工，挑选最轻的一块给他的一位一般员工。该问题可以转换成在一个具有n个元素的数组里，寻找关键字最大、最小的元素问题。其实现代码如下： 输入：整数数组A[]，数组的起始边界和结束边界low和high；输出：最大元素e_max和 最小元素e_min。 void maxmin(int A[],int &e_max,&e_min, int low,int high){ int mid,x1,y1,x2,y2; if ((high-low)<=1){ if (A[high]>A[low]){ e_max=A[high]; e_min=A[low]; } else { e_max=A[low]; e_min=A[high]; else { mid=(low+high)/2; maxmin(A,x1,y1,low,mid); maxmin(A,x2,y2,mid+1,high); e_max=max(x1,x2);e_min=min(y1,y2); 令C (n )表示算法对n 个元素的数组所执行的比较次数，将比较操作看作基本操作，以此来度量该算法的时间复杂度。可以列出如下的递归方程： 2，生成函数求解递归方程 定义1 令a 0，a 1，a 2，⋯是一个实数序列，构造如下的函数： 算法时间复杂度分析中递归方程求解方法综述 胡章平 王瑞胡 重庆文理学院数学与计算机科学系 402160 摘 要：算法分析中计算复杂性常用递归关系来表达，递归方程的求解有助于分析算法设计的好坏。常用的递归方程的求解方法包括生成函数法、特征方程法、递推法等。递归树方法和主方法给出了递归方程计算复杂度的渐进表示。 关键词：生成函数；特征方程；递推；递归树；主方法 [中图分类号]TP301.6 [文献标识码]A 则函数G(z)称为序列a0，a1，a2，⋯的生 成函数。 菲波那契序列问题：假设小兔子每隔一个月长成大兔子，大兔子每隔一个月生一只小兔子。第一个月有一只小兔子，求n 个月后有多 少只兔子？ 令t(n)、T(n)分别表示第n 个月小兔子、大兔子的数目，f(n)为第n个月兔子的总数目， 则有如下关系式： T(n) = T(n-1) + t(n-1) t (n) = T(n-1) f(n) = T(n) + t(n) 由上述三式可以得到如下递归方程： 用f(n)作为系数，构造一个生成函数F(x): 可求得F(x)-xF(x)-x2F(x)=x，即 3，特征方程求解递归方程除了利用生成函数求解递归方程外，还可利用递归方程的特征方程来求解。 3.1 k阶常系数线性齐次递归方程定义2 形如 称上式为递归方程的特征方程。 可以求出特征

最后

以上就是斯文黑猫为你收集整理的递归方程复杂度计算公式推导_算法时间复杂度分析中递归方程求解方法综述的全部内容，希望文章能够帮你解决递归方程复杂度计算公式推导_算法时间复杂度分析中递归方程求解方法综述所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。