《学习JavaScript数据结构与算法》——第十五章 算法复杂度

再学习所有算法之前,我们需要了解一下算法复杂度,包括大O表示法,时间复杂度,NP完全理论。

什么是大O表示法

大O表示法是描述算法的性能和复杂程度的一种方法,大O表示法是将算法按照消耗的时间进行分类,依据随输入增大所需要的空间/内存
比如下面这张图,是我们常见的几类函数


再比如各类排序算法

比如冒泡排序(下一篇文章会说到),需要两次循环,那我们就表示O(n²),如果是三次循环,那我们就表示O(n³)。

var a=[3,2,4,5,1];
function swap(array, p1, p2){
  var temp = array[p1];
  array[p1] = array[p2];
  array[p2] = temp;
}
function bubbleSort(array) {
  var index=1;
  while (index < array.length){
    var i=0;
    while(i<=array.length-1-index){
      if(array[i]>array[i+1]){
        // t = array[i];
        // array[i]=array[i+1];
        // array[i+1]=t;
           swap(array,i,i+1);
      }
      i++;
    }
    index++
  }
  return array;
}
2
console.log(bubbleSort(a));

时间复杂度比较

大O表示的时间复杂度

基于这张图可以画出大O表示法的消耗

常用数据结构的时间复杂度

图的时间复杂度

排序算法的时间复杂度

搜索算法的时间复杂度

NP完全理论概述

以后补充,暂时看不懂