时间复杂度与空间复杂度剖析

访客4年前黑客文章1107

作为开发人员,我们都希望在完成功效的基础上让代码运行的更快、更省空间,那若何权衡编写的代码是否更有效率,这就需要我们学会若何剖析代码时间复杂度和空间复杂度.


什么是复杂度剖析

执行时间和占用空间是代码性能的2个评判尺度,我们划分用时间复杂度和空间复杂度去形貌这2个尺度,二者统称复杂度,复杂度形貌的是算法执行时间(或占用空间)随数据规模的增进关系.


为什么需要复杂度剖析

有人可能想问我代码运行一下不就知道他执行多长时间了吗,为什么还需要复杂度剖析,确实你能够通过这种方式评估出代码的执行效率,然则这样会有一些局限性.

1.测试效果太过于依赖测试环境
统一段代码在差别处理器的机械上运行效果是显然不一样的,这时就不知道应该参考哪个测试效果.
2.测试效果受到数据规模的影响很大
两段差别的代码在数据量比较小的时刻可能相差甚微,无法真实反映代码的性能问题.

以是我们需要一个不依赖测试环境同时也不需要有详细的测试数据就能大略的估量代码的执行效率的方式,也就是复杂度剖析.


若何举行复杂度剖析

大O复杂度示意法
先看一段代码,求1,2,3...n的累加和

int calc(int n) {
  int sum = 0;  //之一行
  for(int i = 1; i <=n; i++) {
    sum = sum + i;
  }
  return sum;
}

我们来评估一下这段代码的执行时间,假设每行执行的时间一样,为row_time.第1行需要一个row_time的执行时间,第2,3行划分执行了n次,以是需要2n*row_time的执行时间,以是这段代码加起来总共的执行时间为(2n+1)*row_time,虽然我们并不知道row_time的详细时间,但我们发现代码的总执行时间T(n)与代码的执行次数n成正比.我们可以用公式来示意

T(n) = O(f(n))

T(n)代表代码的总执行时间,f(n)代表代码的执行次数,O代表T(n)与f(n)成正比.以是上面的例子中,T(n) = O(2n+1),我们可以看出大O时间复杂度示意代码执行时间随数据规模的转变趋势,我们简称为时间复杂度.

当n很大时,公式中的常量,系数都可以忽略不计,并不会对转变趋势有太大影响,我们只需记下一个更大量级即可,那么刚刚的例子最后就可以记为T(n) = O(n)

那以后的代码若何去剖析其时间复杂度呢,我们有以下规则:
1.看代码执行次数最多的一段,好比循环
2.多段代码取更大量级,好比单循环和多重循环,应取多重循环的复杂度
3.嵌套代码复杂度即是嵌套内外代码复杂度的乘积,好比递归和多重循环等

平时我们有一些常用的复杂度级别,好比O(1) (常数阶)、O(logn) (对数阶)、O(n) (线性阶)、O(nlogn) (线性对数阶)、O(n²) (平方阶)

领会了时间复杂度,那么空间复杂度也不难理解了,时间复杂度示意的是算法执行时间随数据规模增进的转变关系,那空间复杂度则示意的是算法存储空间随数据规模增进的转变关系.


总结

复杂度用来剖析算法执行效率与数据规模增进的转变关系,越高阶复杂度的的算法执行效率也就越低,上面枚举的复杂度级别从低到高划分为O(1)、O(logn)、O(n)、O(nlogn)、O(n²).

来自:https://segmentfault.com/a/1190000018129300


思源资源网:分类流动

1.阿里云: 本站现在使用的是阿里云主机,平安/可靠/稳固。点击领取2000米代金券、领会最新阿里云产物的种种优惠流动点击进入

返回列表

上一篇:RemoveBG

下一篇:progress.js

相关文章

网络推广怎么做(新手网络推广怎么干)

  互联网如何做推广(初学者互联网推广如何干)针对初学者而言,互联网推广是件繁杂又非常烧脑的事儿,互连“网”太宽,该从哪里下手?有什么方式?有什么推广方式?这些。互联网推广确实难吗?瑞萦文化传媒觉得,...

奉献爱心共建人类精子库,另有5000块钱拿

谢谢本站会员“一个小同伙”分享,原帖地址,更多内容分享请接见本站论坛。 很早就听说捐精可以赚钱,要害是可以奉献爱心啊。 官方网站: 中国人类精子库 ...

win10电脑bios设置u盘启动方法,不同主板的bios设置

win10电脑bios设置u盘启动方法,不同主板的bios设置

操作方法 01 进入BIOS的方法,不同的电脑型号进入BIOS的方法是不一样的,大部电脑开机后按Del进入BIOS设置第一启动项的。注意按下快捷键进入主板之前要先插上U盘。 02 按住De...

咋个定位别人手机位置(如何定位老公的手机所在位置)

咋个定位别人手机位置(如何定位老公的手机所在位置) 这篇文章咱们聊一下如何通过手机定位你的男朋友或者是女朋友的位置。其实这个不仅仅适用于情侣之间。也可以通过这个办法寻找你的家人。 在这里咱们以苹果...

黑客xss是什么意思(xds黑客800怎么样)

黑客xss是什么意思(xds黑客800怎么样)

xss什么意思 XSS是实验小卫星的意思,是Experimental Small Satellite的缩写。数字版是游戏及后续更新内容都储存在游戏机内。xss只能玩数字版。数字版是游戏及后续更新内容都...