复杂度

复杂度包括 时间复杂度 和 空间复杂度

一般来说，时间复杂度是我们比较关心和重要的，因为都是用空间换时间

时间复杂度表示代码执行时间随数据规模增长的变化趋势，表示方法图所示：

大 O 表示法：我们在分析时间复杂度的时候往往遵循以下原则：

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

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

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

如果某个算法的时间复杂度是 T(n) = O(2n+2) 或 T(n) = O(2n^2 +2n+3)

则公式中的低阶、常量、系数三部分都可以忽略，即：T(n) = O(n) 和 T(n) = O(n^2)

常见时间复杂度如下图所示：

时间复杂度里细分起来又有最好、最坏、平均情况时间复杂度之分：

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

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

• 3、平均情况时间复杂度顾名思义就是结合概率论分析从最好到最坏每种情况平均下来的加权平均时间复杂度