计算机程序基础数据算法

第一章算法计算机软件技术基础2023/2/5计算机软件技术基础第一章算法2第一章算法1.1算法的基本概念1.2算法设计基本方法1.3算法的复杂度分析什么是算法；算法的基本特征。1.列举法；2.递推法；3.递归法；4.减半递推法；5.回溯法。算法的时间复杂度。2023/2/5计算机软件技术基础第一章算法31.1算法的基本概念用计算机解决一个实际问题，首先要进行程序设计。通常，程序设计主要包括两个方面：行为特性的设计：要求将解决实际问题的每个细节准确地加以定义，并且还应当将全部解题过程完整地描述出来，这一过程即是算法的设计；结构特性的设计：指确定适合的数据结构。2023/2/5计算机软件技术基础第一章算法41.1算法的概念定义：“算法”是指解题方案的准确而完整的描述。算法可解：对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果。程序与算法的区别：程序可以作为算法一种描述，但程序通常还需考虑很多与方法和分析无关的细节问题，因为在编写程序时要受到计算机系统运行环境的限制。结论：通常，程序设计不可能优于算法的设计。2023/2/5计算机软件技术基础第一章算法51.1.1算法的基本特征能（可）行性(effectiveness)⑴算法中的每一个步骤必须能够实现。⑵算法执行的结果要能够达到预期的目的。例如：三个量的和，如果采用不同的运算顺序，就会得到不同的结果：数据存储的实际范围2023/2/5计算机软件技术基础第一章算法6确定性(definiteness)算法中每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。反映了算法与数学公式的明显差别：针对某种特殊情况，数学公式是正确的，但按此数学公式设计的计算过程可能会使计算机系统无所适从。因为没有考虑异常情况的出现。举例：“输入一个x，若x比1大很多，则输出数字1，否则输出数字0。”2023/2/5计算机软件技术基础第一章算法7有穷性(finiteness)算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。举例：一个数的无穷级数表示只是一个计算公式，而根据精度要求确定的计算过程才是有穷的算法。另一种定义：合理的执行时间。2023/2/5计算机软件技术基础第一章算法8补充：无穷级数无穷级数是研究有次序的可数无穷个数或者函数的和的收敛性及和的数值的方法。举例：假定有一个无穷数列：u1，u2，u3，...，un，...其前n项的和为：Sn=u1+u2+u3+...+un由此得出另一个新无穷数列：S1，S2，S3，…，Sn，...当n无限增加时，Sn趋向一个极限；如果极限存在，这个无穷数列就叫做是收敛的无穷级数，如果极限不存在，这个数列就是发散的。只有收敛的无穷级数存在一个和S。S=u1+u2+u3+...+un+...2023/2/5计算机软件技术基础第一章算法9拥有足够的情报一个算法是否有效还取决于为算法所提供的情报是否足够。通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入会有不同的输出。当提供的情报不够时，算法并不是有效的。2023/2/5计算机软件技术基础第一章算法10结论算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列。2023/2/5计算机软件技术基础第一章算法111.1.2算法的基本要素算法通常由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。算法中对数据的运算和操作①算术运算：加、减、乘、除、整除、取余等运算；②逻辑运算：“与”、“或”、“非”等运算；③关系运算：“大于”、“小于”、“等于”、“不等于”等运算。④数据传输：赋值、输入、输出等操作。2023/2/5计算机软件技术基础第一章算法12算法的控制结构定义：算法中各操作之间的执行顺序。描述算法的工具：传统流程图；N-S结构化流程图；算法描述语言。三种基本控制结构：顺序、选择、循环。ABABCTFACTF2023/2/5计算机软件技术基础第一章算法131.2算法设计的基本方法计算机解题的过程实际上是在实施某种算法，这种算法通常称为计算机算法，与人工处理的算法不同。举例：2023/2/5计算机软件技术基础第一章算法14算法设计的基本方法人工处理的步骤：找出被积函数f(x)的源函数F(x);利用牛顿-莱布尼兹公式计算。计算机处理方式：采用数值积分法，根据实际被积函数的类型以及精度要求选择相应的算法。2023/2/5计算机软件技术基础第一章算法15㈠列举法基本思想：根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。列举法常用于解决“是否存在”或“有多少种可能”等类型的问题，例如求解不定方程的问题。特点：算法比较简单，但当列举的可能情况较多时，执行列举算法的工作量将会很大。2023/2/5计算机软件技术基础第一章算法16举例：百鸡百钱问题例1.1：设每只母鸡值3元，每只公鸡值2元，两只小鸡值1元。现要用100元钱买100只鸡，设计买鸡方案。（百鸡百钱问题）

