Python Algorithms - C3 Counting 101

Python算法设计篇(3) Chapter 3: Counting 101

The greatest shortcoming of the human race is our inability to understand the exponential function. —— Dr. Albert A. Bartlett, World Population Balance Board of Advisors

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

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

1.代换法

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

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

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

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

2.递归树法

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

3.主定理法

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

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

返回Python数据结构与算法设计篇目录

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏有趣的Python和你

Python数据分析之锁具装箱问题问题重述问题分析建模与求解

11730
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet系列 之 随机选择

  平日工作学习时总会遇到一些令人欣喜的代码段子(Snippet),虽然都很短小,但是其间所含的道理都颇有意味,遂而觉得应该不时的将她们记下,一来算作复习整理,...

11920
来自专栏章鱼的慢慢技术路

笔试常考题型之时间复杂度

15930
来自专栏大数据风控

R中如何用ifelse进行数据分组

数据分组,根据数据分析对象的特征,按照一定的数值指标,把数据分析对象划分为不同的区间部分来研究,以揭示内在的联系和规律性; 在R中,我们常用ifelse函数来进...

33380
来自专栏章鱼的慢慢技术路

笔试常考题型之时间复杂度

52560
来自专栏CSDN技术头条

程序员必须知道的十大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较...

21150
来自专栏编程之旅

数据结构——最小生成树(C++和Java实现)

快要一整个月没有更新博客了,之前的几周每周都想着要写,但是最后时间还是排不开,最近的状态是一直在写代码,一直在怼工作的需求,顺便刷刷算法题,国庆则是没心没肺的玩...

36240
来自专栏潇涧技术专栏

Problem: Delete Number Problem

这题可以使用贪心策略,每次从高位向低位数,删除高位比低位数字小的那位上的数字,直到删除了k位之后,得到的数字肯定是最大值。

9320
来自专栏老九学堂

程序员必须知道的十大基础实用算法及讲解!

最近社群很多的小伙伴们对算法进行了激烈的讨论与学习,今天老九君就给大家介绍一些编程语言里的基础算法,提高小伙伴们的算法知识及编程里对算法的运用。 我们一起来看看...

36850
来自专栏智能算法

程序员必须知道的十大基础实用算法及其讲解

出自博客园 原文地址:http://kb.cnblogs.com/page/210687/ 算法一:快速排序算法   快速排序是由东尼·霍尔所发展的一种排序算法...

38480

扫码关注云+社区

领取腾讯云代金券