一个算法就是解决某个问题需要遵循的一套描述清晰的指令集。
一旦给出某个问题的算法且判断该算法是正确的后，一个非常重要的步骤就是分析该算法需要多少资源，比如时间或者空间等。
一个能解决问题但需要一年的时间的算法是毫无意义的。
一个能解决问题但需要成百上千G内存的算法是毫无意义的。
在这一章，我们将会学到
- 如何估计一个程序的运行时间？
- 如何将一个程序的运行时间从年或者天缩减到秒？
- 滥用递归会带来什么后果？
- 针对求一个数的幂次方和两个数的最大公约数，都有哪些有效的算法？
算法分析所需的数学知识
关键词 相对阶 相对增长速率
如何确定函数的相对阶？
一般来说，给定两个函数f(n)和g(n)，总存在点使得f(n)<g(n)。基于这些点就判断f(n)<g(n)是没有意义的。
所以，确定函数的相对阶就是比较两个函数的相对增长速率。
函数相对增长速率分类
- 小于等于
- 大于等于
- 等于
- 严格小于
例1 证明：1000N=O(N^2)
