算法初步知识点.doc

----------------------- Page 1-----------------------
算法基础
前面，我们讨论了程序设计中关于数据组织的问题。对程序设计来说，另外一个重要的
问题是如何确定数据处理的流程，即确定解决问题的步骤。这就是算法问题。算法是一组确
定的解决问题的步骤。它和机器以及语言并无关系，但最终还是需要使用特定的语言加以实
现。
算法的概念
算法是计算机科学特别是软件设计中最具研究性质的。在计算机科学中，算法是研究适
合计算机程序实现问题解决的方法，因此它是许多计算机问题的核心研究对象。
一般认为，算法是一组明确的、可以执行的步骤的有序集合。“有序集合”说明算法中
的步骤是有顺序关系的。算法中的每一步骤还必须是“明确的”，模棱两可的步骤不能构成
算法。例如，“把变量x 加上一个不太大的整数”。这里 “不太大的整数”就很不明确。另外，
算法中的每一步骤还必须是“可执行的”。这里所说的可执行不是一定要能被计算机所直接
执行，即它不一定直接对应计算机的某个指令。但至少对阅读算法的人来说，相应步骤是有
效和可以实现的。例如，“列出所有的正整数”就是不可执行的（有无穷多的）。
当我们使用计算机来解决问题的时候，有时会面临多种可能的解决途径。而选择不同的
解决途径可能会有不同的问题求解效率。如果是一个简单的问题，这种选择也许无关紧要；
但对大型问题，这种选择就是至关重要的。如果被设计的程序需要机器运行数年、或至少数
GB 以上的内存，那就看不出这个程序还有什么意义。对于一些复杂的问题，例如对现实的
模拟过程，使用设计优良的算法使系统运行速度和性能得以成倍的提高是完全可能的。
所以，不管需要解决的问题是属于哪个应用领域，严谨的、合理的、高效的算法设计对
解决复杂问题是非常有意义的。
下面，我们来看一个简单的算法例子。
【】在一个从小到大顺序排好的整数序列中查找某一指定的整数所在的位置。
这是一个查找问题。我们可以比较两种不同的查找方法。
[方法一]一种简单而直接的方法是按顺序查找，相应的查找步骤是：
1 ）查看第一个数。
2 ）若当前查看的数存在，则
若该数正是我们要找的数，则找到，查找过程结束；
若不是我们要找的数，继续查下一个数，重复 2 ）步。
3 ）若当前查看的数不存在，则要找的数不在序列里，查找过程结束。
[方法二]二分查找法（或称折半查找法，binary search）。由于序列中的整数是从小到大
排列的，所以可以应用此方法。该方法的要点是，先比较序列中间位置的整数，如果与
要找的数一样，则找到；若比中间那个整数小，则只要用同样方法在前半个序列中找就
可以了；否则，在后半个序列中找。相应查找步骤如下:
1 ）把含n 个整数的有序序列设为待查序列 S
2 ）若S 不空，则取序列S 中中间位置的整数，并设为middle。
若我们要找的数与 middle 一样，则找到，查找过程结束。
若我们要找的数小于middle，则将S 设为middle之前的半段序列，重复2 ）。
若我们要找的数大于middle，则将S 设为middle之后的半段序列，重复2 ）。
3 ）若S 为空，则要找的数不在序列中，过程结束。
在上述两种方法中，顺序查找方法简单，但效率不高。一般来说，若整数序列中整数的
·255 ·
----------------------- Page 2-----------------------
个数为n，即平均要找n/2 次才找到（若该数在序列中）。而二分查找法虽然思路相对复杂，
但效率高。通过分析可以知道，若要查找的数在个数为n的序列中，二分查找法平均花log2(n)
次左右的比较就可以找到。当问题的规模（n ）很大时，不同算法的效率就可以很明显地看
出来了。例如，当n为 100 万时，