第1节 计算机算法概述 ................................................................................................................................................................. 1
1.1 算法的五个特性 .............................................................................................................................................................. 1 1.2 算法设计的要求 .............................................................................................................................................................. 1 1.3 算法效率的度量 .............................................................................................................................................................. 1
第2节 各种常规算法 ..................................................................................................................................................................... 2
2.1 迭代法 .............................................................................................................................................................................. 2 2.2 穷举搜索法 ...................................................................................................................................................................... 3 2.3 递推法 .............................................................................................................................................................................. 3 2.4 递归法 .............................................................................................................................................................................. 3 2.5 分治法 .............................................................................................................................................................................. 4
2.5.1 分治法思想 ......................................................................................................................................................... 4 2.5.2 分治法时间复杂度计算 ...................................................................................................................................... 5 2.6 动态规划法 ...................................................................................................................................................................... 6 2.7 回溯法 .............................................................................................................................................................................. 8 2.8 贪心法 ............................................................................................................................................................................ 10 2.9 分支限界法 .................................................................................................................................................................... 10 2.10 概率算法 ...................................................................................................................................................................... 11 2.11 字符串的模式匹配 ...................................................................................................................................................... 11
第3节 附录部分 .......................................................................................................................................................................... 12
3.1 使用递推法求N的阶乘程序代码 ................................................................................................................................. 12
I
第1节 计算机算法概述
计算机算法是对特定问题求解步骤的描述，它是指令的有限序列.为解决某问题的算法与为该问题编写的程序含义是相同的. 常用的表示算法的语言有：自然语言、流程图、盒图、程序设计语言和伪代码.
1.1 算法的五个特性
1. 有限性：算法必须在执行有限条指令之后结束，每条指令执行的时间也必须是有限的.
2. 确定性：算法中每一条指令必须有确切的含义，读者和计算机在理解时不会产生二义性，并且在相同条件下，相同的输入只能得到相同的输出.
3. 可行性：算法能把问题真正的解决.即不能是理论正确但无法在计算机上实现的算法. 4. 输入：一个算法有零个或多个输入.
5. 输出：一个算法有一个或多个输出. ●(2004年下)下面的程序段违反了算法的 (54) 原则. void sam() { int n=2； while(!odd(n)) n+=2； printf(n)； } (54)A.有穷性 B.确定性 C.可行性 D.健壮性 1.2 算法设计的要求
1. 正确性：算法应当满足具体问题的需求. 2. 可读性：算法应该能让人读懂，能被计算机运行. 3. 健壮性：算法应该具有容错处理能力，不容易被击垮.
4. 高效率与低存储量要求：效率指程序的执行时间（越短越好），算法要占用计算机一定的存储量（越小越好）.
1.3 算法效率的度量
1. 时间复杂度
根据不同的输入，将算法的时间复杂度分为三种情况：
(1) 最佳情况：使算法执行时间最少的输入.一般不进行算法在最佳情况下的时间复杂度分析.
(2) 最坏情况：使算法执行时间最多的输入.一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，而且对于某些算法来说，最坏情况是相当频繁的.
(3) 平均情况：算法的平均运行时间，可按三个步骤进行分析：将所有的输入按其执行时间分类；确定每类输入发生的概率；确定每类输入的执行时间.
(4) 时间复杂度的表示
算法时间复杂度符号O、Ω、Θ的定义分别如下.
? O记号：给出一个函数的渐进上界.给定一个函数g(n)，O(g(n))表示为一个函数集合的{f(n)：存在正常数c和n0，使得对所有的n≥n0，有O≤f(n)≤c·g(n)}.
? Ω记号：给出一个函数的渐进下界.给定一个函数g(n),Ω(g(n))表示为一个函数集合的{f(n)：存在正常数c和n0，使得对所有的n≥n0，有O≤c·g(n)≤f(n).
? Θ记号：给出一个函数的渐进上界和下界，即渐进确界.给定一个函数g(n)，Θ(g(n))表示为一个函数集合{f(n)：存在正常数c1、c2和n0，使得对所有的n≥n0，有O≤c1·g(n)≤f(n)≤c2·g(n)}.
常用大O记法，假如一个程序的实际执行时间为T（n）= 2n3+n2+5，则T（n）=O（n3）. (5) 时间复杂度常用表示方法
323
? 大O记法:假如一个程序的实际执行时间为T（n）= 2n+n+5，则T（n）=O（n），只用最高的次幂表示.
? O(1)：当算法耗费的时间没有达到n这个数据级别时，就使用O(1)表示（其中的“1”并非表示数量1，而表示时间未至n这个数量级）.
常见的时间复杂度如图 1.1所示.
23n22
图 1.1 常见时间复杂度的比较 ●(2012年上)以下关于渐进符号的表示中，不正确的是 (62) . O(1)?O(logn)?O(n)?O(nlogn)?O(n)?O(n)?O(2)2(62)A.n= (n) B.n2=O(n2) C.n2=O(n) D.n2=O(n3) ●(2004年下)下面函数中渐进时间最小的是(53). (53)A．T1(n)=n+nlogn B．T2(n)=2n+nlogn C．T3(n)=n2-logn D．T4(n)=n+100logn 2. 空间复杂度
一个算法的空间复杂度是指程序运行从开始到结束所需的存储量.主要包含算法自身实现所需要的辅助存储空间，不包含程序中原存储
1
2
数据的空间.
? 固定空间：在硬盘上的存储空间.
? 可变空间：程序运行时占用的内存空间. ●(2007年下)关于算法与数据结构的关系， （64）是正确的. A. 算法的实现依赖于数据结构的设计 B. 算法的效率与数据结构无关 C. 数据结构越复杂，算法的效率越高 D. 数据结构越简单，算法的效率越高 ●(2014年上)某个算法的时间复杂度递归式T(n)=T(n-l)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（62），若问题的规模增加了16倍，则运行时间增加（63）倍. （62）A.Θ(n) B.Θ(nlgn) C.Θ(n2) D.Θ(n2lgn) （63）A.16 B.64 C.256 D.1024 ●(2006年上)设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为(59). A．O(lgn) B．O(nlgn) C．O(n) D．O(n2) ●(2008年下)设某算法的计算时间表示为递推关系式T(n)= T(n-1)+ n(n>0)及T(0)=1，则该算法的时间复杂度为（65）. （65）A.O(lgn) B.O(nlgn) C.O(n) D.O(n2) ●(2010年上)若某算法在问题规模为n时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为（64）. T（n）=?n?1n＞1?T(n?1)?n?1 （64）A.O(n) B.O(n2) C.O(logn) D.O(nlogn) ●(2009年下)某算法的时间复杂度表达式为T(n)=an2+bnlgn+cn+d，其中，n为问题规模，a、b、c和d为常数，用O表示其渐进意义时间复杂度为（63）. （63）A.O(n2) B.O(n) C.O(nlgn) D. O(1) ●(2010年上)若对一个链表最常用的操作是在末尾插入结点和删除结点，则采用仅设尾指针的单向循环链表(不含头结点)时，（65）. A.插入和删除操作的时间复杂度都为O(1) B.插入和删除操作的时间复杂度都为O(n) C.插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(n) D.插入操作的时间复杂度为O(n)，删除操作的时间复杂度为O(1) ●(2011年下)对n个元素值分别为-1、0或1的整列数组A进行升序排序的算法描述如下：统计A中-1、0和1的个数，设分别为n1、n2和n3，然后将A中的前n1个元素赋值为-1，第n1+1到n1+n2个元素赋值为0，最后n3个元素赋值为1.该算法的时间复杂度和空间复杂度分别为（64） . ●(2012年上)现要对n个实数（仅包含正实数和负实数）组成的数组A进行重新排列，使得其中所有的负实数都位于正实数之前.求解该问题的算法的伪代码如下所示，则该算法的时间和空间复杂度分别为 (65) . i=O；j=n-l； while i 2.1 迭代法 思想：从某个点出发，通过某种方式求出下一个点，使得其离要求的点（方程的解）更近一步；当两点之差接近到可接受的精度范围时，就认为找到了问题的解. 注意：如果方程无解或者迭代方法不够适用，那么近似根序列将不会收敛，迭代过程会成为“死循环”.所以使用迭代法之前要进行是否有解的判断，并且限制迭代的次数；而方程即使有解，也要选择合适的迭代公式，否则迭代失败. 例子：用迭代法求x=sqrt(n).根据牛顿迭代法，构造出求平方根的迭代公式为:x=(x+n/x)/2要求前后两次求出的x的差的绝对值小于10e-6. #include void main() { int n; double x0,x1; scanf(\ while (n>=0) { x0 = 1; x1 = (x0+n/x0)/2; while(fabs(x1-x0)>=0.000001) { x0 = x1; x1 = (x0+n/x0)/2; } printf(\ scanf(\ } } 迭代法是用于求方程或方程组近似根的一种常用算法设计方法. 2.2 穷举搜索法 思想：对可能的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解. 特点：这种方法通常采用多重循环（循环次数取决于变量个数）来实现，对每个变量的每个值都测试是否满足所给定的条件，如果满足则认为找到问题的一个可行解. 缺点：只能解决候选解个数非常有限且容易枚举这些候选解的问题. 例子：找出n个自然数(1,2,3,…,n)中r个数的组合，要求r为3，且第一位数大于第二位数，第二位数大于第三位数. 程序： #include 思想：设要求解的问题规模为N，当N≤某个常数C时，解或为已知，或能非常方便地得到解.能采用递推法构造算法的问题有重要的递推性质：当得到问题规模为i-1的解后，由问题的性质，能从已求得的规模为1、2、3…、i-1的一系列解，构造出问题规模为i的解.这样，程序可从i=0或i=1出发，重复地，由已知的i-1规模的解，通过递推，获得规模为i的解，直至规模为n的解. 递推法典型用法是求整数的阶乘问题.求n！可转换为(n-1)!*n，以下是使用递推法求解整数5的阶乘的算法描述： (1) 求出1的阶乘结果为1（1的阶乘结果是已知的）； (2) 根据1的阶乘结果递推2的阶乘，即2！=1！*2; (3) 根据2的阶乘结果递推3的阶乘，即3！=2！*3; (4) 根据3的阶乘结果递推4的阶乘，即4！=3！*4; (5) 根据4的阶乘结果递推5的阶乘，即5！=4！*5; 递推法特点：执行效率高，能解决有前向相关性的问题，但是要求前向相关顺序确定而且个数不多的问题.任何能使用递推法解决的问题，都能使用递归法解决，但反之不然. 2.4 递归法 递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的一些问题，然后从这些小问题的解方便地构造出大问题的解，并且这样规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出其分解之前问题的解.特别地，当规模N≤C(C为常数)时，能直接得到解. 阶乘函数可递归地定义如图 2.1所示： 图 2.1 阶乘递归式 阶乘函数的自变量n的定义域是非负整数.递归式的第一式给出了这个函数的一个初始值，是非递归定义的.每个递归函数都必须有非递归定义的初始值，否则，递归函数就无法计算.递归式的第二式是用较小自变量的函数值来表示较大自变量的函数值的方式来定义n的阶乘.n！可以递归地计算如下： int Factorial（int n） 3 { if (n == 0) return 1; if (n > 0) return n*Factorial（n - 1）； } 图 2.2是当n＝3的递归图： 图 2.2 求3！的递归图 特点:由于递归程序需要调用工作栈，故其运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多.递归程序分为递推和回归两个过程： ? 递推过程：把较复杂的问题的求解推到比原来问题简单一些的问题的求解； ? 回归阶段：当获得最简单情况的解后，逐级返回，依次获得稍复杂问题的解. Fibonacci数列和背包问题等都是递归算法的典型应用. 递推法和递归法的关系：任何能使用递推法解决的问题，都能使用递归法解决，反之不成立.因为某些递归算法所要求的子问题的形式，不一定能够预先计算好结果，因此只能递归，无法递推.经典的例子是合并排序既能够递推，也能够递归，而快速排序无法递推，只能递归. ●(2007年上)若一个问题既可以用迭代方式也可以用递归方式求解，则（65）方法具有更高的时空效率. A.迭代 B.递归 C.先递归后迭代 D.先迭代后递归 ●(2005年下)设求解某问题的递归算法如下： F(int n){ if n==1 { Move(1) }else{ F(n-1); Move(n); F(n-1); } } 求解该算法的计算时间,仅考虑算法Move所做的计算为主要计算,且Move 为常数级算法.则算法F的计算时间T(n)的递推关系式为(53) ；设算法Move的计算时间为k，当n=4时，算法F的计算时间为 (54) . （53）A.T(n)=T(n-1)+1 B.T(n)=2T(n-1) C.T(n)=2T(n-1)+1 D.T(n)=2T(n+1)+1 （54）A.14k B.15k C.16k D.17k 2.5 分治法 2.5.1 分治法思想 思想：将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各个击破，分而治之.如果规模为n的问题可以分解成k个子问题，1 Hanoi塔问题、比赛日程安排是该算法的典型应用场所. 例子：最大子段和问题.给定由n个整数(可能为负整数)组成的序列a1、a2、a3、…、an,求该序列形如 ?ak?ijk的子段和的最大值.当所有 整数均为负整数时定义其最大子段和为 ??j??0，依次定义，所求的最优值为:max?0,max?a?,例如，当(a1, a2, a3, a4, a5, k??k?i1??i??j??n??ka6)=( -2,11,-4,13,-5,-2)时，最大子段和为： ?ak?24?20，如果将所给的序列a[1:n]分为长度相等的两端a[1:n/2]和a[n/2+1:n],分别求出这两 端的最大子段和，则a[1:n]的最大子段和有3种情形： 4
常用算法设计方法(2024年下-打印版本有答案--改革版本)
