小学生C++趣味编程训练营+第10课快慢知多少时间复杂度.pptx

第10课快慢知多少

——时间复杂度《小学生C++趣味编程训练营》

2时间复杂度目录21问题导入3试一试4动动脑

问题导入01

问题导入4编程中如何知道一个算法的快慢？先将算法用程序语言实现，然后把这个程序运行一遍，那么它所消耗的时间就自然而然知道了。尼克和格莱尔经常一起探讨编程问题，来看看他们现在正在探讨的话题吧！

问题导入5clock()是C++中的计时函数，这个函数返回从“开启这个程序进程”到“程序中调用clock()函数”时之间的CPU时钟计时单元数。CLOCKS_PER_SEC，用来表示一秒钟会有多少个时钟计时单元这种方法容易受到运行环境的影响，在性能高的机器上“跑”出来的结果与在性能低的机器上“跑”出来的结果相差很大，而且跟测试时使用的数据规模也有很大关系。

时间复杂度02

时间复杂度71、算法执行的策略2、问题的规模3、编写程序的语言4、编译产生的机器代码质量5、计算机执行指令的速度影响算法执行时间相关因素分析：不是针对实际执行的时间精确地算出算法执行具体时间，而是针对算法执行过程中某些“时间固定的基本操作语句”的执行次数做出估计，从而得出算法执行时间的信息。算法执行时间：一个算法的执行时间大致上等于其所有语句执行时间的总和。时间固定的基本操作：一般指的是在程序里嵌套层次最深，运行次数最多的语句。例如在未排序的数组中查找某个给定的值，如果将数组元素从头到尾依次与待查找的值相比较，那么这个“时间固定的基本操作”就是比较。与语言和机器有关

时间复杂度8算法1时间复杂度常用大写字母O和小写字母n表示，称为大O表示法，如O(n)、O(n2)。时间复杂度关注的是这个“时间固定的基本操作”被执行次数与n（数据规模）的关系，至于这个“时间固定的基本操作”每次执行需要多少时间并不关心。算法2执行n次执行1次用算法执行过程中某些“时间固定的基本操作”需要执行的次数和n（数据规模）的关系来度量算法的快慢。时间复杂度

时间复杂度9像这样“时间固定的基本操作”被执行次数为常量、与数据规模无关的算法，它的时间复杂度为O（1），常量级。时间固定的基本操作执行次数为3n的值无论是多少，都不会影响执行次数时间复杂度O（1）【例1】

时间复杂度10像这样“时间固定的基本操作”被执行的次数随着输入数据规模而发生线性变化的算法，它的时间复杂度为O（n），线性级。时间固定的基本操作执行次数为n时间复杂度O（n）【例2】n执行次数1110001000

时间复杂度11一般来说，标记算法的时间复杂度时不关心系数，所以它的时间复杂度也是O（n），线性级。时间固定的基本操作执行次数为2n时间复杂度O（n）【例3】

时间复杂度12在讨论某个算法的时间复杂度时，只关心随着n的增长而增长得最快的那一项（抓大去小）。此时，只关心n2项，忽略n+5项，它的时间复杂度为O（n2）。时间固定的基本操作时间复杂度O（n2）【例4】时间固定的基本操作执行n+5次执行n2次共执行n2+n+5次nn2n+511610010000105

时间复杂度13像这样的算法，它的时间复杂度是O(log2n)，但标记算法时间复杂度时不关心系数，它的时间复杂度为O（logn），对数阶。时间固定的基本操作时间复杂度O（logn）【例5】n执行次数42164102410nlog2n

14时间复杂度O（1）O（logn）O（n）O（n2）O（2n）O（nlogn）O（n!）O（n3）O（1）O（logn）O（n）O（nlogn）O（n2）O（n3）O（2n）O（n!）这四种时间复杂度究竟谁用时更长，谁节省时间呢？O（1）O（logn）O（n）O（n2）

试一试03

尼克认为，这也太简单了，只要用cout语句就能实现了。试一试16算法时间复杂度：O（n2）n=100000；运算次数为100000×100000，即100亿；超时从一般的经验来看，一个评测系统一秒能承受的运算次数大概是107～108，如果运算次数达到1亿这个量级就会比较危险，10亿肯定过不了，几千万有可能过，几百万肯定没有问题。

尼克认为，这也太简单了，只要用cout语句就能实现了。试一试17小实验输入下面的程序，并试着改变一下程序中的n值，看一看运行结果有没有变化？算法时间复杂度：O（n）

动动脑04

动动脑20【问题描述】一一对应第一行包含两个整数r和c（1≤r≤100，1≤c≤100），表示表格的行数和列数，中间用单个空格隔开。之后r行，每行上有c个整数n（1≤n≤105），表示第1个表格的各个单元格的数字，数与数之间以一个空格隔开。之后r行，每行上有c个整数n（1≤n≤105），表示第2个表格的各个单元格的数字，数与