假设买母鸡i只，公鸡j只，小鸡k只。2023/2/5计算机软件技术基础第一章算法17最粗略的列举算法如下：算法：求解百鸡百钱问题。

fori＝0to100doforj＝0to100dofork＝0to100do{m=i＋j＋kn=3i＋2j＋0.5kif((m＝100)and(n＝100))thenoutputi，j，k}returni表示购买的母鸡个只数j表示购买的公鸡个只数k表示购买的小鸡个只数计算购买鸡的总数m以及总价格n2023/2/5计算机软件技术基础第一章算法18i=0i≤100j=0j≤100Tk=0k≤100T计算鸡的总只数m和购买鸡的总价格nm==100&&n==100输出m和nTk++j++i++TFF结束F1013F2023/2/5计算机软件技术基础第一章算法19改进算法：求解百鸡百钱问题。

fori＝0to33doforj＝0to50－1.5ido{k=100－i－jif(3i＋2j＋0.5k＝100)thenoutputi，j，k}return总循环次数为：运行结果如下：02306805257008207211157414107617578200802023/2/5计算机软件技术基础第一章算法20㈢递推基本思想：从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。补充举例：计算下列定积分递推算法在数值计算中极为常见，但对于数值型的递推算法必须要注意数值计算的稳定性问题。2023/2/5计算机软件技术基础第一章算法21对上式稍作分析，可以发现相邻两个积分之间存在以下关系：从而得到递推公式：2023/2/5计算机软件技术基础第一章算法22利用牛顿-莱布尼兹公式可以计算出积分I0的值：从而得到21个积分的递推算法如下：近似值就意味着有误差假定初始值（情报）的误差为α2023/2/5计算机软件技术基础第一章算法23表1.1第一种递推公式得到的结果2023/2/5计算机软件技术基础第一章算法24实际上，根据关系式还可以得到另一个递推公式2023/2/5计算机软件技术基础第一章算法25如果要使用递推公式(1.5)时，需要确定初始值I20。有如下不等式：可以得到：最后可得：当n=21时，有由于很接近，因此可用它们的平均值作为I20的近似值，即近似值就意味着有误差2023/2/5计算机软件技术基础第一章算法26根据之前的推论，可以得到第二种21个积分的递推算法：假定初始值（情报）的误差为β2023/2/5计算机软件技术基础第一章算法27表1.2第二种递推公式得到的结果递推算法在数值计算中极为常见，但对于数值型的递推算法必须要注意数值计算的稳定性问题。2023/2/5计算机软件技术基础第一章算法28㈣递归基本思想：将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。补充举例：求解Hanoi塔问题。2023/2/5计算机软件技术基础第一章算法29补充举例：求解Hanoi（汉诺）塔问题。 设有三个塔座分别为X、Y、Z。现有n个直径各不相同的圆盘，且按直径从小到大用自然数编号为1，2，…，n。开始时，此n个圆盘依下大上小的顺序放在塔盘X上。先要根据下列原则将X塔座上的这n个圆盘移动到Z塔座上：每次只允许移动一个圆盘（从一个塔座到另一个塔座）；移动时可用Y塔座作为中间塔座；在移动过程中，任何一个塔座上均不允许出现大压小的情况发生。2023/2/5计算机软件技术基础第一章算法30图示Hanoi塔问题XYZ起始塔柱中间塔柱目的塔柱每次只允许移动一个圆盘（从一个塔座到另一个塔座）；移动时可用Y塔座作为中间塔座；在移动过程中，任何一个塔座上均不允许出现大压小的情况发生。2023/2/5计算机软件技术基础第一章算法31三阶Hanoi塔问题分析：起始塔座X上有三个圆盘，所以该问题被称为三阶Hanoi塔问题。塔座X塔座Y塔座Z321需要完成：Hanoi(3,X,Y,Z)；其中，参数1表示一共需要移动几个圆盘；参数2表示起始塔座；参数3表示中间塔座；参数4表示目的塔座。2023/2/5计算机软件技术基础第一章算法32三阶Hanoi塔问题分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。塔座X塔座Y塔座Z321需要先完成：Hanoi(2,X,Z,Y)；该工作又可分解成：①Hanoi(1,X,Y,Z)；②MOVE(X,2,Y)；③Hanoi(1,Z,X,Y)。完成Hanoi(1,X,Y,Z)；工作等价于MOVE(X,1,Z)。2023/2/5计算机软件技术基础第一章算法33三阶Hanoi塔问题塔座X塔座Y塔座Z321分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。需要先完成：Hanoi(2,X,Z,Y)；该工作又可分解成：①Hanoi(1,X,Y,Z)；②MOVE(X,2,Y)；③Hanoi(1,Z,X,Y)。完成MOVE(X,2,Y)。2023/2/5计算机软件技术基础第一章算法34三阶Hanoi塔问题塔座X塔座Y塔座Z321分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。需要先完成：Hanoi(2,X,Z,Y)；该工作又可分解成：①Hanoi(1,X,Y,Z)；②MOVE(X,2,Y)；③Hanoi(1,Z,X,Y)。完成Hanoi(1,Z,X,Y)；工作等价于MOVE(Z,1,Y)。Hanoi(2,X,Z,Y)完成!2023/2/5计算机软件技术基础第一章算法35三阶Hanoi塔问题分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。塔座X塔座Y塔座Z321完成：MOVE(X,3,Z)；接下来需要完成：Hanoi(2,Y,X,Z)。2023/2/5计算机软件技术基础第一章算法36三阶Hanoi塔问题分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。塔座X塔座Y塔座Z321最后完成：Hanoi(2,Y,X,Z)；该工作又可分解成：①Hanoi(1,Y,Z,X)；②MOVE(Y,2,Z)；③Hanoi(1,X,Y,Z)。完成Hanoi(1,Y,Z,X)；其工作等价于MOVE(Y,1,X)。2023/2/5计算机软件技术基础第一章算法37三阶Hanoi塔问题分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。塔座X塔座Y塔座Z312最后完成：Hanoi(2,Y,X,Z)；该工作又可分解成：①Hanoi(1,Y,Z,X)；②MOVE(Y,2,Z)；③Hanoi(1,X,Y,Z)。完成MOVE(Y,2,Z)。2023/2/5计算机软件技术基础第一章算法38三阶Hanoi塔问题分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三个步骤：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。塔座X塔座Y塔座Z321最后完成：Hanoi(2,Y,X,Z)；该工作又可分解成：①Hanoi(1,Y,Z,X)；②MOVE(Y,2,Z)；③Hanoi(1,X,Y,Z)。完成Hanoi(1,X,Y,Z)；其工作等价于MOVE(X,1,Z)。Hanoi(2,Y,X,Z)完成!Hanoi(3,X,Y,Z)完成!2023/2/5计算机软件技术基础第一章算法39总结：三阶Hanoi塔问题将一个复杂的问题（三阶Hanoi塔问题）归结为若干个较简单的问题（二阶Hanoi塔问题）；然后将这些较简单的每一个问题（二阶Hanoi塔问题）再归结为更简单的问题，直到最简单的问题（一阶Hanoi塔问题）为止。塔座X塔座Y塔座Z3212023/2/5计算机软件技术基础第一章算法40再分析：n阶Hanoi塔问题求解的步骤：如果n=1，则可直接将这一个圆盘移动到目的柱上，过程结束。如果n>1，则进行步骤2。设法将起始柱的上面n-1个圆盘（编号1到n-1）按移动原则移动到中间柱上。将起始柱上的最后一个圆盘（编号为n）移到目的柱上。设法将中间柱上的n-1圆盘按移动原则移到目的柱上。2023/2/5计算机软件技术基础第一章算法41步骤2与步骤4实际上还是Hanoi塔问题，只不过其规模小一些而已。如果最原始的问题为n阶Hanoi塔问题，且表示为Hanoi(n,X,Y,Z)则步骤2与步骤4为n-1阶Hanoi塔问题分别表示为：

