趣解数据结构与算法(一)——代码效率优化方法论


0x00.如何衡量程序运行的效率

在数据结构一定的情况下,我们以时间复杂度空间复杂度作为衡量程序运行效率的标准

  • 时间复杂度:算法执行步骤次数
  • 空间复杂度:算法执行辅助空间

0x01.数据结构教会了我们什么

不同的数据结构有自己不同的优劣,只有掌握足够多的经典数据结构,在实际应用生产中才能灵活运用各种数据结构来构建高效、健壮的应用程序。
我们不应当只执着于某一种进阶结构,程序使用数据结构时,永远讲究最合适和最高效。

0x02.复杂度分析

我们来学习时空复杂度的分析

为什么需要复杂度分析

资源路径有问题
事后统计法:人为分析程序效率

大O表示法

看两个示例,假设每条命令执行时间相同且为unit_time:
资源路径有问题

资源路径有问题

资源路径有问题

资源路径有问题

资源路径有问题

当你的算法输入n规模非常庞大的时候,低阶项、常量、系数对趋势的影响非常小,我们只需要关心复杂度的大致趋势即可,所以就可以忽略不重要的东西了。

时间复杂度分析方法

单段代码看高频:只关注循环执行次数最多的一段代码

示例:

1
2
3
4
sum=0; //1*unit_time
for(i=1;i<=n;i++){ //n*unit_time
sum=sum+(-1)^n; //n*unit_time
}

一共需要(2n+1)*unit_time

大O统计法:T(n)=O(2n+1)
求极限后(省去低阶项、常量、系数):T(n)=O(n)

多段代码取最大:总复杂度等于量级最大的那段代码的复杂度

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sum_1=0; 
for(p=1;p<=100;p++){
sum_1=sum_1+p;
}
sum_2=0;
for(q=1;q<=n;q++){
sum_2=sum_2+q;
}
sum_3=0;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
sum_3=sum_3+i*j;
}
}
return sum_1+sum_2+sum_3;

第一段:(1+100+100) *unit_time
第二段:(1+n+n) *unit_time
第三段:(2n^2+n+1) *unit_time
第三段>第二段>第一段

大O统计法:T(n)=O(2n^2+3n+1)
求极限后(省去低阶项、常量、系数):T(n)=O(n^2)

嵌套代码求乘积:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sub1
{
sum=0;
for(p=1;p<=n;p++){
sub 2
}
}
sub2
{
for(j=1;j<=n;j++){
for(k=1;k<=n;k++){
sum=sum+j;
}
}
}

sub1:(1+n+n *sub2) *unit_time
sub2:(n+n *n+n *n) *unit_time
则sub1嵌套后需要:(1+n+n^2+2 *n^3) *unit_time

大O统计法:T(n)=O(1+n+n^2+2 *n^3)
求极限后(省去低阶项、常量、系数):T(n)=O(n^3)

常见时间复杂度

资源路径有问题

  • 多项式量级就是这个时间复杂度是由n作为底数的,例如O(n) O(nlogn)
  • 非多项量级就是n不是作为底数,例如O(2^n) 指数阶级

时间复杂度为非多项式量级的算法问题叫做NP问题(Non-Deterministic Polynomial, 非确定多项式),非多项式量级的时间复杂度往往是计算机不能承受的(想想指数爆炸多么可怕~),当数据规模n越来越大时,非多项式量级的算法的执行时间会急剧增加,求解问题的执行时间会无限增长。所以,非多项式时间复杂度的算法其实是非常低效的算法。

O(1)

O(1)是常量级时间复杂度的一种表示方法,并不只是执行了一行代码,而是说算法的时间复杂度与问题规模n无关而已。

一般情况,只要算法中不存在循环语句、递归语句,即使成千上万行的代码,其时间复杂度也是O(1)

O(logn)/O(nlogn)

对数阶/线性对数阶时间复杂度非常常见,同时也是最难分析的一种时间复杂度
logn默认是以2为底数的
示例:

1
2
3
4
i=1;
while(i<=n){
i=i *2;
}

只考虑执行次数最多的第三行,i的取值是等比数列:2^0、2^1、2^2……2^k……2^i=n

故2^i=n,解i=log_2_n

对数之间还可以相互转换:log_3_n=log_3_2 *log_2_n,最后大O表示法:T(n)=O(logn)

如果一段代码的时间复杂度是O(logn),我们需要循环n遍,则时间复杂度就是O(nlogn),归并排序、快速排序的时间复杂度都是O(nlogn)

空间复杂度

空间复杂度全称是渐进空间复杂度(asymptotic space complexity)

表示算法的存储空间与数据规模之间的关系

1
2
3
4
5
6
7
8
int i=0;
int a=new int[n];
for(i;i<n;i++){
a[i]=i*i;
}
for(i=n-1;i>=0;i--){
print out a[i];
}

每行代码所需要的空间为unit_space
第一行:1 *unit_space
第二行:n *unit_space

最后一共就是(1+n) *unit_space

大O统计法:T(n)=O(1+n)
求极限后:T(n)=O(n)

常见的空间复杂度就是O(1)、O(n)、O(n^2)
像对数阶复杂度,例如O(logn),平时几乎用不到。

0x03.复杂度总结

资源路径有问题

0x04.时间复杂度的三种情况

上面我们已经基本了解了复杂度分析是咋样一回事,现在我们来进一步学习后面的内容

最好/坏情况时间复杂度

1
2
3
4
5
6
7
8
pos=-1
for(i=0;i<n;i++){
if(array[i]==x){
pos=i;
break;
}
}
return pos

上述代码意为在数组中查找某个数据的位置,找到返回数组下标并结束查找,没找到则返回-1

像这种情况,时间复杂度是不确定的,在区间[O(1),O(n)]
即最好的情况:T(n)=O(1)
最坏的情况:T(n)=O(n)

这就是最好/坏时间复杂度的分析

平均情况时间复杂度

1
2
3
4
5
6
7
8
pos=-1
for(i=0;i<n;i++){
if(array[i]==x){
pos=i;
break;
}
}
return pos

仍然是上面这个代码,这段代码执行,有n+1种情况(1到n是找到的情况,第n+1是没找到的情况)
每种情况需要遍历的次数累加,除以情况总数n+1,最后得到的就是遍历元素个数的平均值。

根据上述分析,可推导出来:(1+2+3+……+n+n)/(n+1)=[n(n+3)]/[2(n+1)]

忽略系数、常量,最后时间复杂度T(n)=O(n)

资源路径有问题

在大多数情况下,我们并不需要区分最好、最坏、平均情况时间复杂度三种情况,我们使用一个复杂度就可以满足需求了。
只有同一代码在不同的情况下,时间复杂度产生量级的差距,我们才会使用这三种复杂度表示法来区分。

欢迎请我喝奶茶(*゜ェ゜*)
---这篇文章到头了---感谢您的阅读-------------