Python算法:Counting 101

本网站用的阿里云ECS,推荐大家用。自己搞个学习研究也不错
原文出处: hujiawei (@五道口宅男)   

原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法

因为本节内容都很简单,所以我只是浏览了一下,重要的只有计算算法的运行时间的三种方法:1.代换法; 2.递归树法; 3.主定理法。

1.代换法

代换法一般是先猜测解的形式,然后用数学归纳法来证明它

下面是算法导论中的一个求解例子

有意思的是,还有一类问题可以通过变量替换变成容易求解的形式

下面是常用的一些递归式以及它们对应的结果还有实际算法实例

2.递归树法

这种方法就是通过画递归树,然后对每层进行求和,最后将每层的结果相加得到对总的算法运行时间的估计

3.主定理法

这种方法大家最喜欢,给出了一种就像是公式一样的结论,虽然它没有覆盖所有的情况,而且证明非常复杂,但是很多情况下都是可以直接使用的,还有,需要注意主定理的不同情况下的条件,尤其是多项式大于和多项式小于!


不喜欢本节的可以跳过,不留练习了这次,嘿嘿,想练习的话刷算法导论的题目吧

1 赞
1 收藏

评论





转载自演道,想查看更及时的互联网产品技术热点文章请点击http://go2live.cn

未经允许不得转载:演道网 » Python算法:Counting 101

赞 (0)
分享到:更多 ()

评论 0

评论前必须登录!

登陆 注册