Hanoi(n-1,X,Z,Y) Hanoi(n-1,Y,X,Z)

其中第一个参数表示问题的阶数，第二、三、四个参数分别表示起始柱、中间柱与目的柱。将X塔座上的n号圆盘移到Z塔座上

Move(X,n,Z)2023/2/5计算机软件技术基础第一章算法42补充举例之算法：求解n阶Hanoi塔问题。

Hanoi(n,X,Y,Z) IFn=1THENmove(X,1,Z) ELSE {Hanoi(n-1,X,Z,Y)

move(X,n,Z)

Hanoi(n-1,Y,X,Z) }RETURN函数在执行过程中调用自身的方法叫递归调用。递归的边界2023/2/5计算机软件技术基础第一章算法43另一个简单的例子例1.2：编写一个过程，对于输入的参数n，依次打印输出自然数1到n。（非递归算法）PROCEDUREWRT(n)FORk＝1TOnDOOUTPUTkRETURN2023/2/5计算机软件技术基础第一章算法44输出自然数1到n的递归算法。

PROCEDUREWRT1(n)IF(n≠0)THEN{WRT1(n－1)OUTPUTn}RETURNWRT1(3)WRT1(2)WRT1(1)WRT1(0)OUTPUT2OUTPUT1OUTPUT3递归的边界√√√√√√√☆☆☆1232023/2/5计算机软件技术基础第一章算法45总结一个典型的递归算法：自己调用自己。直接递归：如果一个算法P显式地调用自己。间接递归：如果算法P调用另一个算法Q，而算法Q又调用算法P。递归算法与递推算法的区别：两者的实现方法是大不一样的。递推是从初始条件出发，逐次推出所需求的结果；而递归则是从算法本身达到递归边界。2023/2/5计算机软件技术基础第一章算法46㈤减半递推所谓“减半”，是指将问题的规模减半，而问题的性质不变。所谓“递推”，是指重复“减半”的过程。将实际问题的规模逐渐减少，可明显地降低解决问题的复杂程度。这种方法称为分治法，即对问题分而治之。工程上常用的分治法是减半递推技术，这个技术在快速算法的研究中有很重要的使用价值。2023/2/5计算机软件技术基础第一章算法47举例例1.3：二分法求方程f(x)在[a,b]的根设方程f(x)=0在区间[a,b]内有且只有一个实根，则函数f(x)在区间的两个端点处的函数值必异号，即2023/2/5计算机软件技术基础第一章算法48首先取给定区间的中点c＝(a＋b)/2。然后判断f(c)是否为0。若f(c)＝0,则说明c即为所求的根，求解过程结束；如果f(c)≠0,则根据以下原则将原区间减半；若f(a)f(c)＜0，则取原区间的前半部分；若f(b)f(c)＜0，则取原区间的后半部分。最后判断减半后的区间长度是否已经很小：若|a－b|＜ε，则过程结束，取(a＋b)/2为根的近似值；若|a－b|≥ε，则重复上述的减半过程。所能接受的误差2023/2/5计算机软件技术基础第一章算法49算法1.3二分法求方程的根输入：根所在区间[a,b]，精度要求输出：满足精度要求的根的近似值cf0←f(a)WHILE|b-a|≥εDO {c←(a+b)/2;f1←f(c) IFf1=0THEN {OUTPUTc

RETURN} IFf0×f1>0THENa←c ELSEb←c}c←(a+b)/2OUTPUTc

