关闭

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

时间: 2019-02-07阅读: 1035标签: 开发

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


什么是复杂度分析

执行时间和占用空间是代码性能的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.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

链接: http://www.fly63.com/article/detial/1985

关闭

敏捷开发是如何被跑偏的

先说结论:据我观察,至少有60%的团队误用了敏捷软件过程,或者说至少60%的团队在进行伪敏捷开发。与大家通常的认知是相反的,敏捷过程并不是一个非常容易实践或者实施的过程规范。

敏捷开发

我们最优先要做的是通过尽早的、持续的交付有价值的软件来使客户满意。即使到了开发的后期,也欢迎改变需求。敏捷过程利用变化来为客户创造竞争优势。

别再空谈敏捷开发了

现如今,“ 敏捷 ”可以是指任何东西。渐渐地,它就变得毫无意义了。很多企业已经对”敏捷“感到厌倦了,甚至有了抗拒性。更糟糕的是,就像孔子说的那样:跨学科研究、原则和实践是敏捷的未来。

软件开发教给我们的7个生活指南

我们在做软件开发时学到的很多思维、方法、工具、模型、算法……其实可以迁移到生活中使用,让我们生活得更美好哦。我这里暂举 7 个,以后有时间,慢慢补坑,争取补到 60 个。大家有兴趣的,可以留言补充你最有感觉的。

12 个概念,让 JavaScript 开发更加简单

JavaScript 是一门复杂的语言,不管处于什么样的水平,都有必要了解 JavaScript 的基本概念。本文介绍了 12 个非常重要的 JavaScript 概念,但绝对不是说掌握好 JavaScript 只需要知道这些就可以了。

写给开发人员:为什么朝九晚五不适合我们?

位我很尊敬的高级开发人员给我打来电话。他想找个朋友聊聊:因为担心自己只能得到可怜的 12% 加薪——而他所管理的其他初级开发人员,则有望获得 40% 的加薪。他还抱怨道

从后端开发转职前端开发,我学到了什么?

从后端开发转职到前端开发真的不容易。特别是当你已经习惯了后端开发的工作模式,习惯了构建数据结构,编写类似于测试驱动开发的测试,习惯了使用持久层、仓库和数据库图表,以及给前端创建API接口。

不想谈业务的开发不是好开发?

业务,似乎与开发人员不是太相关,开发人员天生处于技术端。但是,一个只会开发的开发人员,很容易被代替,只有真正了解业务,才能真正了解需求,做出好的产品。那么如何去解决这些问题呢?

js处理时间时区问题

服务器时间是东八区时间,页面会在全世界各地,页面 JS 功能需要对比服务器时间和用户本地时间,为兼容世界各地时间,需要将用户本地时间转换为东八区时间

5 个 VSCode 扩展提高你的开发兴趣

VSCode 为我们提供了一个小颜色框作为参考,但它还不够大,无法判断相似颜色之间的差异。Color Highlight 通过用颜色包装每个十六进制代码为我们提供了更大的预览。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!