学习前端算法前你需要了解的‘大O表示法’

布满荆棘的人生 2023-02-20 10:41 10阅读 0赞

**「前言」**

在现实生活中，解决一个问题可以有多种方法，其中有好的方法，也有较为一般的方法。评判标准虽有不同，但总体思想是：用最小的代价获得最多的收益。

这里所说代价并不仅指金钱开销，有时也包括时间，所耗费资源等。

计算机程序也是为了解决问题而编写的。同理可知，程序有好的，也有一般的，评判标准主要有两方面：时间与空间。

人们都希望事情解决的越快越好，所以程序解决问题花费的时间一定要少。计算机资源是有限的，所以程序也要尽可能的少消耗资源。

不过很多时候不能两全其美，此时应该抓主要矛盾。在编程时，很多场合会用空间消耗的增加来换取运行时间的减少。毕竟对于我们来说，时间一般会更加重要。

那么应该怎么比较不同算法之间的优劣呢？答：应该从时间与空间两方面入手。

本文主要带你了解什么是大O表示法，但是在了解大O表示法之前，你有必要了解什么是算法。

读完本文，你将了解到：

*  什么是算法
 *  算法设计的要求
 *  算法的好坏评定标准
 *  大O表示法

## 什么是算法？ ##

> 算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

简而言之，计算机算法，是用计算机解决问题的方法、步骤。解决不同的问题，需要不同的算法。![format_png][]

比如，小学乘法算法表，九九八十一。比如，妈妈做饭脑子里出现的食谱，先炒，再炖，再小火收汁（我又饿了）。

> 有一个很著名的公式 “程序=数据结构+算法”

## 算法设计的要求 ##

**「正确性」**

算法应当满足具体问题的需求,能够通过特定的问题测试。

**「可读性」**

算法主要是为了人的阅读与交流，其次才是机器的执行。

**「健壮性」**

当输入非法的数据时，算法也能够适当做出反应或进行处理，而不会产生莫名奇妙的输出结果。

**「效率与低存储量需求」**

效率指**「算法运行的时间，执行时间短效率高」**；存储量需求是指**「算法执行过程中所需的最大存储空间」**。

二者都与问题的规模相关，同时也要根据实际需求决择，要效率，还是要节省空间，或者折中。一般情况二者不可得兼，要么用空间换时间，要么用时间换空间。

## 算法的好坏评定标准 ##

**「时间复杂度 ：T(n)」**

> 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作 T(n)=O(f(n)) ，他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长相同，称作算法的渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

**「空间复杂度 ：S(n)」**

> 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

我们这里只讨论的是时间复杂度。需要注意的是，我们分析算法的时间复杂度，并不是基于算法执行的确切时间，而是基于算法**「执行步骤数量」**。而这个执行步骤数量因不同的情况，也分**「最好情况、最坏情况 和 平均情况」**

*  某个特定的数据集能让算法的执行情况极好，这就是最「最好情况」
 *  而另一个不同的数据会让算法的执行情况变得极差，这就是「最坏情况」
 *  不过在大多数情况下，算法的执行情况都介于这两种极端情况之间，也就是「平均情况」

我们要明白这几种情况的不同价值，这样才能帮助我们接下来了解的大O表示法

*  **「最优情况」**:没有什么大的价值，因为它没有提供什么有用信息，反应的只是最乐观最理想的情况，没有参考价值。
 *  **「平均情况」**:是对算法的一个全面评价，因为它完整全面的反映了这个算法的性质，但从另一方面来说，这种衡量并没有什么保证，并不是每个运算都能在这种情况内完成。
 *  **「最坏情况」**:它提供了一种保证，这个保证运行时间将不会再坏了，所以一般我们所算的时间复杂度是最坏情况下的时间复杂度，做事要考虑到最坏的情况是一个道理。

因此，我们知道了，分析算法的时间复杂度的好坏，通常是根据**「最坏情况」**去分析的。

## 大O表示法 ##

### 基本概念 ###

> 定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。

“大O记法”：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。

### 常见的大 O 运行时间 ###

以下由快到慢排序。

*  O（log n）,也叫对数时间，这样的算法包括二分查找
 *  O(n)，线性时间，包括简单查找
 *  O(n\*log n)，包括快速排序（业界俗称快排），一种速度较快的快速排序
 *  O（n^ x）,包括平方时间、立方时间
 *  O(2n) 指数时间
 *  O（n！），包括旅行商问题的解决方案，一种非常慢的算法

#### O（log n） ####

> O(log2n)表示每次循环运行之后，需要处理的数据减去一半。比如100、50、25、13。。。

##### 对数 #####

了解对数时间，就要先了解什么是对数，尽管对数在高一就学过，但是想必不少人都忘记了它吧（小声逼逼）。如果你清楚什么是对数，请直接跳过这个环节。

指数是幂运算aⁿ(a≠0)中的一个参数，a为底数，n为指数，指数位于底数的右上角。

1、当指数 n=0时，![format_png 1][]

2、当指数 n>0时，，且n为整数时，![format_png 2][]

3、当指数 n<0时，![format_png 3][]

4、当指数n=2时，称为平方。

5、当指数 n=3时，称为立方。

如果

![format_png 4][]

，即a的x次方等于N（a>0，且a≠1），那么数x叫做以a为底N的对数（logarithm），记作

