筛选极客时间上面算法专栏提到的书籍，在此处备注，待后面学习
1：入门
《图解算法》、《大话数据结构》
2：面试
《编程之美》、《剑指offer》、《编程珠玑》
3：编程语言
《数据结构与算法分析：Java语言描述》、严蔚敏《数据结构》
4：闲暇阅读
《算法帝国》、《数学之美》、《算法之美》
5：经典大部头
《算法导论》、《算法》
6：殿堂级
《计算机程序设计艺术》
7：数学基础：
《离散数学及其应用》
高德纳《具体数学》

数据结构与算法

数据结构是为算法服务的；算法要建立在特定的数据结构之上。

从极客时间算法专栏得到的图片

从广义上讲，数据结构就是一组数据的存储结构。算法就是操作数据的一组方法。
考量数据结构和算法的效率和资源消耗的方法：复杂度分析法。

时间、空间复杂度分析

什么是复杂度分析？

1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
3.分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
4.复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。

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

1.和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
2.掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

大O复杂度表示法

简述

大 O 时间复杂度表示法：并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
1）来源
算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。
2）特点
以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽略这些项。

时间复杂度分析

1. 只关注循环执行次数最多的一段代码
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

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

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )。

常用的复杂度级别

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

一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
O(m+n)、O(m*n) ：v代码的复杂度由两个数据的规模来决定

空间复杂度分析

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
常见空间复杂度：O(1)、O(n)、O(n^2)、

最好情况复杂度（beat case time complexity）：最理想的情况下，执行这段代码的时间复杂度。
最坏情况复杂度（worst case time complexity）：最糟糕的情况下，执行这段代码的之间复杂度。
平均情况复杂度（average case time complexity）（加权平均时间复杂度或期望时间复杂度）。代码在所有情况下执行的次数的加权平均值表示。
均摊时间复杂度（amortized time complexity）（摊还分析、平摊分析）：一般使用摊还分析法进行分析，在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。一般情况下，均摊时间复杂度就等于最好情况时间复杂度。

注意

1，在大O表示法中，常量的影响可能很大，例如对快速排序和合并排序，快速查找的常量比合并查找小，因此如果它们的长度和运行时间都为O(n log n)，快速查找的速度将更快。实际上，快速查找的速度确实更快，因为相对于遇上最糟情况，它遇上平均情况的可能性要大得多。