第2章 算法分析

一个算法就是解决某个问题需要遵循的一套描述清晰的指令集。

一旦给出某个问题的算法且判断该算法是正确的后，一个非常重要的步骤就是分析该算法需要多少资源，比如时间或者空间等。

一个能解决问题但需要一年的时间的算法是毫无意义的。

一个能解决问题但需要成百上千G内存的算法是毫无意义的。

在这一章，我们将会学到

• 如何估计一个程序的运行时间？
• 如何将一个程序的运行时间从年或者天缩减到秒？
• 滥用递归会带来什么后果？
• 针对求一个数的幂次方和两个数的最大公约数，都有哪些有效的算法？

算法分析所需的数学知识

关键词 相对阶 相对增长速率

如何确定函数的相对阶？
一般来说，给定两个函数f(n)和g(n)，总存在点使得f(n)<g(n)。基于这些点就判断f(n)<g(n)是没有意义的。
所以，确定函数的相对阶就是比较两个函数的相对增长速率。

函数相对增长速率分类

• 小于等于
• 大于等于
• 等于
• 严格小于

例1 证明：1000N=O(N^2)