1. 算法复杂度的今生今世

1.1 什么是算法

算法是一个抽象的概念。可以理解为：一组输入数据经过正确、确定、可行的有限步运算后得到的输出结果，中间的正确、确定、可行的有限步运算就是我们所说的算法。

需要注意的是，正确性、确定性、可行性和有穷性由数学问题的性质决定的，而不是程序的特点。举一个例子，hailstone序列：

根据定义，你可能直接写出程序：

但是，这样你从源头上就错了，先不考虑程序，针对于这个问题，你能确保给定任意一个数，其序列的长度是有限的？也就是是否对于任意n，都有 |Hailstone(n)| < ∞，然而，这个问题到现在都还被解决，是一个不确定问题，不符合有穷性，所以其不是一个算法。自然的，对于上面的程序也不是一个算法程序。
所以，平时在写算法程序时遇到死循环或者栈溢出时，可能不是程序的问题，可能是该问题本质上就不能用一个算法解决。

结论：

算法的正确性、确定性、可行性和有穷性是数学问题的性质决定的，而不是程序决定的。即程序 != 算法

但是，由于我们平时关注更多的是程序方面的算法实现，所以，后续说算法指算法程序。

1.2 如何衡量算法的好坏

衡量算法好坏：先满足时间复杂度最低，再去考虑空间复杂度最低。

但是，需要注意：算法的最优解并不意味着实际情况的最优解。 比如：

当计量非常大时，应该将时间复杂度最优，将空间复杂度降低，以空间换时间。

当计量不是很大时，应该找时间复杂度与空间复杂度的平衡。尽可能双双压低。

如果空间不充足的情况下，可以考虑时间换空间。

例子：

1.2.1 时间复杂度

时间复杂度的3个标记：

O( )：用来定义最坏的趋势。求解步骤：

得到计算公式后求极限

忽略常数和系数

Ω( )：用来定义最好的趋势。求解步骤：

得到计算公式后求极限

忽略常数和系数

θ( )：用来定义平均的趋势。求解步骤： θ取夹在 Ω 与 O 中间的数。比如：Ω(1) < θ < O(n)，则有θ(n^0.5) 或 θ(n^0.3) 等等

注意：通常使用O来衡量算法的复杂度，而不是θ。

① 当两个算法的O不相等时，O小的效率更高。
② 当两个算法的O相等时，理论上需要看基本操作的常数时间，常数时间小的效率高。但是，在实际开发中可以将两个算法分别其运行很多次，并直接比较运行时间。