web前端杂文让前端飞程序员

每天一点算法-时间复杂度 (Day1)

2018-12-29  本文已影响22人  岛民小强

我去年给自己定了个今年存款3万块的小目标,掐指一算,现在还差5万。

又是定小目标的时间,2018年余额只有2天了,我参加了简书的坚持写作60天以上的活动,也算是激励自己吧。第一部分将跟分享算法与数据结构相关的知识,共同学习。废说少话,day1开始。

概念

算法的时间复杂度是表示算法所消耗时间大小的量度,通常使用大O表示法来建立数学模型,即O(f(n)),随着n的数值增大,O(f(n))的数值增长的越慢就越是时间复杂度低的算法

大O阶推导

大O表示法的关键在O里面的阶,推导大O阶的步骤:

1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中,只保留最高阶项。
3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。得到的结果就是大O阶。

例子

常数阶

var a = 1, b = 1; //运行一次
var sum = a + b; //运行一次

运行了2次,按照推导方法,“2”是常数,应该用"1"来取代;然后就没有出现阶项,所以忽略后面两个推导步骤。所以这里的时间复杂度为O(1)

线性阶

for(var i = 0; i < 2*n+3; i++){ //执行了2*n+3次
  sum +=n;
}

执行次数为2n+3,按照第一步推导为2n+1; 按照第二步推导修改为2n(为什么呢?因为n=n1, 1=n0, 所以n的为最高阶项);第三条,2n应该除以常数2;所以这里的时间复杂度为O(n)

对数阶

var cout = 1;
while(cout < n){
  cout = cout * 2; 
}

假设循环次数为x, 则次表达式成立:2x = n, 及x = log2n, 时间复杂度为O(logn)

平方阶

  for(var i=0;i<n;i++){   
      for(var j=0;j<n;j++){
         //时间复杂度O(1)的语句
      }
  }

假设循环次数为n2,时间复杂度为O(n^2)

时间复杂度的比较

常见的时间复杂度所耗费的时间大小关系:
O(1 )< O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

上一篇下一篇

猜你喜欢

热点阅读