大O时间复杂度

  • A+
所属分类:算法与数据结构

大O时间复杂度

大O时间复杂度,又称为渐进时间复杂度,简称时间复杂度。

公式

T(n) = O(f(n))

f(n)代表变量n的函数,O代表成正比,T(n)代表执行时间。

含义

代码执行时间随数据规模增长的变化趋势。

当n很大时,低阶、常数、系数三部分都不能左右增长趋势。

时间复杂度分析

1.只关注循环执行次数最多的一段代码

2.加法法则:总复杂度等于量级最大的那段代码的复杂度。

O(n^2) + O(n) = O(n^2)

只要是一段代码的循环次数已知,与n无关,都是常数级的执行时间。无论其循环次数多大,在n趋向无穷大时,都可以忽略。

3.乘法法则

常见时间复杂度量级

多项式量级

O(1)常数阶 O(logn)对数阶 O(n)线性阶 O(nlogn)线性对数阶 O(n^2)平方阶 O(n^3)立方阶

O(logn)对数阶:

i的取值为等比序列,执行次数设为x,则2^x=n,x = log(n)。

非多项式量级

O(2^n)指数阶 O(n!)阶乘阶

我们把非多项式量级的算法问题叫作NP(Non-Deterministic Polynomial, 非确定多项式)问题。

最好时间复杂度

最好的情况发生时的时间复杂度

最坏时间复杂度

最坏的情况发生时的时间复杂度

平均时间复杂度

即每种情况乘以其发生的概率所得到的时间复杂度,准确说应该叫做加权平均时间复杂度,或期望时间复杂度。

均摊时间复杂度

对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系,这个时候,我们就可以将这一组操作放在一块儿分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。而且,在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度。

 

空间复杂度

常见的有O(1)  O(n) O(n^2)

 

许龙涛

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: