数据结构和算法学习总结 - 复杂度分析

数据结构和算法要解决的问题，1 是快，2 是省。

1.快，让代码运行的更快，代码具有更低的时间复杂度。 

2.省，让代码更省存储空间，代码具有更低的空间复杂度。

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

一、什么是复杂度分析？

1.数据结构和算法解决的是“如何让计算机更快时间、更省空间的解决问题”。

2.从执行时间和占用空间两个维度来评估数据结构和算法的性能。

3.分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。

4.复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。

二、为什么要进行复杂度分析？ 

1.和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。

2.掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

三、如何进行复杂度分析？

1.大 O 表示法

1）来源算法的执行时间与每行代码的执行次数成正比，用 T(n) = O(f(n))表示，其中 T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而 n 往往表示数据的规模。

2）特点：以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时可忽略这几项。

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

4）当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：

T(n) = O(n)； T(n) = O(n2)。

下面我们分别来看一下各种复杂度分析的相关代码，如下：

 O(1)

int n = 1000; 
System.out.println("Hey - your input is: " + n);

O(n)

for (int = 1; i<=n; i++) {  System.out.println(“Hey - I'm busy looking at: " + i); }

O(n^2)

for (int i = 1; i <= n; i++) { for (int j = 1; j <=n; j++) {  System.out.println("Hey - I'm busy looking at: " + i + " and " + j);  } }

O(log(n))

for (int i = 1; i < n; i = i * 2) {  System.out.println("Hey - I'm busy looking at: " + i); }

O(K^n)

for (int i = 1; i <= Math.pow(2, n); i++){  System.out.println("Hey - I'm busy looking at: " + i); }

O(n!)

for (int i = 1; i <= factorial(n); i++){  System.out.println("Hey - I'm busy looking at: " + i); }

2.复杂度分析法则

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

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

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

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

四、常用的复杂度级别？ 

多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶） 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括， O(2^n)（指数阶）、O(n!)（阶乘阶）。

五、复杂度分析方法有哪些？

5.1 复杂度分析的 4 个概念

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

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

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

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

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

用代码在所有情况下执行的次数的加权平均值表示。

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

在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

5.2 为什么要引入这 4 个概念？

1.同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这 4 个概念。

2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。

5.3 如何分析平均、均摊时间复杂度？

1.平均时间复杂度

代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。

2.均摊时间复杂度

两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

六、如何掌握好复杂度分析方法？ 复杂度分析关键在于多练，所谓孰能生巧。推荐算法练习网站，“全球极客挚爱的技术成长平台”leetCode。多看牛人的优秀代码，不断精进与提升我们的“码感”。

leetCode 中文站：https://leetcode-cn.com/problemset/all/

leetCode：https://leetcode.com/problemset/all/