算法复杂度

算法复杂度

之前在学习算法或者是在看React文档中的diff算法时，总是提到复杂度这个关键词， 而且往往它们都是根据复杂度来评价算法的优劣， 那算法的复杂度到底是什么呢？ 以及它们如何计算出来的呢？带着这些疑问学习一下吧。

大O表示法

算法的复杂度常常通过大O表示法表示，大O表示法表示程序运行所需要消耗的时间或占用空间随程序数据规模增长的变化趋势，大O表示法就是将程序的所有执行步骤总和转换为关于规模n的通项公式, 然后去除不会对问题的整体复杂度产生较大影响的低阶系数和常数项。根据所需时间和所用空间， 又细分出了时间复杂度和空间复杂度.

时间复杂度

又称渐进式时间复杂度: 执行算法需要消耗的时间与数据规模之间的增长关系: T(n) = O(f(n)) 其中n表示程序数据规模, f(n)表示复杂度的具体算法(执行步骤总和)， T(n)表示算法执行所消耗的总时间：

//伪代码
let n = 10, sum = 0; 
for (let i=0; i++; i<n ) {
  	sum = sum + i
}
复制代码

假定每一行代码的执行所消耗的时间都是相同的、都为1个单位时间， 那么:

let n = 10, sum = 0; 所需要消耗的时间为1
let i=0; i++; i<n 所需要消耗的时间为n
sum = sum + i 所需要消耗的时间为n
复制代码

所以整个程序消耗的总时间就为2n+1,如果当n无限大时, 低阶系数和常数项就可以忽略不计, 所以f(n)=n, 用大O表示法就是O(n)

常见的时间复杂度量级

1. 常数阶O(1)

   let i = 10;
   let j = 0; 
   let k = i + j
   复制代码

   还是假定每一行代码的执行所消耗的时间都是相同的、都为1单位时间; 如果有n行代码需要执行,执行时间就是n了,那么这段程序的时间复杂度是不是就是 O(n) 了呢? 事实上不是的。大 O 表示法的时间复杂度实际上并不具体表示代码真正执行所消耗的时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度，简称时间复杂度。如果程序的执行时间不随着问题规模n的增加而增长，即使程序中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 再通俗一点就是: 只要算法中不存在循环语句、递归语句，即使程序中有上千条语句，其时间复杂度也是Ο(1)。

2. 对数阶O(logn)

   let i = 1;
   while(i < n) {
       i = i * 2;
   }
   复制代码

   以前一直不理解为什么时间复杂度怎么还会有对数阶?这回终于搞明白了。像这种有循环体的，我们就只需要关注循环体内执行次数最多的一条语句就可以了。在上面的程序中i的值从1开始, 每循环一次i的值乘以2, 当i的值大于n时循环结束. 不难看出i的值依次是2⁰、2¹、2²、2³……、2ˣ，其中x的值就代表循环次数，而且循环结束的临界条件是 2ˣ=n 根据数学中的对数公式就可以求出x的值了，即x = log₂?; 所以其时间复杂度为O(log₂?)

3. 线性阶O(n)

for (let i=0; i++; i<n ) {
  	sum = sum + i
}
复制代码

上面有提到过,不再叙述, 但是对于循环语句, 在计算时间复杂度时,只需要关注循环体内执行次数最多的那条语句就可以了, 因为在n值无限大时, 其他的都可以忽略不计了.

4. 平方阶O(n²)

for (let i=0; i++; i<n ) {
  	for (let j=0; j++; j<n ) {
        sum = sum + i + j
    }
}
复制代码

空间复杂度

又称渐进式空间复杂度: 执行算法所需要的存储空间与数据规模之间的增长关系，同时间复杂度类似，空间复杂度同样表示的是一种增长趋势，而不是具体的存储大小值。 S(n) = O(f(n)) 其中n表示程序数据规模, f(n)表示复杂度的具体算法(所用单位空间)， S(n)表示算法执行所需要的存储空间。 空间复杂度相对于时间复杂度来说，要简单的多了， 因为最常见的就那么两种：

1. 常数阶O(1)

   let i = 10;
   let j = 0; 
   let k = i + j
   复制代码

   程序的执行所需要的存储空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，无非是大小之分， 空间复杂度可表示为O(1)

2. 线性阶O(n)

   //伪代码
   let sum = {}
   for (let i=0; i++; i<n ) {
     	sum[i]= i
   }
   
   复制代码

   程序每循环一次，都需要内存开辟一个空间来存储i的值, 整个程序运行所需要的空间是随着变量n的增加而增加的， 是一种线性增加关系， 空间复杂度可表示为O(n)

在空间复杂度中，像对数阶O(logn)，指数阶O(n²)、O(n³) 等， 试想一下， 我们平时的程序中是不是都很少用到，这里也就不再叙述了。