![format_png 5][]

。其中，a叫做对数的底数，N叫做真数，x叫做“以a为底N的对数”。

##### 二分查找法 #####

> 二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回 null

> 一般而言，对于包含 n 个元素的列表，用二分查找最多需要 log2 n 步，而简单查找最多需要 n 步。

我们通过 JS 来实现一下思路：

如果我们输入一个包含100个元素的有序数组，那么我们利用二分查找，最快找到元素的步骤设为n 那么![format_png 6][]

这就是O(logn)表示法。

### 线性时间O(n) ###

> o(n)表示 随着输入量的增加，时间复杂度呈线性增长。

这里以简单查找的方法举例：

function test (array,num){
      for(let i =0;i<array.length;i++){
        if(array[i] === num){
          return i
        }
      }
    }

### 平方时间![format_png 7][] ###

> 表示的是算法的时间复杂度随着输入量的变化发生平方变化。

在js中，典型的就是双层循环

function test(arr1,arr2,){
        arr1.map(item=>{
          arr2.map(item2=>{
            if(item2 === item1){
              return item
            }
          })
        })
      }

立方时间同理，算法的时间复杂度随着输入量的变化发生立方变化，常见的算法有三层循环。随着循环层k的增加，算法复杂度为![format_png 8][]

### 指数时间 ###

![format_png 9][]

> 指数时间表示的算法的时间复杂度随着输入量的增加呈两倍数增加。常见算法：选择排序

**「常用排序算法的时间复杂度」**

<table> 
 <thead> 
  <tr> 
   <th>排序法</th> 
   <th>最差时间分析</th> 
   <th>平均时间复杂度</th> 
   <th>稳定度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(n2)</td> 
   <td>O(n2)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(n2)</td> 
   <td>O(n*log2n)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>O(n2)</td> 
   <td>O(n2)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>二叉树排序</td> 
   <td>O(n2)</td> 
   <td>O(n*log2n)</td> 
   <td>不一定</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>O(n2)</td> 
   <td>O(n2)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(n*log2n)</td> 
   <td>O(n*log2n)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O</td> 
   <td>O</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

以上为全部内容，谢谢您的观看和点赞。

**「参考文章」**

什么是算法？

算法图解1 - 二分查找和大O表示法

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9tMEFzN1hPQ1YzVjhCOFd5cElqWjFmZ21IVGY3Z01QYk5RRnlHMzQ3UWdiVXFSY0s5SjFITnZ1bmRxdjBZQkZoS3RYaklPc3dQaWNmaWFCeGhrM1JaMXJ3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9tMEFzN1hPQ1YzVjhCOFd5cElqWjFmZ21IVGY3Z01QYkM2eW91dGxKeExmaWFKdW5hYVdQcFcyU25pYjJ4VXNqaWJBUWtrWXk2YnZlMGtJUHdFWkM2Mk10US82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9tMEFzN1hPQ1YzVjhCOFd5cElqWjFmZ21IVGY3Z01QYnhpYnJhdGs0VjlpY2RqY2liUzBWNXlPMFZ6R2lhaWNBWTV2eDJQRUU1OXBGQUVFcXhPSHkzZFhBaWJady82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9tMEFzN1hPQ1YzVjhCOFd5cElqWjFmZ21IVGY3Z01QYjRUcG5NVkEzeFRHbUZmSU1IUnVJMTlpYlJraFhpYU5Tc1BhaWNNTlNDTVZnSEpUTXJKaGlidFNVUHcvNjQw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9tMEFzN1hPQ1YzVjhCOFd5cElqWjFmZ21IVGY3Z01QYlljVHQyd3Q4aWJGV1JOVTQzQk5KenV2N0hGWm1NT3ppY2hXVEl0clZTaDVpYkIwMEo4cEN3TTJ0US82NDA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9tMEFzN1hPQ1YzVjhCOFd5cElqWjFmZ21IVGY3Z01QYldnekxYbmVoeUxudXU2cXNCWGJ3UDlndU1sd0VCYURaVGNjTVhuaWNtZFhCY01Va243QXNpY3pRLzY0MA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9tMEFzN1hPQ1YzVjhCOFd5cElqWjFmZ21IVGY3Z01QYjJzaWNGbFA2cVJpY2VPTEpibE42ZUZnbmNoeXVmdkVTQzhydWJlYURpY3RlVWliTmpQNHl2Z25KNGcvNjQw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9tMEFzN1hPQ1YzVjhCOFd5cElqWjFmZ21IVGY3Z01QYm80S1JTUVJwdk9VWFV4cEdaanJWSjducm5vbnAxSEdZRzlzMkRub01TaWFzUWhVREdpY0w2S3NBLzY0MA?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9tMEFzN1hPQ1YzVjhCOFd5cElqWjFmZ21IVGY3Z01QYmw4S1A0a3k4OGtuY3IyVlo3SnFTMFdGdkJueDFpYm12TmZMZ2c5eVNSY01kMllZU24zVmdMZEEvNjQw?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9tMEFzN1hPQ1YzVjhCOFd5cElqWjFmZ21IVGY3Z01QYmlhbVM3dXFnekppYlpDSFZOaDUzbEFTa2lhTWpLaWFKaWNoa0tHSm5aWG9zNWhhVEpveTJpYjJOWHp3dy82NDA?x-oss-process=image/format,png