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

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

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

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

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

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

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

复杂度分析

（What）复杂度分析的是什么？

复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容就掌握了一般

（Why）为什么要进行复杂度分析？

弥补事后统计法的不足

1、测试结果非常以来测试环境

2、测试规模受数据规模的影响很大

（How）怎么进行复杂度分析？

一、大O复杂度分析法

假设条件：假设每行代码执行的时间都一样，为unit_time

示例1:

所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

时间复杂度分析

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

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

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

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

对于非多项式量级只有两个：O(2^n) 和 O(n!)

常见的多项级时间复杂度

1. O(1)

2. O(logn)、O(nlogn)

3. O(m+n)、O(m*n)

空间复杂度