本文共 1046 字，大约阅读时间需要 3 分钟。

原文地址：

为什么要做性能分析？

这里呢有许多东西需要考虑，比如用户的友好度，模块化，安全性，以及可维护性等等。为啥就不考虑考虑性能呢？

答案很简单，如果我们拥有了性能，那么上面提到的东西也就有了。所以性能就像货币一样，用它我们可以买到上面提到的所有东西。另外学习性能的原因就是——速度超有趣！

对一个任务的两种算法，我们怎样才能确定哪个更好呢？

一个最普通的方法就是：实现两种算法，然后用不同的输入在你的计算机上跑跑，看看哪个用的时间更少。但是这种分析算法的方法存在很多问题。

1）对于一些输入，第一个算法可能比第二个快，对于另外一些输入呢，第二个又比第一个好。

2）也有可能对于一些输入，第一个算法在一个机器上比第二个算法好，但是在另一台机器上第二个又比第一个好。

渐近分析是一个大问题，它就是在算法分析中处理上面的问题的。在渐近分析中，我们用输入的大小来评估算法的性能（我们不测量具体的运行时间）。我们计算的是随着输入大小的增加，算法所需要的时间（或者空间）。例如，我们考虑一个有序数组的搜索问题（搜索一个指定项）。

一个方法就是线性查询（递增顺序是线性的），另一个方法就是二分查询（递增顺序是对数级的）。为了能够很好滴理解渐近分析是怎样在算法分析中解决上面提到的问题，我们假设让线性查找在一个快的机器上跑，而让二分查询在一个慢的机器上跑。对于输入数组的大小比较小的时候，那么快的计算机花费的时间可能较少。但是，当输入的数组大小增长到一定程度的时候，二分查询的花费时间毫无疑问要比线性查询花费的时间要少，尽管二分查询是在比较挫的机器上跑的。原因是对递增数组进行二分查询对于输入的大小是对数级的，而线性查询则是线性级的。所以在特定的输入大小之后，机器的本身是可以忽略的。

渐近分析总是有效吗？

渐近分析不是完美的，但是它是分析算法的最好方法。例如，有两个排序算法，在同一台机器上分别花费1000nLogn与2nLogn的时间。这两个算法的进行线是相同的（递增方向是nLogn）。所以，用渐近分析，我们不能判定哪个更好，因为我们忽略了渐近分析的常量。

另外在渐近分析中，我们总是讨论输入的大小多余常量值。你的软件或者算法可能永远不会用到这么量大的输入，虽然你的算法渐近是更慢的，但是它在你特定的情况下工作是很有效的，所以你可以不用为你的软件把渐近更慢的算法替换为更快的算法。

参考：

MIT’ s Video lecture 1 on Introduction to Algorithms.

转载地址：http://nwhii.baihongyu.com/