算法学习-算法复杂度

算法复杂度用于衡量算法的效率,用大O来表示。使用大O表示法分析算法复杂度时,时常遇到以下几类函数

O(1)

function increment(num){
  return ++num;
}

increment函数用于计算数值加1的结果,无论数值是几,函数内部只执行了一次运算,它的复杂度就是O(1)。常见的比如数组/栈/队列、链表的插入和删除操作,时间复杂度都是O(1)

O(n)

function sequentialSearch(item, array){
  for (var i=0; i<array.length; i++){
    if (item === array[i])
      return i;
    }
  }
  return -1;
};

sequentialSearch是一个顺序搜索函数,时间复杂度取决于array的大小,如果array的长度是100,开销就是100,因此sequentialSearch的复杂度是O(n)。

O(n^2)

冒泡排序的时间复杂度是O(n^2),冒泡排序内部有两个循环,因此如果要排序的数组长度是100,开销就是10000,复杂度就是O(n^2)。如果某个算法内部要三次循环,它的复杂度就是O(n^3)

数据结构时间复杂度

注释: 图中的二分搜索树应该是二叉搜索树

排序算法时间复杂度

搜索算法时间复杂度

总结

冒泡排序:O(n2)
快速排序:O(nlog2n)

顺序搜索:O(n)
二分搜索:O(log2n)

posted @ 2018-10-10 20:10:11 浏览(334) JavaScript笔记

avatar