为什么我们要寻找“多项式算法”

通俗地讲，算法就是解决问题的方法。求解同一个问题，可以有好多种不同的算法。让我们来看一个简单的例子。

已知n个数，a₁，a₂，…，a_n，要求找出其中最大的数。

方法一：根据给出这几个数的顺序，将a₁，与其余n-1个数比大小，如果发现有一个数比a₁大，说明a₁不是最大数。

于是，让a₂与其余n-1个数比较……以此类推，最后一定能找出最大数。

方法二：先让a₁与a₂比较，如果a₁＞a₂，则让a₁与a₃比较，否则a₂与a₃比较。在a₁与a₃或a₂与a₃中再挑选一个大的数与a₄比较……这样，在每次比较的两个数中，总有一个是在以前比较过的数中最大的。因此，只需比较n-1次便能找到其中最大的数。

哪种方法更合理呢?显然是方法二。它进行比较的次数比方法一少。当n很大时，它比方法一能更快地得到结果。正因为算法有好有坏，所以在设计解决问题的具体算法时，人们都希望找到一种迅速便捷的好算法。那么，如何衡量算法的好坏呢?什么是好的算法呢？

衡量一个算法好坏的标准之一，就是计算机执行算法所耗费时间的长短。在上面的例子中，当n很大很大时，显然方法二比方法一解决问题所用的时间要短。一般地，我们把算法所要求解决问题的初始数据量称为问题的规模。如上例，它的规模为n。执行算法的时间耗费可用规模n的表达式表示，如方法二，它的时间耗费量就是n-1。

通常，多项式算法是我们追求的目标。所谓多项式算法，是指它的时间耗费是规模n的一个多项式。相对于指数算法（时间耗费是规模n的指数表达式），它大大节约了计算机执行程序的时间。下表是两种算法耗费时间的比较，其中n表示问题规模。

可以看出，当n越来越大时，指数算法的耗费时间越来越多。尽管计算机速度很快，我国的银河亿次机每秒能计算1亿次，但指数函数的增长速度实在是太惊人了。假定我们用每秒10万次的计算机计算时间耗费量为2³⁰的算法，所需时间大约为10⁴秒，也就是将近3个小时，这还能接受。倘若时间耗费为2¹⁵⁰、2¹⁰⁰⁰呢？计算机可就束手无策、无能为力了。

因此，计算机并不能解决一切数据庞大、操作繁复的计算问题。求解问题的关键是寻找计算机能接受的算法，这也是我们寻找多项式算法的原因所在。

关键词：算法 多项式算法