RETURNf0←f(a)|b-a|≥εc←(a+b)/2;f1←f(c)f1==0OUTPUTc结束得出准确根f0×f1>0得出近似根a←cb←cTTFFTF2023/2/5计算机软件技术基础第一章算法50总结对于有些实际问题，可以设计出直观的减半递推算法，经过逐次的减半递推，直接得到所需求的结果，如例1.3：二分法求方程的根。对于另外一些问题，根据减半递推技术设计出的算法是递归算法，在执行过程中只能靠算法本身到达递归边界。如例子：两个n阶矩阵相乘的快速方法就是递归算法（斯特拉森（Strassen）算法）。2023/2/5计算机软件技术基础第一章算法51㈥回溯法通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。例1.4求解皇后问题。2023/2/5计算机软件技术基础第一章算法52例1.4求解皇后问题。 由n2个方块排成n行n列的正方形称为“n元棋盘”。如果两个皇后位于棋盘上的同一行或同一列或同一对角线上，则称它们为互相攻击。现要求找使n元棋盘上的n个皇后互不攻击的所有布局。分析：假设棋盘上的每一行放置一个皇后，分别用自然数进行编号为1，2，…，n。首先，将问题归结为在n元棋盘的每一行上安置一个皇后，并假设第i个皇后被安置在第i行上。定义一个长度为n的一维数组q，其中每一个元素q[i]（i=1，2，…，n）用于在安置皇后过程中随时记录第i行上的皇后所在列号。2023/2/5计算机软件技术基础第一章算法53此时，在安置每一行上的皇后时，只需考虑每两个皇后不能在同一列或者同一对角线上即可。容易验证，第i行上的皇后和第j行上的皇后正好在同一列上的充要条件为：

