前言:为什么要分析算法的复杂度

1. 测试结果非常依赖测试环境:如硬件影响结果

2. 测试结果受数据规模的影响很大:如数据排序,本身数据的有序程度影响结果

所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。这就是时间、空间复杂度分析方法。

时间复杂度

代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。一般称大 O 时间复杂度表示法

大 O 时间复杂度表示法

其中，T(n) 表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

时间复杂度分析

1.单段代码看高频：比如循环。

2.多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。

3.多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

4.嵌套代码求乘积：比如递归、多重循环等

几种常见的时间复杂度实例分析

常见时间复杂度 常见时间复杂度效率

非多项式量级

随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，

O(2^n)（指数阶）、O(n!)（阶乘阶）

多项式量级

随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，

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

空间复杂度分析

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。

最好情况时间复杂度（best case time complexity）

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

最坏情况时间复杂度（worst case time complexity)

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

平均情况时间复杂度（average case time complexity）

实际上，在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。像我们上一节课举的那些例子那样，很多时候，我们使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。

均摊时间复杂度（amortized time complexity）

摊还分析(平摊分析)

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