文档介绍：: .
算法
递归分为直接递归与间接递归两种。
(5)减半递推技术
实际问题的复杂程度往往与问题的规模有着密切的联系。因此，利用分治法解决这类实
际问题是有效的。工程上常用的分治法是减半递推技术。所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减
半”的过程。
(6)回溯法
在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不
能进行无限的列举。对于这类问题，一种有效的方法是“试”。通过对问题的分析，找出一
个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解，若试探失
败，就逐步回退，换别的路线再逐步试探。
4 算法设计的要求
通常一个好的算法应达到如下目标：
(l)正确性(correctness)
正确性大体可以分为以下 4 个层次：
①程序不含语法错误；
②程序对于几组输入数据能够得出满足规格说明要求的结果；
③程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格
说明要求的结果；
④程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
(2)可读性(readability)
算法主要是为了方便入的阅读与交流，其次才是其执行。可读性好有助于用户对算法的
理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。
(3)健壮性(robustness)
当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的
输出结果。
(4)效率与低存储量需求
效率指的是程序执行时，对于同一个问题如果有多个算法可以解决，执行时间短的
算法效率高；存储量需求指算法执行过程中所需要的最大存储空间
考点 2 算法的复杂度1 算法的时间复杂度
算法的时间复杂度，是指执行算法所需要的计算工作量。同一个算法用不同的语言
实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。这表明
使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，
可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模(通常用整数 n 表示)，
它是问题的规模函数。即
算法的工作量=f(n)
例如，在 N×N 矩阵相乘的算法中，整个算法的执行时间与该基本操作(乘法)重复执行
的次数 n3 成正比，也就是时间复杂度为 n3，即
f(n)=O(n3)
在有的情况下，算法中的基本操作重复执行的次数还随问题的输入数据集不同而不同。
例如在起泡排序的算法中，当要排序的数组 a 初始序列为自小至大有序时，基本操作的执行
次数为氏当初始序列为自大至小有序时，基本操作的执行次数为 n(n- 1)/2。对这类算法
的分析，可以采用以下两种方法来分析。
(1)平均性态(Average Behavior)
所谓平均性态是指各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
设 x 是所有可能输入中的某个特定输入，p(x)是 x 出现的概率(即输入为 x 的概率)，t(x)
是算法在输入为 x 时所执行的基本运算次数，则算法的平均性态定义为