数据结构——算法效率_数据结构比较函数增速

作者：小小林熬夜学编程 | 2024-04-14 15:43:44

踩

数据结构比较函数增速

算法效率的度量

1.度量

算法采用的策略、方案
编译产生的代码质量
问题的输入规模
机器执行指令的速度

2.算法

算法效率研究的是算法随着输入规模扩大增长量的一个抽象，不是精准的执行多少次

2.1函数的渐进增长

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YLkxLjrl-1646382391396)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220304143605835.png)]$

对于两个函数f(n)g(n)，当有一个整数N，n>N时，f(n)>g(n)，我们就说在n以后f(n)的增长率比g(n)大

最高次项越大的函数，随着n增长，结果也会增长特别快

结论:判断一个算法的效率时，我们通常去判断它的最高次项，一般忽略次要项，项前数字也可以忽视

2.2算法时间复杂度与空间复杂度

定义：在计算分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示岁问题规模n的增大，算法执行时间的增长率和f（n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度，其中f(n)是问题规模n的某个函数。

三个求和算法 1 n n^2

求O阶

1.所有的常数用1代替
2.如果最高阶存在且不是1，则去除这个项前的常数
3.得到的结果就是O
1
2
3

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DBUmcEUp-1646382353371)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220304145356622.png)]$

对于此函数
每次函数都是i*2后在进行比较，所以假设有x个2相乘运行次数n=x*2
i=log(2)n
O(log(n))
1
2
3
4

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RFxyNCd6-1646382353371)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220304145549409.png)]$

O(n)

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IJ7nLYBn-1646382353371)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220304145633054.png)]$

O(n^2)

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1nlv1Pld-1646382443439)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220304145656971.png)]$

O(n^3)

常用的时间复杂度耗费的时间从小到大:

O(1)<O(logn)<O(n)<O(n^2)<O(n3)<O(2^n)<O(n!)<O(nn)

时间复杂度来指运行时间的需求，空间复杂度来指空间的需求

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/422857