数据结构与算法-复杂度分析

一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率(代码执行的时间)的方法

所有代码的执行时间T(n)与每行代码的执行次数n成正比，公式:T(n) = O(f(n))

T(n):表示代码执行的时间；

n:表示数据规模的大小；

f(n):表示每行代码执行的次数总和。因为这是一个公式，所以用f(n)来表示；

O:表示代码的执行时间T(n)与f(n)表达式成正比

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增⻓的变化趋势，所以也叫作渐进时间复杂度，简称时间复杂度。

复杂度量级

1.多项式量级

量级递增:常量阶(O(1)) < 对数阶(Olog(n)) < 线性阶(O(n)) < 线性对数阶(O(nlog(n))) < 平方阶(O2) < 立方阶(O3) < K次方阶(Ok)

常量阶(O(1)):

一般情况下，只要算法中不存在循环、递归语句，即使有上万行代码，复杂度也是Ο(1)

对数阶(Olog(n)) :

在对数阶时间复杂度表示方法，我们忽略对数的“底”，统一表示O(logn)。

线性阶(O(n)):

线性对数阶(O(nlog(n))):

非常常⻅的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是O(nlogn)

平方阶(O2):

立方阶(O3):

K次方阶(Ok):

2.非多项式量级

量级递增: 指数阶(O(2)) < 阶乘阶(O(n!))

当数据规模n越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增⻓。所以非多项式时间复杂度的算法其实是非常低效的算法。

基础分析方式:

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

我们通常忽略公式中的常量、低阶、系数，只记录一个最大阶的量级。所以我们在分析一个算法/代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以。

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

3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

复杂分析方式: 为了表示代码在不同情况下的不同时间复杂度

1.最好情况时间复杂度:在最理想的情况下，执行这段代码的时间复杂度

2.最坏情况时间复杂度:在最糟糕的情况下，执行这段代码的时间复杂度

3.平均情况时间复杂度:全称应该叫加权平均时间复杂度或者期望时间复杂度

计算过程中引入概率,计算结果用大O表示法来表示，去掉系数和常量

4.均摊时间复杂度:是一种特殊的平均情况时间复杂度

摊还分析法:

将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上

能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度等于最好情况时间复杂度

渐进空间复杂度，表示算法的存储空间与数据规模之间的增⻓关系。

量级递增: O(1) > O(logn) > O(n) > O(nlogn) > O(n2)

最后编辑于：2020.05.05 19:23:06