复杂度分析

[18888628835]

一、什么是数据结构?什么是算法?

从广义上讲,数据结构就是指一组数据的存储结构.算法就是操作数据的方法.

比如,图书馆储存书籍,为了方便查找,图书管理员一般会将书籍分门别类进行存储.按照一定规律编号,这就是书籍这种数据的存储结构.

那么如何来查找一本书呢?我们可以一本一本查找,也可以根据书籍的某种规律(编号、类别)等方法查找。笼统来说，这些查找方法都是算法。

从狭义上讲，数据结构和算法比如队列、栈、堆、二分查找、动态规划等，这些都是前人智慧的结晶，我们可以直接拿来用。

二、数据结构和算法的关系

数据结构和算法是相辅相成的。数据结构需要为算法服务，而算法需要作用在特定的数据结构之上。

比如：数据具有随机访问的特点，常用的二分查找算法需要用数组存储，但是如果选择了链表这种数据结构，二分查找就无法工作，因为链表不支持随机访问。

数据结构是静态的，它只是组织数据的一种方式。因为不在它的基础上操作、构建算法，孤立存在的数据结构是没用的。

三、复杂度分析

学习数据结构和算法，首先需要掌握一个最重要的概念——复杂度分析。

这个概念几乎是数据结构和算法的半壁江山，是数据结构和算法学习的精髓。

数据结构和算法解决的是如何更省、更快地存储和处理数据的问题。因此，我们需要一个考量效率和资源消耗的方法，这就是复杂度分析。

3.1为什么需要复杂度分析

很多时候，我们只需要把代码跑一遍，通过统计、监控就可以得到算法执行的时间和占用的内存大小。那为什么还需要做复杂度分析呢？这种分析方法能够比我实实在在跑一遍更加准确吗？

通过统计、监控的手段得出代码执行时间和占用内存大小有一个专业的名词，叫做事后统计法。但是这种统计方法具有非常大的局限性。

• 测试结果依赖测试环境
  测试环境中的硬件设备的差异性会影响到测试结果，比如同一段代码在i3和i9之间处理，速度肯定是i9更快。你要怎样证明你写的代码比你同事的更快？放在同一台电脑上运行当然可以，但是可能换了一台电脑会得到截然相反的结果。

• 测试结果受数据规模影响大
  同一个排序算法，在待排序数据的有序度不一样，排序的执行时间就会有很大差别。比如，数据已经是有序的，那么排序算法就不需要做任何操作，执行时间就会非常短。

此外，数据规模如果很小，可能无法真实反映算法性能。比如小规模的数据排序，插入排序可能比快速排序要快。

因此，我们需要一个不用具体的测试数据来测试，就可以粗略估计算法执行效率的方法。

3.2大O复杂度表示法

算法的执行效率，可以粗略用执行时间来表示，如何在不运行代码的情况下，用肉眼得到一段代码的执行时间？

来看下面这段代码

function fn(n){
  let sum=0;
  let i=0
  for(;i<n;i++){
    sum= sum + i
  }
  return sum
}

从cpu角度来看，这段代码每一行都执行类似的操作：读数据，运算，写数据。尽管每行代码对应的cpu执行个数、时间都不一样，但是，我们这里只是粗略估计，所以假设每行代码的执行时间都相同，为n_time。在这个基础上，我们可以得出总执行时间是多少？

当函数执行时，第二行、第三行代码为2个n_time时间。第四行、第五行则运行了n遍，为2n个n_time时间，计算下来总体的时间为 2*n_time+2n*n_time, 合并后则为

T(n)=(2n+2)*n_time

我们可以看出，代码的执行时间T(n)和每行代码执行次数n成正比。即n越大，T(n)越大。

按照这个思路，我们再来看一段代码

function fn(n){
  let sum=0;
  let i =0;
  let j=0;
  for(;i<=n;i++){
    for(;j<=n;j++){
      sum = sum + i +j
    }
  }
}

依然假设这段代码每行的时间为n_time，那么第二、三、四行为3*n_time，第五行需要n*n_time时间，第六、七行则分别执行了n*n*n_time时间。所以T(n)时间为3*n_time+n*n_time+2*n²*n_time,简化后为

T(n)=(3+n+2n²)*n_time

通过两段代码，我们可以得到一个非常重要的规律

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

我们可以把这个规律总结成一个公式

其中T(n)表示代码执行的时间，n表示数据规模的大小，f(n)表示每行代码执行次数的总和。因为这是一个公式，所以用f(n)表示。公式中的O,表示代码执行时间T(n)与f(n)成正比

我们将第一个例子中的f(n)放入这个公式中，就变成了

T(n)=O(2n+2)

将第二个例子中的f(n)放入到公式中，就变成了

T(n)=O(3+n+2n²)

这就是大O时间复杂度表示法。大O时间复杂度表示法实际上并不是表示具体代码执行的时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也称为时间复杂度。

当n很大时，比如n为1000000，那么诸如3+n+2n²中的3、n、2都可以忽略，因为并不会影响到增长趋势。我们只需要记录一个最大量级就可以了，于是最终的公式就变成：

第一个例子

T(n)=O(n)

第二个例子

T(n)=O(n²)

3.3时间复杂度分析的方法

前面介绍了时间复杂度的演进过程和表示方法，那么我们如何分析一段代码的时间复杂度？有三个比较实用的方法。

只关注循环次数最多的代码

由于大O法只表示一种数据变化的趋势，所以我们可以忽略掉公式中的常量、系数、低阶，只需要记录最大的量级即可。

所以我们在分析算法、代码的时间复杂度时只需要关注执行次数最多的那一段核心代码。这段核心代码执行次数的n的量级，就是整段要分析代码的时间复杂度。

以第一个例子为例：

function fn(n){
  let sum=0;
  let i=0
  for(;i<n;i++){
    sum= sum + i
  }
  return sum
}

第二、三行代码就是常量，第四、五行的代码是循环执行最多的核心代码，应当记为2n次，2为系数，也可以忽略，因为系数是不变的，它并不影响增长趋势。所以最终得到O(n)

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

比如下面的三段代码：

function cal(n){
  let sum_1=0;
  let p1=0;
  for(;p1<100;p1++){
    sum_1 = sum_1 + p1
  }
  
  let sum_2=0;
  let p2 =0;
  for(;p2<n;p2++){
    sum_2 += p2
  }
  
  let sum_3=0;
  let p3 =0;
  let p4 =0
  for(;p3<n;p3++){
    for(;p4<n;p4++){
      sum_3 = sum_3 + p3 + p4
    }
  }
}

上面的函数里面有三段不同的代码，我们在第一条规则的基础上忽略掉常量，只看代码段中执行最多的代码。

第一段代码的循环执行了100次，因为它已知且跟n无关，不管是10000次还是1000000次，它依然只是常量。时间复杂度所表现的是算法的执行效率和数据规模增长的变化趋势，当n无限大时，这个常量对数据规模的增长趋势并没有影响，所以我们直接忽略。

第二段代码执行了n次，记为O(n)

第三段代码执行了n²次，记为O(n²)

综合三段代码，我们取其中最大的量级，所以cal函数的时间复杂度为O(n²)。

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

举个例子

function cal(n){
  let result=0
  for(let i=0;i<n;i++){
    result += fn(n)
  }
}

function fn(n){
  let r=0
  for(let i=0;i<n;i++){
    r += i
  }
}

单看第一个函数，我们可以得出复杂度为O(n),只是在第一个函数中，里面有一段fn(n)的执行代码，fn(n)的复杂度同样是O(n)，最终我们得出复杂度为O(n²)

3.4常见时间复杂度量级

其中划线的部分称非多项式量级，当数据规模越来越大时，非多项式算法执行时间会急剧增加。

非划线部分为多项式量级。

O(1)级

O(1)是常量级时间复杂度的表示方法，比如说下面的代码

let i=0
let j=1
let k=i + j

虽然有三行代码，但是其依然记作O(1)级代码。有个简单的记忆方式：只要算法中不存在循环、递归，那么即使代码行数过万，也只是O(1)级时间复杂度。

O(logn)、O(nlogn)

数阶的时间复杂度非常常见，但是非常难分析。比如下面这行代码

let i=1
while(i<n){
  i=i*2
}

我们可以看出第三行代码运算次数最多。只要i小于n，那么i会不断乘以2，直到大于n为止。

所以i的结果是

1 * 2=> 2 * 2=> 4 * 2=> 8 * 2=> 16 * 2=> ...x * 2 >= n

换算一下就可以表示为

