最近一段时间有看一些关于算法的文章，主要是因为在leetcode跟warcode都有做过一些题目了。算法以前学过一些皮毛，但是还是会觉得不够，有些算法还是需要找很多资料花一些时间才能想明白。这里整理一些关于算法分析的笔记。
复杂度分析
什么是复杂度分析
数据结构和算法解决的是“如何让计算机更短时间，更省空间的解决问题”，因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
我们可以分别用时间复杂度和空间复杂度两个概念来描述算法的性能问题，这两个概念也统称为算法的复杂度分析。因此，算法的复杂度描述的是算法执行的时间或占用的空间与数据规模的增长关系。
为什么要做复杂度分析
其一，和性能测试相比，复杂度分析有不依赖执行环境，成本低，效率高，已操作，指导性强的特点。
其二，掌握复杂度分析，将有助于我们编写出性能更优的代码，有利于降低系统开发和维护成本。
如何计算复杂度
大O表示法
算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示其中T(n)表示内行代码执行的总次数，而n表示数据的规模。
以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶，低阶以及系数实际上对这种增长趋势不产生决定性的影响，所以在做时间复杂度分析时可以忽略这些项。
复杂度分析技巧：
单独一段代码，只需要找到最高频运行的代码分析，比如循环代码。
多段代码的分析，则取所有代码中最高频运行的代码分析，比如一段代码中同时有单循环和多重循环的，只需要分析多重循环的代码复杂度；即：如果T1(n) = O(f(n))， T2(n) = O(g(n))，则T(n) = T1(n) + T2(n) = max(O(f(n)), O(g(n))) = O(max(f(n), g(n)))。
嵌套代码的分析，可以先把嵌套拆分分析复杂度，再相乘。即：如果T1(n) = O(f(n))， T2(n) = O(g(n))，则T(n) = T1(n) x T2(n) = O(f(n) x g(n)) = O(f(n)) x O(g(n))。
多参数多段代码的分析，需要分别分析每个参数参与代码的复杂度，然后再相加。即：如果T1(n) = O(f(n))， T2(m) = O(g(m))，则T(n, m) = T1(n) + T2(m) = O(f(n)) + O(g(m))。
常见的时间复杂度
以下是一些常见的时间复杂度量级：
常量阶O(1)：常量阶一般指代码的时间复杂度不随n的增大而增长。
对数阶O(logn)，O(nlogn)：简单的例子：用while循环计算一个2的n次方，n是参数，其时间复杂度为O(logn)。
线性阶O(n)：线性阶指代码的时间复杂度跟n成比例。
平方阶O(n^2)，立方阶O(n^3)：平方阶跟立方阶都是随n的增大而呈现高倍增长。
非多项式阶-指数阶O(2^n)，阶乘阶O(n!)：非多项式阶的时间复杂度会随着数据的规模增长而大幅度增长，所以这类算法的性能都很差。
空间复杂度
一般来说，提及复杂度分析主要指的是事件复杂度分析。但是实际还有空间复杂度分析。空间复杂度全程为渐进空间复杂度，表示算法的储存空间与数据规模之间的增长关系。同样是使用大O表示法，但是分析的是存储空间。