# 算法分析
在计算机科学中，算法分析（Analysis of algorithm）是分析解决计算问题所需任何算法执行所需计算资源（计算时间、内存空间等）或者复杂度的过程。算法分析一词由著名的计算机科学家高德纳创造，是计算复杂度理论重要的组成部分。
著名的摩尔定律定律告诉我们，计算机的计算速度和内存容量每 18 个月都会翻一倍。但是，这些计算机资源并不是无限的，我们通过算法分析寻找一种高效的算法在有限资源情况下可以提升程序的性能。
算法的效率或者复杂度在理论上可以通过函数描述算法的输入规模与时间复杂度或空间复杂度之间的增长关系，这里我们只关心算法的时间复杂度。
一般来说，算法的运行时间与输入规模呈同步增长趋势。
相同规模不同的输入可能导致算法运行时间发生变化，这需要在最好、最坏、平均和均摊情况下分析算法的运行时间。一个算法的上限往往取决于它最坏情况的运行时间，可以通过摊还分析来保证最坏情况下每个操作的平均性能；在某种特定情况下，我们将会考虑算法平均情况的运行时间，这需要用到随机化算法和概率分析，从而得到一个期望的运行时间。
在任意规模输入情况下，可以通过渐进符号大 O 或者其他符号来表示算法渐进的运行时间。
通过大 O 表示法可以将算法的增长数量级表示为：常数阶 O(1)、对数阶 O(logn)、线性阶 O(n)、线性对数阶 O(nlogn)、平方阶 O(n2)、指数阶 O(2n) 等。
注：具体的算法分析过程将会在各算法中详细说明。
# 参考
- Wikipedia (opens new window)
- 《算法导论》
- 《算法》（第4版）
- 《数据结构与算法之美》