当前位置 博文首页 > 柠檬树:数据结构与算法之美——复杂度分析——学习笔记
一、前言
? ? ? ?只要讲到数据结构与算法,就一定离不开时间、空间复杂度分析。可以说,复杂度分析是整个算法学习的精髓,只要掌握了它,只要掌握了复杂度分析,数据结构与算法的内容基本上就掌握了一半。
二、为什么需要复杂度分析
? ? ? ?俗话说,实践是检验真理的唯一标准,那么把代码跑一遍,通过统计、监控、就能得到算法执行的时间和占用的内存大小。这个方法叫做事后统计法。为什么还要做时间、空间复杂度分析呢?因为事后统计法存在非常大的局限性。
? ? ? ?1、测试结果非常依赖测试环境
? ? ? ?同一段代码在不同硬件环境下的执行速度显然不一致。
? ? ? ?2、测试结果受数据规模的影响很大
? ? ? ?对于大规模的数据而言,快速排序比插入排序要快得多。但是对于小规模的数据,插入排序反而比快速排序快。
? ? ? ?所以,我们需要一个不用具体的测试数据来测试,就可以粗略地估计算法的执行效率的方法。也就是我们所讲的时间、空间复杂度分析方法。
三、大O复杂度表示法
? ? ? ?求1,2,3...n的累加和,现在估算这段代码的执行时间?
int cal(int n){
int sum = 0;
int i = 1;
for(; i<=n; i+1){
sum = sum +1;
}
return sum;
}
? ? ?假设每行代码执行时间都一样,为unit_time。在这个假设之上,这段代码的执行时间是多少?
? ? ?第2、3行代码分别需要1个unit_time的执行时间,第4、5行都运行了n遍,所以需要2n*unit_time的执行时间。所以这段代码总的执行时间就是(2n+2)*unit_time。可以看出,所有代码的执行时间T(n)与每行代码的执行次数成正比。
? ? ?按照这个思路,我们来看下面的代码。估算执行时间?
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
? ? ? ?第2、3、4行,每行需要1个unit_time的执行时间,第5、6行代码循环执行了n遍,需要2n*unit_time的执行时间,第7、8行代码循环执行了n2遍,所以需要2n2*unit_time。所以这段代码的执行时间为(2n2+2n+3)*unit_time。
? ? ? ?通过这两段代码的推导过程,我们可以得到一个非常重要的规律,那就是,所有代码的执行时间T(n)与每行代码的执行次数n成正比。总结成公式为:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? T(n) = O(f(n))
? ? ? 解释如下:
? ? ? T(n):代表代码的执行时间
? ? ? n:表示数据规模的大小
? ? ? f(n):每行代码执行次数的总和,因为这是一个公式,所以用f(n)来表示。
? ? ? O:表示代码的执行时间T(n)与f(n)成正比。
? ? ?所以,第一个例子T(n)=O(2n+2),第二个例子T(n)=O(2n2+2n+3),这就是大O时间复杂度表示法。
? ? ?大O时间复杂度表示法实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势。所以也叫渐进时间复杂度,简称时间复杂度。
? ? ?由于公式中的低阶、常量、系数三部分并不左右增长趋势,所以可以忽略。只需要最大量级。因此例1和例2可以表示为
? ? ?T(n)=O(n);T(n)=O(n2)
四、时间复杂度分析
? ? ? ?1、单段代码看高频:比如循环
? ? ? ?2、多端代码取最大:比如一段代码中有单循环和多重循环那么取多重循环的复杂度。
? ? ? ?3、嵌套代码求乘积:比如递归、多重循环等
? ? ? ?4、多个规模求假发:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。
五、常见复杂度案例分析
? ? ? ? ?
? ? ? ? 常见的复杂度并不多,从低阶到高阶有:O(1)、O(logn)、O(n)、O(nlogn)、O(n2)。
? ? ? ? ?1、O(1)
? ? ? O(1)只是常量级时间复杂度的一种表示方法,并不是指只执行了一行代码。比如这段代码,即使只有3行,它的时间复杂度也是O(1),而不是O(3)。
int i = 8;
int j = 6;
int sum = i + j;
? ? ? ?只要代码的执行时间不随n的增大而增大,时间复杂度为O(1)。一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是O(1)。
? ? ? 2、O(logn)、O(nlogn)
? ? ? ?对数阶时间复杂度非常常见,同时也是难分析的一种时间复杂度。我通过一个例子来说明一下。
i=1;
while (i <= n) {
i = i * 2;
}
? ? ? 这3行代码是循环次数最多的,所以,我们只要能计算出这行代码执行了多少次,就能知道整段代码的时间复杂度。
? ? ? 从代码可以看出,变量从1开始取,每循环一次乘以2.当大于n时,循环结束。变量i的取值就是一个等比数列。
? ? ??
所以x=log?n。所以这段代码的时间复杂度就是O(log?n)。在采用大O标记复杂度时,可以忽略系数,因此,在对数阶时间复杂度统一表示为O(lonn)
? ? ? 按照乘法法则,如果时间复杂度O(nlogn)表明一段代码的时间复杂度是O(logn),我们循环执行n遍,时间复杂度就是O(logn)。而且O(nlogn)也是一种非常常见的算法时间复杂度。比如,归并排序、快速排序的时间复杂度都是O(nlogn)。
? ? ?3、O(m+n)、O(m*n)
? ? ?再来讲一种跟前面都不一样的时间时间复杂度,代码的复杂度由两个数据的规模来决定。
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
? ? ? ?m和n是表示两个数据规模。我们无法评估m和n谁的量级大,所以不能套用加法法则,所以时间复杂度为O(m+n)
五、最好、最坏、平均、均摊情况时间复杂度
? ? ? ?最好情况时间复杂度:在理想的情况下,执行这段代码的时间复杂度
? ? ? ?最坏情况时间复杂度:在最糟糕的情况下,执行这段代码的时间复杂度
? ? ? ?平均情况时间复杂度:也叫加权平均值,也叫期望值,
? ? ? ?均摊时间复杂度:? ?摊还分析法:通过摊还分析得到的时间复杂度我们起了一个名字,叫均摊时间复杂度。均摊时间复杂度就是一种特殊的平均时间复杂度。
?
? ? ? ?
cs