[科普中国]-有效算法

概述

对于那些不熟悉计算机的人来说，可以使用别人已设计好的现成算法，只需根据算法的要求给予必要的输入，就能得到输出的结果。对他们来说，算法如同一个“黑箱子”一样，他们可以不了解“黑箱子”中的结构，只是从外部特性上了解算法的作用，即可方便地使用算法。例如，对一个“输入3个数，求其中最大值”的算法，只要输入a,b,c这三个数，执行算法后就能得到其中最大的数。但对于程序设计人员来说，必须会设计算法，并且根据算法编写程序1。

正确认识存在这样一类问题，其目前最快算法所需计算次数是n的指数函数而非多项式，所以n略大时，计算机就不能胜任，故以其在计算上难于对付而闻名，被称为NP-Complete问题，如旅行售货员问题、时间表问题等。数学家强烈的认为：人们不可能找出一个有效算法这一事实是NP-Complete问题的固有性质。他们相信，不会有有效算法存在（如其一具有有效算法，余者皆然）。因此，对这类问题，寻找近似解的有效算法便自然成为人们追求的方向。

然而，对算法的认识并未到此结束，人们很快发现上述复杂性概念涉及到算法在最坏的情况下的性态。而这种最坏情况在实际中发生的概率究竟有多大并未予以考虑，以致出现了多项式算法反倒不如非多项式算法在实算中的奇怪现象。例如，单纯形算法已被证明是普遍实用和非常有效的，但人们也举例证明了它不是多项式算法，哈奇杨算法已被证明是多项式算法，但在许多实践中，其计算速度反比单纯性算法慢得多。这说明用算法在最坏的情况下的性态来区别好坏不是科学的，而算法的平均性态才是衡量算法好坏的最有说服力、最重要的标志。因此，那种近凭一、两个并不具有代表性的例子来肯定或否定一种的算法的思想和行为是不可取的。

对于解决同一类问题的各种算法，优劣立判的算法并不常见，往往是尺短寸长，各有特点。方法一可能在解决A类问题上更有效，方法二可能在解决B子类问题上更优越，应当实事求是的进行具体分析，不宜简单肯定而否定另一种。那种认为某类问题已有有效算法，从而对新提出的算法一概采取轻视，过于挑剔甚至怀疑的态度，这对算法的发展是有害的。对算法也应采取”百花齐放，推陈出新“的方针，特别是对比较成熟的领域的算法，哪怕是稍微有所改进，也可能产生较大的经济效益，因此更加不能忽视。

算法的发展是没有穷尽的，人们对算法的认识也在逐渐深入，期待着有更好的好算法出现，为社会服务，为人类造福2。

其他特点出了有效性，算法还应该具备一下特点：

1、有穷性。一个算法应包含有限的操作步骤，而不是无限的。

2、确定性。算法中的每一个步骤都应当是确定的，而不应是含糊的、模棱两可的。

3、有零个或多个输入。所谓输入指在执行算法时需要从外界取得必要的信息。

4、有一个或多个输出。算法的目的就是为了求解，”解“就是输出。