2021-05-12

数据复杂度分析

数据结构和算法本身解决的快和省的问题；

如何衡量的代码的执行效率；时间、空间复杂度分析。

1. 测试结果非常依赖测试环境

2.测试结果受数据规模的影响很大

大O复杂度表示法

所有代码的执行时间T(n)与每行代码的执行次数成正比。

大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

时间复杂度分析

1.只关注循环执行次数最多的一段代码

int cal(int n) {

  int sum = 0;

  int i = 1;

  for (; i <= n; ++i) {

    sum = sum + i;

  }

  return sum;

}

其中第2、3行代码都是常量级的执行时间，与n的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第4、5行代码，所以这块代码要重点分析。前面我们也讲过，这两行代码被执行了n次，所以总的时间复杂度就是O(n)。

2.加法法则：总复杂度等于量级最大的那段代码的复杂度

3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

几种常见时间复杂度实例分析

1. O(1)

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

2. O(logn)、O(nlogn)

i=1;

while (i <= n)  {

  i = i * 2;

}

从代码中可以看出，变量i的值从1开始取，每循环一次就乘以2。当大于n时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量i的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的：

现在，把代码稍微改下，这段代码的时间复杂度是多少？

i=1;

while (i <= n)  {

  i = i * 3;

}

根据我刚刚讲的思路，很简单就能看出来，这段代码的时间复杂度为O(log3n)。

实际上，不管是以2为底、以3为底，还是以10为底，我们可以把所有对数阶的时间复杂度都记为O(logn)。为什么呢？

空间复杂度分析

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

我们常见的空间复杂度就是O(1)、O(n)、O(n2 )，像O(logn)、O(nlogn)这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。