2.3　证比求易算法

为了更好地理解计算复杂性的有关概念，我国学者洪加威曾经讲了一个被人称为“证比求易算法”的童话，用来帮助读者理解计算复杂性的有关概念，大致内容如下。

从前，有一个酷爱数学的年轻国王艾述向邻国一位聪明美丽的公主秋碧贞楠求婚。公主出了这样一道题：求出48 770 428 433 377 171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。

国王回去后立即开始逐个数地进行计算，他从早到晚，共算了3万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很快就验证了这个数确能除尽48 770 428 433 377 171。公主说：“我再给你一次机会，如果还求不出，将来你只好做我的证婚人了。”

国王立即回国，并向时任宰相的大数学家孔唤石求教，大数学家在仔细地思考后认为这个数为17位，则最小的一个真因子不会超过9位，于是他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。最后，国王用这个办法求婚成功。

在“证比求易算法”的故事中，国王最先使用的是一种顺序算法，其复杂性表现在时间方面，后面由宰相提出的是一种并行算法，其复杂性表现在空间方面。直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，因而大大地限制了并行计算机系统的加速能力。下面用阿姆达尔（G.Amdahl）定律来说明这个问题。

设f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p为处理器的数目，Sp为并行计算机系统最大的加速能力（单位：倍），则

设f=1%，p→∞，则Sp=100。这说明在并行计算机系统中即使有无穷多个处理器，若串行执行操作占全部操作的1%，则其解题速度与单处理器的计算机相比最多也只能提高100倍。因此，对难解性问题而言，单纯地提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题。