每天一点算法-时间复杂度 (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)