q[i]–q[j]=0

正好在某一对角线上的充要条件为： |q[i]–q[j]|-|i-j|=0在初始时，将每一行的皇后均放在第一列，即初始状态为：

q[i]=1,i=1,2,3,…,n。2023/2/5计算机软件技术基础第一章算法54然后从第一行（即i=1）开始进行以下过程：设前i-1行行的皇后已经布局好，即它们互不攻击。现考虑安排第i行上的皇后位置，使之与前i-1行上的皇后也互不攻击。为了实现这一点，需要从第i行皇后的当前位置开始向右搜索：2023/2/5计算机软件技术基础第一章算法55若q[i]≤n，则需检查第i行皇后与前i-1行的皇后是否互不攻击。若无攻击，则考虑安排下一行皇后的位置；若有攻击，则将第i行皇后右移一个位置，重新进行这个过程。若q[i]>n，则说明在前i-1行皇后的当前布局下，第i行皇后无法安置。此时，将第i行皇后重新放在第一列，且回退一行，考虑第i-1行皇后与前i-2行皇后均互不攻击的下一个位置。在这种情况下，如果已经退到第0行（n元棋盘不存在第0行），则过程结束。若当前安置好的皇后是在最后一行（即第n行），则说明已找到了n个皇后互不攻击的一个布局，将这个布局打印输出。然后将第n行的皇后右移一个位置，重新进行这个过程，以便进一步寻找出另外的布局。2023/2/5计算机软件技术基础第一章算法56举例：5阶皇后问题初始状态：五粒皇后棋子最初均被放置在每一行的第1列，即，数组q[5]中的五个元素均取初值1。12345123452023/2/5计算机软件技术基础第一章算法57举例：5阶皇后问题皇后1：前面没有其它皇后，所以保留其初始值1，表示该皇后棋子被放置在第1行（1号皇后）第1列。q[1]=1。12345123452023/2/5计算机软件技术基础第一章算法58举例：5阶皇后问题皇后2：前面有皇后1，从第1列开始寻找和前面的所有皇后棋子均不相互攻击的位置，第一个合适的位置在第3列，q[2]=3。12345123452023/2/5计算机软件技术基础第一章算法59举例：5阶皇后问题皇后3：前面有皇后1和皇后2，寻找到第一个合适的位置（与皇后1、2均不相互攻击）为第2列，q[3]=2。12345123452023/2/5计算机软件技术基础第一章算法60举例：5阶皇后问题皇后4：前面有皇后1、2和3，寻找到第一个合适的位置为第5列，q[4]=5。12345123452023/2/5计算机软件技术基础第一章算法61举例：5阶皇后问题皇后5：前面有皇后1～4，寻找到第一个合适的位置为第4列，q[5]=4。1234512345找到一个布局！找到一个5元棋盘上的5个皇后互不攻击布局，即这5粒棋子相互均不在同一行、同一列和同一对角线上。2023/2/5计算机软件技术基础第一章算法62举例：5阶皇后问题重新开始查找新布局：从上一布局最后一粒皇后棋子开始。将皇后5右移动一格，q[5]=5。1234512345原来的位置新的位置2023/2/5计算机软件技术基础第一章算法63举例：5阶皇后问题发现问题：皇后5找不到一个合适的新位置，所以说明前四个皇后棋子的位置不合适，所以问题回溯到皇后4的重新找位上，其皇后5回到第1列。12345123452023/2/5计算机软件技术基础第一章算法64举例：5阶皇后问题又发现新问题：皇后4也找不到一个合适的新位置，所以说明前三个皇后棋子的位置不合适，所以问题回溯到皇后3的重新找位上，其皇后4回到第1列。12345123452023/2/5计算机软件技术基础第一章算法65举例：5阶皇后问题重找新布局之皇后3：通过皇后3不断后移，又发现了第4列是一个合适的位置，q[3]=4。此时皇后3与皇后1、2均不相互攻击。1234512345原来的位置新的位置2023/2/5计算机软件技术基础第一章算法66举例：5阶皇后问题重找新布局之皇后4：皇后4右移动，发现新的合适位置第2列，即q[4]=2。12345123452023/2/5计算机软件技术基础第一章算法67举例：5阶皇后问题重找新布局之皇后5：皇后5右移动，发现只能放在第5列，但显然不合适，所以重新回溯到皇后4寻找！同时皇后5回到第1列。12345123452023/2/5计算机软件技术基础第一章算法68举例：5阶皇后问题重找新布局之回溯皇后4：皇后4右移动，发现新位置第5列，q[4]=5。12345123452023/2/5计算机软件技术基础第一章算法69举例：5阶皇后问题重找新布局之皇后5：皇后5右移动，发现新位置第2列，q[5]=2，此时找到第二个布局。1234512345又找到一个布局！找到一个5元棋盘上的5个皇后互不攻击布局，即这5粒棋子相互均不在同一行、同一列和同一对角线上。2023/2/5计算机软件技术基础第一章算法70总结综合以上过程，可以形象地概括成一句话：“向前走，碰壁回头”。这种方法也称为深度优先搜索DFS（DepthFirstSearch）技术。2023/2/5计算机软件技术基础第一章算法71算法1.4求解皇后问题。输入：n。输出：n个皇后互不攻击的各种布局，即数组元素q[i]（i=1，2，…，n）。FORi＝1TOnDOq[i]＝1i＝1loop:

