大家好，又见面了，我是你们的朋友全栈君。
一、算法时间复杂度定义
在进行算法分析时候,语句总的执行次数T(n)是关于问题规模n的函数,进而分型T(n)随着n的变化情况并确定T(n)的数量级.算法的时间复杂度,也就是算法的时间度量记作:T(n)=O(f(n)).它表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度.其中f(n)是问题规模n的某个函数.
简单来说T(n)代表时间频度：一个算法中语句执行次数称为时间频度
时间复杂度就是：算法的时间复杂度描述的是T(n)的变化规律，计作：T(n) = O(f(n))。
这里用大写的O( )来体现算法时间复杂度的记法,我们称之为大O记法.
二、推导大O阶方法（游戏秘籍三部曲）
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果最高阶项存在且不是1，则去除与这个项乘积的常数。
三、常数阶
let sum = 0, n = 100 //执行一次
sum = (1 + n) * n / 2 //执行一次
return sum //执行一次这个算法的运行次数是f(n)=3,与n的大小无关
根据推导大O阶的方法,常数项3改为1,即时间复杂度为O(1)
对于分支结构(不含循环结构),无论真或假,执行的次数都是恒定的
不会随着n的变大而发生变化,其时间复杂度也是O(1)
四、线性阶
for(let i=0;i<n;i++){
/* 这里是时间复杂度为O(1)的程序步骤序列*/
}关键就是要分析循环结构的运行情况
上面这是一个for循环,那么它的时间复杂度又是多少呢?首先循环体就是一个执行一次的循环体,总共执行了n次,那么执行次数就是f(n) =n,启动我们的游戏攻略三部曲知道,时间复杂度就是为O(n).
五、对数阶
let count=1;
while(count<n){
count=count*2
}对数阶不是很好理解
每次count都会乘以一个2，他会距离n更近一步
这里详细解释一下
count=1时 1<n count=2 2的一次方
count=2时 2<n count=4 2的二次方
count=4时 4<n count=8 2的三次方
…
到2的x次方大于n的时候 循环就结束了
由2的x次方等于n –> x = logn,时间复杂度为O(logn)
常见的二分查找就是以上思路，时间复杂度为O(logn).
六、平方阶
for(let i=0;i<n;i++){
for(let j=i+1;j<n;j++){
/* 这里是时间复杂度为O(1)的程序步骤序列*/
}
}由于当i = 0时,内循环执行n此,当n = 1时, 执行了 n – 1 次, …当 i = n-1 时, 执行了1次,所以总的执行次数为:
n + (n -1) +( n -2 ) +… +1 = n(n +1)/2 = n^2/2 + n/2
根据我们的游戏秘籍的三部曲(保留最高阶，去除最高阶不是1的常数项),我们可以分析出来,时间复杂度为 O( n^2 ).
七、常见算法时间复杂度
笔者最近看《大话数据结构》，总结了一点，最后一张图网上找的。需要《大话数据结构》pdf高清电子版的铁汁留言，我在评论区发你！
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/146697.html原文链接：https://javaforall.net
