文章详情

  • 游戏榜单
  • 软件榜单
关闭导航
热搜榜
热门下载
热门标签
php爱好者> php文档>算法效率分析

算法效率分析

时间:2011-06-08  来源:brokencode


参考  第二章  算法效率分析基础


2.1  分析框架

输入规模,运行时间,增长次数,最优最差平均效率


2.2  基本符号和效率类型

一张图,注意一般的效率类型都是什么情况





2.3  非递归算法的效率分析


很直观--

找到基本操作

建立基本操作执行次数的求和表达式



2.4  递归算法的效率分析


不那么直观,得看递归的深度

对算法基本操作的执行次数,建立一个递推关系式以及相应的初试条件

解递推关系式(跟高中数列的递推关系式差不多)

举了2个例子,

阶乘递归实现---基本操作的递推关系式

汉诺塔---基本操作的递推关系式

很重要!一定要会建立递推关系式和解递推关系式



2.5  一个例子  斐波那契数列

定义就不用详细说了:



由这个式子:


根据数学知识,解特征方程可以直接得到第n个斐波那契数:




其实我都忘了怎么解特征方程什么的,但大概还记得是那么回事。介绍了这么多高数里面的东西,主要是要说明,这个有2个好处:

1)它快速的告诉了我们斐波拉契数的增长速度,是呈指数增长的!!!

2)由F(n)的表达式可以知道,被减去的那一部分在0到-1之间,事实上,对任意n,




有了上面这些,相信对斐波拉契数列应该有了更深一步的认识。

归于正题,在计算机中怎么去求第n个斐波拉契数,最直接的办法也许会写成这样:



没有任何优化,直接根据递归的定义把上面都交给了计算机。

这里存在着大量的重复计算!!!!

这个例子可以很好的说明动态规划的思想,事实上,只需要记录连续2个f的值就可以迭代的求到F(n),它的复杂度是线性的。




总结:

1)表2.2  常见的时间复杂度一般是怎么产生的

2)非递归和递归的效率分析,递归算法的复杂度是通过递推的关系式的建立来解出来的

3)斐波拉契数列的特征,优化来获得线性的时间复杂度


相关阅读 更多 +
排行榜 更多 +
哥布林弹球b服手游下载

哥布林弹球b服手游下载

休闲益智 下载
小马样式盒游戏下载

小马样式盒游戏下载

休闲益智 下载
异变小镇中文版下载安装

异变小镇中文版下载安装

冒险解谜 下载