[算法分析] （一）渐近分析

为什么要提到渐进分析？

我们有许多需要关心的方面，像是用户友好性，模块性，安全性，可维护性等等。为什么要关心性能？答案很简单，没有性能一切免谈。性能就像货币，我们可以通过它买到上述所有的东西。研究性能另一个原因是 —— 速度充满乐趣！
归根结底，性能就是指规模。想象一下一个文本编辑器能载入 1000 页，却只能每分钟检查 1 页的语法，又或者一个图像编辑器需要花 1 小时把你的图片向左旋转 90 度 …… 你应该懂我的意思了。如果一个软件不能应付用户需要执行的任务规模 —— 那就死定了。

同一个任务给定两种算法，我们怎么找出更好的那个？

一种朴素的方法就是实现这两种算法，然后在你的电脑上以不同的输入值运行这两个程序，看哪一个花费更少的时间。但这种分析方法有许多问题：

• 一个可能是对于某些输入值，第一种算法比第二种算法效率更高，对于另一些输入值则相反。
• 另一个可能是对于某些输入值，第一种算法在这台电脑上表现更好，在另一个电脑上则不尽然。

在算法分析中，渐近分析是解决上述问题的好主意。在渐近分析中，我们从输入规模的角度来评估一种算法的性能（而不是计算实际运行时间）。我们计算的是一种算法随着输入规模的增长，它所需要的时间（或空间）开销是多少。
举个例子，比如在一个有序列中的查询问题（查找一个给定值）。一种办法是线性查找（增长是线性的），另一种办法是二分查找（增长是对数级的）。为了理解渐近分析是如何解决上述问题的，我们可以假设线性查找在一台高速的电脑上运行而二分查找在一台低速的电脑上运行。对于小规模的有序列，高速的电脑可能花费更少的时间。但是，当有序列的规模达到一个特定值之后，二分查找一定会比线性查找更快一些，即便二分查找是在低速的电脑上运行。原因是二分查找的开销是对数级增长的，而线性查找是线性增长的。所以在特性的输入规模之后，机器相关的常数一般可以忽略不计。

渐近分析总是有效吗？

渐近分析并不完美，但它是算法分析中可行的最好的方法。例如，在同一台机器上，有两种排序算法分别开销为 $1000NLogN$ 和 $2NLogN$。它们是渐近相同的（增长级都是 $NLogN$）。所以，对于这种渐近分析结果，我们无法判断哪一个更好因为我们忽略了常数。
同样地，在渐近分析中，我们总是考虑输入规模大于常数的情况。很可能你的程序永远没有那样大的输入规模，或者一个分析得出较慢的算法总是在特定情形下效率更好。所以，你可能最终会选择一个在你程序中较快的算法即便分析结果指出它较慢。