时间复杂度与空间复杂度

算法的 “时间复杂度” 和“空间复杂度”合称为算法的复杂度。

时间复杂度

时间复杂度的定义可以参考以下我列下的几篇博客。

计算机科学家用于表示用于一个算法的效率或计算复杂度的一种表示法，叫作大O表示法（big-O notation）。“O”表示“on the order of（在……阶）”，这是对算法工作量的复杂度的级别的一种表示。例如，一个线性时间算法的阶是O(n)。大O表示法将我们对复杂度的阶的讨论形式化。

按数量级递增排列，常见的时间复杂度有：常数阶O(1)$O(1)$，对数阶O(log2n)$O(lo{g}_{2}n)$，线性阶O(n)$O(n)$，线性对数阶O(nlog2n)$O(nlo{g}_{2}n)$，平方阶O(n2)$O(n^2)$，立方阶O(n3)$O(n^3)$，…，k次方阶O(nk)$O(n^k)$，指数阶O(2n)$O(2^n)$。随着问题规模n的不断增大，算法的执行效率越低。

下表列出一些复杂度阶的示例：

下图列出了常用的时间复杂度的图例

空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。　　
（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))　　其中n为问题的规模，S(n)表示空间复杂度。

参考：
https://blog.csdn.net/booirror/article/details/7707551
https://blog.csdn.net/zolalad/article/details/11848739
https://www.jianshu.com/p/589a49ad2360
https://segmentfault.com/a/1190000003074973
http://www.voidcn.com/article/p-fcxbgkfc-st.html