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

我去年给自己定了个今年存款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=n¹, 1=n⁰, 所以n的为最高阶项）；第三条，2n应该除以常数2；所以这里的时间复杂度为O(n)。

对数阶

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

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

平方阶

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

假设循环次数为n²，时间复杂度为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)