第5章 算法与复杂性
习 题
一、选择题
1. B 2. D 3. C 4. A 5. B
6. B 7. D 8. C 9. A 10. A
二、简答题
1．什么是算法，算法的特性有哪些？
答：“算法(Algorithm)是一组明确的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果”。算法的特性有：
(1) 有穷性(可终止性)：一个算法必须在有限个操作步骤内以及合理的有限时间内执行完成。
(2) 确定性：算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。
(3) 有效性(可执行性)：算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。
(4) 输入及输出：一个算法应该有零个或多个输入数据、有1个或多个输出数据。
2．什么是算法的时间复杂度和空间复杂度，如何表示？
答：时间复杂度是与求解问题规模、算法输入相关的函数，该函数表示算法运行所花费的时间。记为，T(n)，其中，n代表求解问题的规模。
算法的空间复杂度(Space complexity)度量算法的空间复杂性、即执行算法的程序在计算机中运行所占用空间的大小。简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。记为，S(n)，其中，n代表求解问题的规模。
时间复杂度和空间复杂度同样，引入符号“O”来表示T(n)、S(n)与求解问题规模n之间的数量级关系。
3．用图示法表示语言处理的过程。
答：语言处理的过程如图所示：
4．简述算法设计的策略。
答：作为实现计算机程序实现时解决问题的方法，算法研究的内容是解决问题的方法，而不是计算机程序的本身。一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要，因此，在计算机程序设计中，算法设计往往处于核心地位。
要想充分理解算法并有效地应用于实际问题，关键是对算法的分析。通常可以利用实验对比分析、数学方法来分析算法。实验对比分析很简单，两个算法相互比较，它们都能解决同一问题，在相同环境下，一般就会认为哪个算法的速度快这个算法性能更好。在算法设计中，通常采用能近似表达性能的方法来展示某个算法的性能指标。例如，计算机对n
22和n2n的响应速度，当n比较大的时,没什么区别，便可直接认为后者算法的复杂度为n2。
基于算法复杂度简化表达的思想基础上，通常会对算法进行最坏情况分析和平均情况分析。对于一个给定的算法，如果能保证它的最坏情况下的性能依然很好，但是在某些情况下，程序的最坏情况算法的运行时间和实际情况的运行时间相差很大，在实际应用中几乎不会碰到最坏情况下的输入，那么此时进行最坏情况分析显得有些画蛇添足，特别是分析最坏情况算法会花费大量精力的时候。算法的平均情况分析可以帮助估计程序的性能，作为算法分析的基本指标之一，但是平均情况和实际情况仍然会有相差很大的时候，这时便可以使用随机法来尽量模拟现实中的情况，这样可以得到在严格的概率意义上的预测运行时间。另外，对于一个经典算法，没有必要再去对该算法进行改进，研究它的上界和下界，只需要了解该算法的特性，然后在合适的时候使用它。
5．简述并行算法研究的内容。
答：(1) 并行计算模型并行算法作为一门学科，首先研究的是并行计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。
并行计算模型的第一代是共享存储模型，如SIMD-SM和MIMD-SM的一些计算模型，模型参数主要是CPU的单位计算时间，这样科学家可以忽略一些细节，集中精力设计算法。第二代是分布存储模型。在这个阶段，人们逐渐意识到对并行计算机性能带 来影响的不仅仅是CPU，还有通信。因此如何把不同的通信性能抽象成模型参数，是这个阶段的研究重点。第三代是分布共享存储模型，也是我们目前研究所处的阶段。随着网络技术的发展，通信延迟固然还有影响，但对并行带来的影响不再像当年那样重要，注重计算系统的多层次存储特性的影响。
(2) 设计技术并行算法研究的第二部分是并行算法的设计技术。虽然并行算法研究还不是太成熟，但并行算法的设计依然是有章可循的，例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法破对称法等都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。
以上是并行算法的常规研究内容。随着时代的进步，我们需要不断调整研究方向。目前并行算法研究的新走向是并行算法研究内容不断拓宽，并行计算被纳入研究范畴；与广大用户领域结合，注重应用，强调走到用户中去，为用户解决问题；重视新的、非常规计算模式，如神经计算、量子计算等，这些模式能够解决某类特定问题，有其自身的优越性。
三、讨论题
1．算法是程序设计的基础，没有好的算法，就不可能写出好的程序，但是，学习算法涉及到很多交叉学科的知识，怎样才能把这些知识融会贯通，写出优秀的程序？
答案略。
2．算法设计非常复杂，如何才能设计优秀的算法？
答案略。
第5章 算法与复杂性
习 题
一、选择题
1. B 2. D 3. C 4. A 5. B
6. B 7. D 8. C 9. A 10. A
二、简答题
1．什么是算法，算法的特性有哪些？
答：“算法(Algorithm)是一组明确的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果”。算法的特性有：
(1) 有穷性(可终止性)：一个算法必须在有限个操作步骤内以及合理的有限时间内执行完成。
(2) 确定性：算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。
(3) 有效性(可执行性)：算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。
(4) 输入及输出：一个算法应该有零个或多个输入数据、有1个或多个输出数据。
2．什么是算法的时间复杂度和空间复杂度，如何表示？
答：时间复杂度是与求解问题规模、算法输入相关的函数，该函数表示算法运行所花费的时间。记为，T(n)，其中，n代表求解问题的规模。
算法的空间复杂度(Space complexity)度量算法的空间复杂性、即执行算法的程序在计算机中运行所占用空间的大小。简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。记为，S(n)，其中，n代表求解问题的规模。
时间复杂度和空间复杂度同样，引入符号“O”来表示T(n)、S(n)与求解问题规模n之间的数量级关系。
3．用图示法表示语言处理的过程。
答：语言处理的过程如图所示：
4．简述算法设计的策略。
答：作为实现计算机程序实现时解决问题的方法，算法研究的内容是解决问题的方法，而不是计算机程序的本身。一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要，因此，在计算机程序设计中，算法设计往往处于核心地位。
要想充分理解算法并有效地应用于实际问题，关键是对算法的分析。通常可以利用实验对比分析、数学方法来分析算法。实验对比分析很简单，两个算法相互比较，它们都能解决同一问题，在相同环境下，一般就会认为哪个算法的速度快这个算法性能更好。在算法设计中，通常采用能近似表达性能的方法来展示某个算法的性能指标。例如，计算机对n
22和n2n的响应速度，当n比较大的时,没什么区别，便可直接认为后者算法的复杂度为n2。
基于算法复杂度简化表达的思想基础上，通常会对算法进行最坏情况分析和平均情况分析。对于一个给定的算法，如果能保证它的最坏情况下的性能依然很好，但是在某些情况下，程序的最坏情况算法的运行时间和实际情况的运行时间相差很大，在实际应用中几乎不会碰到最坏情况下的输入，那么此时进行最坏情况分析显得有些画蛇添足，特别是分析最坏情况算法会花费大量精力的时候。算法的平均情况分析可以帮助估计程序的性能，作为算法分析的基本指标之一，但是平均情况和实际情况仍然会有相差很大的时候，这时便可以使用随机法来尽量模拟现实中的情况，这样可以得到在严格的概率意义上的预测运行时间。另外，对于一个经典算法，没有必要再去对该算法进行改进，研究它的上界和下界，只需要了解该算法的特性，然后在合适的时候使用它。
5．简述并行算法研究的内容。
答：(1) 并行计算模型并行算法作为一门学科，首先研究的是并行计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。
并行计算模型的第一代是共享存储模型，如SIMD-SM和MIMD-SM的一些计算模型，模型参数主要是CPU的单位计算时间，这样科学家可以忽略一些细节，集中精力设计算法。第二代是分布存储模型。在这个阶段，人们逐渐意识到对并行计算机性能带 来影响的不仅仅是CPU，还有通信。因此如何把不同的通信性能抽象成模型参数，是这个阶段的研究重点。第三代是分布共享存储模型，也是我们目前研究所处的阶段。随着网络技术的发展，通信延迟固然还有影响，但对并行带来的影响不再像当年那样重要，注重计算系统的多层次存储特性的影响。
(2) 设计技术并行算法研究的第二部分是并行算法的设计技术。虽然并行算法研究还不是太成熟，但并行算法的设计依然是有章可循的，例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法破对称法等都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。
以上是并行算法的常规研究内容。随着时代的进步，我们需要不断调整研究方向。目前并行算法研究的新走向是并行算法研究内容不断拓宽，并行计算被纳入研究范畴；与广大用户领域结合，注重应用，强调走到用户中去，为用户解决问题；重视新的、非常规计算模式，如神经计算、量子计算等，这些模式能够解决某类特定问题，有其自身的优越性。
三、讨论题
1．算法是程序设计的基础，没有好的算法，就不可能写出好的程序，但是，学习算法涉及到很多交叉学科的知识，怎样才能把这些知识融会贯通，写出优秀的程序？
答案略。
2．算法设计非常复杂，如何才能设计优秀的算法？
答案略。