所以，我们只要知道x是多少，那就知道代码执行了多少次。那么x怎么计算呢？就是x=log2(n)。意思是2为底数被n开方的结果为x。

得出这段代码的时间复杂度为O(log2(n))

不管底数是多少，由于底数可以互相转换，比如O(log3(n))等于log2(n)*log3(2)。

由于时间复杂度只是表示算法的执行效率和数据规模增长的变化趋势，所以我们可以把系数去除，最终我们得到代码

T(n)=O(logn)

那么现在O(nlogn)就很好理解了，只需要用一个循环把上面的代码再执行n遍，那么就是O(nlogn)的时间复杂度。

O(m+n)、O(m*n)

这种时间复杂度是由两个数据规模共同组成的。

看一段简单的代码

function fn(m,n){
  let sum1=0
  for(let i=0;i<m;i++){
    sum1 += i
  }
  
  let sum2=0
  for(let j=0;j<n;j++){
    sum2 += j
  }
}

由于我们并不知道m跟n的数据规模，所以我们不能省略掉其中一个，只能加起来，所以最终的时间复杂度就是

T(m,n)=O(m+n)

3.5空间复杂度分析

时间复杂度表示算法效率（时间）与数据规模n增长趋势的关系，那么空间复杂度就是算法的存储空间与数据规模增长的趋势关系。

常见的空间复杂度就只有O(1)、O(n)、O(n²)三种。直接上代码

let a=1
let b=1
let c=a + b

我们试着想象一下，这段代码开辟了多少跟数据规模n有关的内容？完全没有，所以这段代码的空间复杂度就是O(1)。

再来一段代码

let a=[]
for(let i=0;i<n;i++){
  a[i] = i
}

上面这段代码的循环中，只要n越大，那么数组a的存储空间就越多，所以这段代码的空间复杂度就是O(n)

3.6内容小结

时间复杂度表示算法执行效率和数据规模增长之间的关系。

空间复杂度表示算法存储空间和数据规模增长之间的关系。

我们用大O复杂度表示法来表示，同时我们忽略系数、常量、低阶的因素，最终我们常见的复杂度可以用以下表示

• O(1)
• O(n)
• O(n²)
• O(logn)
• O(nlogn)
• O(m + n)
• O(m * n)
  如果我们用数学的坐标系来表示，可以用这张图模拟部分复杂度的增长模型

3.7最好、最坏、平均、均摊时间复杂度

继续分析下面代码

function fn(array){
  let i=0
  let a=100
  let c
  for(,i<array.length,i++){
    if(array[i]===a){
      c=i
    }
  }
  return c
}

很简单，上面的代码的时间复杂度为O(n),n为array.length。

不过我们如果中途查到这个数字，那么后面就不用了再循环了，所以我们可以这样改进

function fn(array){
  let i=0
  let a=100
  let c
  for(,i<array.length,i++){
    if(array[i]===a){
      c=i
      break;
    }
  }
  return c
}

现在复杂度是多少？如果第一位就找到，那么复杂度就是O(1)，如果不存在，那就是O(n),这说明在不同情况下，这段代码的复杂度不一样。

那么也就引进了最好时间复杂度、最坏时间复杂度和平均时间复杂度。

最好时间复杂度就是最快的，比如第一位就找到了，那自然是最好时间复杂度。

最坏时间复杂度就是最慢的，全部撸一遍，最后一个才找到，那自然是最坏时间复杂度。

但是上面的两种复杂度相对来说意义不大，因为概率小。所以我们需要平均时间复杂度这一说。

平均时间复杂度的计算方式是这样的：我们需要将遍历的所有元素之和加起来，然后除以所有情况，就可以得出平均时间复杂度。

以上面的代码为例，总共有 n+1种情况：0到n-1次为 n 种情况，另外一种情况是没有找到。

遍历元素之和是多少？假设第0个下标找到，就是遍历1个元素；第1个下标找到，就是遍历2个元素...第 n-1个下标（最后一个位置）找到，那么就是遍历 n 个元素，如果没有找到的情况，同样也要遍历 n 个元素。

所以我们可以得出公式为

平均复杂度=(1+2+3+...n+n)/n+1

其中(1+2+3+...n+n)可以变化为

得出公式为(3n+n²)/2

然后将目前的公式上下都乘以2

最终公式是这样的

由于系数、低阶等都不在考虑范围内，所以我们可以得出平均时间复杂度为 O(n)