IF(q[i]≤n)THEN{k＝1WHILE((k＜i)and((q[k]－q[i])*(|q[k]－q[i]|－|k－i|))≠0)DOk＝k＋1

IF(k＜i)THENq[i]＝q[i]＋1当循环是因为k≥i而停止的时候说明：第i个皇后棋和之前的i-1个皇后棋中的某一个发生了相互攻击的情况。2023/2/5计算机软件技术基础第一章算法72

ELSE{i＝i＋1

//考虑下一行皇后的位置IF(i＞n)THEN{OUTPUTq[i](i＝1，2，…，n)

q[n]＝q[n]＋1//重新考虑新的棋盘布局i＝n}}}2023/2/5计算机软件技术基础第一章算法73ELSE//前i-1行的棋盘布局不能保证第i行皇后//可以找到合适的位置{q[i]＝1i＝i－1IF(i＜1)THENRETURNq[i]＝q[i]＋1}GOTOloopRETURN说明已经回退到第1个皇后棋处还找不到新的布局，则目前所有的布局已经全部找到。结束程序。2023/2/5计算机软件技术基础第一章算法741.3算法的复杂度分析算法的复杂度主要是指时间复杂度与空间复杂度。1.3.1算法的时间复杂度定义：执行这个算法的计算工作量，即算法的时间代价。面临的问题：如何分析一个算法的工作量。简单的解决办法：执行算法所需的时间作为算法工作量的度量。2023/2/5计算机软件技术基础第一章算法75另一种对于时间复杂度的度量用算法程序中所执行的的指令条数或语句条数来度量算法的工作量。缺点：程序中各种指令或者语句的执行速度是极不相同的，而且这种方法又很大程度上取决于所使用的程序设计语言以及编制程序者的水平和风格。所以这种方法也是不可取的。2023/2/5计算机软件技术基础第一章算法76结论为了能够客观地反映出一个算法的效率，度量算法工作量的方法必须与所使用的计算机、程序设计语言以及编制程序者无关；应该与算法实现过程中的许多细节（包括循环控制变量的计算、数组下标的计算、设置数据结构指针等“簿记”bookkeeping）无关。用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。2023/2/5计算机软件技术基础第一章算法77如何选择基本运算应该遵循的两个原则：算法执行的运算总次数与基本运算的次数大体上要成正比；基本运算以外的其它运算其运算量可以忽略。举例：在一维数组中顺序查找值为x的元素，可以选取“x和数组元素的比较”作为基本运算。在两个实矩阵相乘的算法中，可以选取“两个实数的乘法”作为基本运算。2023/2/5计算机软件技术基础第一章算法78举例：顺序查找一维数组L[10]，该形式被称为是长度为10的线性表的顺序存储（顺序实现）。要求：在该数组中分别查找并分别输出元素29和元素48的位置，如果该元素不在其中则输出-1。结果：查找成功、查找失败。3516788543293321544612345678910L[10]元素29在数组L中查找成功，位置为6。顺序与数组L中的所有元素比较后得出查找失败的结论，输出结果-1。该算法的基本操作应为：两两元素的比较。2023/2/5计算机软件技术基础第一章算法79举例：矩阵相乘两个4阶的矩阵相乘：×由于计算机在进行实数运算时，乘法运算的时间代价要远远高于加法运算的时间代价，该算法的基本操作应为：实数间的乘法运算。2023/2/5计算机软件技术基础第一章算法80算法所执行的基本运算次数有时与问题的规模有关。举例：两个20阶矩阵相乘与两个10阶矩阵相乘。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模n的函数，即f(n)。同时，一个算法的具体工作量，即对于一个固定的规模n，算法所执行的基本运算次数还可能与特定的输入有关。举例：“在长度为n的一个维数组中查找值为x的元素。”（采用顺序查找法）2023/2/5计算机软件技术基础第一章算法81两种分析算法工作量的方法(1)平均性态(AerageBehavior)当问题的规模为n时，算法执行的基本运算次数取决于某一特定的输入。可以用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量。设x为所有可能输入中某个特定输入，p(x)是x出现的概率（即输入为x的概率），T(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态：2023/2/5计算机软件技术基础第一章算法82最坏情况复杂性(Worst-CaseComplexity)含义：在规模为n时，算法所执行的基本运算的最大次数。2023/2/5计算机软件技术基础第一章算法83举例说明例1.5设L是包含n个元素的一维数组。对于指定的输入x，如果x在数组中，则顺序找到它第一次出现处的下标；如果x不在数组中，则以下标0作为查找结果。2023/2/5计算机软件技术基础第一章算法84算法：顺序搜索法（SequentialSearch）。输入：一维数组L(1:n)，被查项x。输出：第一次使L(j)=x的j，若x不在数组L中，则输出j=0。j←1WHILE(j≤n)and(L(j)≠x)DOj←j+1IFj>nTHENj←0OUTPUTjRETURN2023/2/5计算机软件技术基础第一章算法85（1）平均性态分析设被查项x在数组L中的概率为q。当输入的x为L(i)时，算法所做的比较次数为：其中x=L(n+1)表示x不在数组L中的情况。再假设输入的x出现在数组中的每个位置上的可能性是一样的，即2023/2/5计算机软件技术基础第一章算法86于是有2023/2/5计算机软件技术基础第一章算法87（2）最坏情况分析最坏情况发生在当x是数组的最后一个元素或者x不在数组中的时候，这时有即，在这两种情况下，要和数组中所有的元素进行比较。2023/2/5计算机软件技术基础第一章算法88补充：时间频度与时间复杂度1.时间频度一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。基本操作的执行次数2023/2/5计算机软件技术基础第一章算法892.时间复杂度在时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。为了知道其变化的规律引入了时间复杂度概念。若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作