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

raise_yang 发布于2019-08-19 11:33 / 1512人阅读

摘要：作为开发人员，我们都希望在完成功能的基础上让代码运行的更快更省空间，那如何衡量编写的代码是否更有效率，这就需要我们学会如何分析代码时间复杂度和空间复杂度什么是复杂度分析执行时间和占用空间是代码性能的个评判标准，我们分别用时间复杂度和空间复杂

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

什么是复杂度分析

执行时间和占用空间是代码性能的２个评判标准，我们分别用时间复杂度和空间复杂度去描述这２个标准，二者统称复杂度，复杂度描述的是算法执行时间（或占用空间）随数据规模的增长关系．

为什么需要复杂度分析

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

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)与代码的执行次数ｎ成正比．我们可以用公式来表示

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²)．

GPU云服务器云服务器时间复杂度快速排序时间复杂度最大流算法时间复杂度数据结构时间复杂度

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77453.html

十分钟弄懂：数据结构与算法之美 - 时间和空间复杂度

摘要：什么是复杂度分析数据结构和算法解决是如何让计算机更快时间更省空间的解决问题。分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。复杂度描述的是算法执行时间或占用空间与数据规模的增长关系。这就是大时间复杂度表示法。 showImg(https://segmentfault.com/img/bVbtpFP?w=1000&h=574); 复杂度分析是整个算法学习的精髓，只要...

Salamander 2019-08-23 17:54 评论0 收藏0
【javascript系列】时间复杂度和空间复杂度

摘要：第三段，时间复杂度。五空间复杂度分析空间复杂度的话和时间复杂度类似推算。一、前言时间复杂度和空间复杂度，我们在大学里的算法与数据结构课程中已经学习过，这回根据项目工作中整理一下，这个估计只是一个粗略的估计分析，并不是一个准确的估计分析。 1、学习时间复杂度和空间复杂度是很有必要的，这个属于算法与数据结构的范畴，学这个是为了解决代码中的快和省的问题。这样才能使你的代码运行效率更高，占...

dcr309duan 2019-08-26 10:18 评论0 收藏0
卷积神经网络的复杂度分析

摘要：同样以里的模块为例，替换前后的卷积分支复杂度如下中使用与卷积级联替代卷积中提出了卷积的，在确保感受野不变的前提下进一步简化。在梳理CNN经典模型的过程中，我理解到其实经典模型演进中的很多创新点都与改善模型计算复杂度紧密相关，因此今天就让我们对卷积神经网络的复杂度分析简单总结一下下。1.时间复杂度1.2 卷积神经网络整体的时间复杂度示例：用 Numpy 手动简单实现二维卷积假设 Stride...

tracy 2019-04-25 18:21 评论0 收藏0
排序之八大绝技

摘要：需要注意的是排升序要建大堆，排降序建小堆。应用场景需要前个最大或最小元素时，或者与其他排序一块使用五冒泡排序排序思想大的元素向下沉，小的元素向上浮。目录一.插入排序 1.插入排序思想 2.动态图形演示 3.插排思路与图解 4.插入排序代码实现（升序） 5.时间复杂度，空间复杂度及稳定...

Vixb 2021-11-23 09:51 评论0 收藏0
JavaScript 数据结构与算法之美 - 冒泡排序、插入排序、选择排序

摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，...

canger 2019-08-26 10:15 评论0 收藏0