计算机算法分析与算法比较

    1.2.3　计算机算法分析与算法比较

    （1）对任一给定问题，一般可研究出多种解法；对一种给定解法，通常可设计出多个计算方法；对一种给定计算方法，通常可构造出多个算法；对一个给定算法，往往可编写出多个程序。

    （2）程序效率（包括时间效率、空间效率）源自算法效率。要从解决同一问题的多个算法（含其程序）构成的算法族（含其程序族）中，挑选出求解有效、效率最高、效果最好的算法，需对这些算法进行评估、分析与比较。算法分析（Algorithm Analysis）是估量一个算法效率的重要办法，它可定量研究算法自身效率的高低，且可度量问题内在复杂程度。

    美国计算机科学家N. Worth教授提出的著名公式“程序 = 算法 + 数据结构”表明，让计算机完成解题任务，除了要选取适当的数据结构外，还需要设计基于所选数据结构的相应算法。实际上，程序可视为是在所论数据的某些描述方式和表示结构的基础上对抽象算法的计算机语言的具体表达。事实上，在为解决同一问题而选择适当数据结构后，设计思路不同的算法对解决问题好坏程度（例如时空效率、计算精度等）影响很大。要更好更快地解决所论问题，就须不断改进和提高算法效率。

    一、算法效率与问题规模

    算法执行效率（简称算法效率），需凭借依据算法而编制出的程序运行时所耗用计算机资源（包括所占用的运行时间和存储空间）程度来度量。因此，算法效率可细分为时间效率与空间效率，算法复杂度（也称算法复杂性）可细分为时间复杂度（也称时间复杂性）和空间复杂度（也称空间复杂性）。

    算法复杂度与其所论问题规模有关。问题规模用以表征算法所论问题大小的数量级。

    定义1.1　算法所论问题中的基本研究要素个数n（它为非负整数），称为问题规模。

    显然，问题规模与算法所要解决的问题本身直接相关。例如：算法所要解决的行列式问题，其问题规模可用基本研究要素“行列式的阶数n”来表示；算法所要解决的图论问题，其问题规模可用基本研究要素“图的边数n”或“图的顶点数n”来表示；算法所要解决的平面凸壳问题，其问题规模可用基本研究要素“平面凸壳所覆盖二维点的个数n”来表示等等。

    二、算法分析基本准则

    为了分析、评价一个算法的优劣，或者说完成对诸多（解决某一问题的若干算法的）算法效率的评估、比较，首先要确认一组基本的判别准则；其次要针对问题的特点，确定哪些准则更重要。但有时我们又不得不在这些准则之间进行某种权衡与折中，以适应用户所提出的要求。因此，设计一个“好”的算法，一般至少应考虑以下算法分析准则。

    1．正确性的有无

    一个算法正确，是指对于一切合法的输入数据，该算法经过有限时间（算法意义上的有限）的执行都能产生正确（或者说满足规格说明要求）的结果。

    一个算法包括两方面的基本内容：一是解决问题的基本方法，二是实现这些方法的一系列操作（包括指令，语句，步骤）。要确认一个算法所用方法、公式、步骤等的正确性，可能需要一组相关的定理和公理，同时更需要证明这些操作确实既符合算法规定，又可解决问题。对较简单算法的正确证明，则须用一些不太严格的证明方法（事实上，这已足够了）；但对较复杂算法的正确证明，则须可用严格的形式化证明方法。当然，如果待证明的算法可以分成一些能独立验证的算法段，其正确性证明就能够被“分而治之，聚而完成”。故倘若时间、条件、成本允许，人们常将一个较复杂算法分成一些既短小又简单的算法段，然后再逐一证明这些算法段的正确性。

    应当强调指出的是算法的正确性证明，比算法的正确化设计要复杂得多、重要得多、困难得多。实际上，算法正确性证明（指严格的形式化证明）难度高，且极重要，迄今尚未突破，仍令人望而生畏，但又充满魅力。

    2．执行时间的多少

    算法的时间复杂度，是指算法所需用的执行时间数量。它显然越少越好。

    为了评估和计算一个算法的执行时间，应该选择一种“对解决同一个问题的诸多算法，均可用它来度量其时间复杂度的有效评估、计算和比较”的时间复杂度测度方法。

    既然：

    （1）如果所选择的度量能表示被比较的诸多算法的实际执行时间，则是比较方便的，但它的一个明显缺点是其实际执行时间将随着所用的计算机系统不同而改变；因而，不同计算机系统执行时间的差异性，并不代表其算法时间复杂度的差别性；

    （2）如果代之以一个算法所执行的语句条数，则人们又会发现这一度量在很大程度上依赖于算法设计者所用算法描述工具及其算法设计风格，从而缺乏可比性。

    因此，人们期待的时间复杂度测度方法，必须满足：

    （1）它能告诉人们算法所用方法（包括其数据结构）的时间效率；

    （2）它与算法描述工具（或所用程序设计语言）及其设计风格无关；

    （3）它与算法实现过程中的许多细节（诸如“增加循环下标，计算数组下标，设置数据结构指针，标记必要数据、中间结果”等簿记运算）无关；

    （4）它应该足够精确和具有通用性（或一般性）。

    据此，在许多情况下，为了便于分析某一算法，可将那些对所研究的问题（或对所论算法）来说是基本的操作（或运算）分离出来，而忽略其他簿记等细节问题，仅仅计算其基本运算的次数。因此，算法的时间复杂度，通常可用其基本运算次数来度量。

    不过，还应强调的是，一个算法所执行的基本运算次数，常常因输入不同而不同。算法所执行的基本运算次数，不仅取决于输入数据元素的个数（也简称为输入规模、或输入的大小等，系指一个输入所包含的输入数据的个数），而且也与输入数据的性质有关。

    3．存储空间的大小

    算法的空间复杂度，是指算法所占用的存储空间数量。它显然越小越好。

    算法执行总需占用必要的存储空间，以存放该算法本身包含的操作（及其语句），常数、变量、输入数据和实现其运算所需要的数据（包括中间结果等）；此外，还需占用一些工作空间，以利于对数据进行处理（例如某种存储处理）。算法所占用存储空间数量，既与算法所采用的数据结构、设计策略以及输入数据的性质、规模、方式等有关，也与算法执行时刻有关（即不同时刻所占用空间的数量不尽相同）。

    一个算法所需的执行时间和存储空间，其数量常常存在“此增彼减”的制约关系；而算法的时间复杂度，通常比算法的空间复杂度更为重要。事实上，在人们为解决具体问题而设计算法的实践中，一般会在算法所需执行时间和所占存储空间之间进行必要权衡，有时可用适当增加存储空间占用量来有效降低执行时间复杂度；有时会被迫以增加执行时间为代价来尽量减少其存储空间占用量。

    4．可读性的好坏

    算法的可读性（或称易读性）是指算法的可读（或易读）性质。可读性好的算法，思路清晰、逻辑合理、简明易懂，有助于设计者和他人在现在和将来进行阅读、理解、修改、使用和重用。反之，晦涩难懂的算法易于藏匿错误、隐蔽危险，徒增人们阅读、理解、调试、修改、使用和重用该算法的困难。

    5．坚固性的强弱

    当出现非法错误时，算法能适时和实时地作出正确反映（既不会简单拒绝错误，也不会听任错误流传）。例如，一个坚固性好的算法，能对所输入数据进行错误侦察（如语法检查、语义检验），发现错误时能提出具体修改建议，并给用户提供机会重新输入数据。

    6．其他性能要求

    一个好算法，还应具有灵活性（Rlexibility）、重用性（Reusabiluty）和自适应性（Adaptability）。

    上述算法分析准则要求：

    （1）正确性。这是任何算法设计者必须确保的基本前提，也是保障其他各准则有效的基础，因为离开了正确性，其他的一切就无从谈起。

    （2）算法效率。这是一切算法设计者所追寻的既定目标，因为一个算法的效率高低，往往决定着该算法实用价值的有无与大小。一般情况下，时间效率比空间效率更受关注，时间复杂度比空间复杂度更加重要。

    三、最优算法基本定义

    人们现已认同，在假定算法正确前提下，可以规定“用时间复杂度作为评价算法优劣的标准”。据此共识，最优算法可定义如下。

    定义1.2　记SA是解决同一问题全部算法所构成的算法集合。如果存在某算法ASA∈，对任一算法XSA∈，均有算法A的基本运算次数总不大于算法X的基本运算次数，则称算法A是算法集SA中基于时间复杂度的最优算法。

    应当明确指出：

    （1）要证明一个算法正确，已非易事；而要证明一个算法最优，尤其不易。

    （2）如果能给出解决同一问题所需要的基本运算次数的下确界，则任一个基本运算次数等于下确界的算法都将是最优的。

    （3）基于规定“用空间复杂度作为评价算法优劣的标准”，也可仿此来定义基于时间复杂度的最优算法。