计算机算法基础(第一章)

算法设计与分析

DesignandAnalysisofComputerAlgorithm有两种思想,像珠宝商放在天鹅绒上的宝石一样熠熠生辉.一个是微积分，另一个就是算法.微积分以及在微积分基础上建立起来的数学分析体系造就了现代科学,而算法造就了现代世界.——DavidBerlinski算法的研究内容问题是否可解1930’s研究集中于判断特定问题在计算机上是否可解，基本方法为：选定一个计算模型，观察是否能在该模型上创建能解决问题的算法。这些计算模型包括：Postmachines、Turingmachines等。这一阶段的成果是：大部分问题为不可解。高效率的解决方法随着计算机的发展和数据资源的增加，算法研究转向针对可解的问题，找到高效率的解决方法。算法的应用数据库中的检索搜索引擎中的检索公共密钥加密和数字签名技术优化问题最短路径资源分配…章节安排《计算机算法基础》，余祥宣、崔国华、邹海明著，华中科技大学出版社第一章导引与基本数据结构 √第二章分治法 √第三章贪心方法 √第四章动态规划 √第五章检索与周游 √第六章回溯法 √第七章分枝-限界 √第八章NP-问题 ⊙

预备知识数学：集合、证明方法（直接、间接、反证、反例、归纳假设）、对数基础、FLOOR&CEILING函数、阶乘、递归关系数据结构：链接表、图、树、二元树第一章导引与基本数据结构1.1算法的定义及特性什么是算法？一系列将问题的输入转换为输出的计算或操作步骤。

2.算法的五个重要特性确定性、能行性、输入、输出、有穷性1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。例：不符合确定性的运算5/0将6或7与x相加未赋值变量参与运算2）能行性算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。例：整数的算术运算是“能行”的实数的算术运算是“不能行”的3）输入每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域（或值域）4）输出一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。5）有穷性一个算法总是在执行了有穷步的运算之后终止。

计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。

准确理解算法和计算过程的区别：不能终止的计算过程：操作系统算法是“可以终止的计算过程”算法的时效性：只能把在相当有穷步内终止的算法投入到计算机上运行3.我们的主要任务算法学习将涉及5个方面的内容：1）设计算法：创造性的活动2）表示算法：思想的表示形式3）确认算法：证明算法的正确性程序的证明4）分析算法：算法时空特性分析5）测试程序：调试和作出时空分布图本课程集中于学习算法的设计与分析。通过学习，掌握计算机算法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基础4.算法描述语言自然语言,数学语言,流程图,程序设计语言等等.5.问题的求解过程2)建立数学模型1)问题的陈述3)算法设计用科学规范的语言,对所求解的问题做准确的描述.通过对问题的分析,找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述.根据数学模型设计问题的计算机求解算法.4)算法的正确性证明5)算法的程序实现6)算法分析证明算法对一切合法输入均能在有限次计算后产生正确输出.对执行该算法所消耗的计算机资源进行估算.将算法正确地编写成机器语言程序.1.2分析算法1.分析算法的目的在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。算法分析是计算机领域的古老而前沿的课题。进行算法分析的基本技术：抽象2.重要的假设和约定1）计算机模型的假设Turing机模型：计算机形式理论模型通用计算机模型：单处理器有足够的“内存”能在固定的时间内存取数据单元2）计算的约定确定使用什么样的运算及其执行时间。从计算时间上，运算的分类：

时间囿界于常数的运算：尽管每种运算的执行时间不同，但一般只花一个固定量的时间（单位时间）就可完成。

·基本算术运算，如整数、浮点数的加、减、乘、除

·字符运算

·赋值运算

·过程调用等2）计算的约定（续）其他运算：

·字符串操作：与字符串中字符的数量成正比

·记录操作：与记录的属性数、属性类型等有关

·

特点：运算时间无定量如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。

如：Tstring=Length（String）*tchar算法的执行时间=∑Fi*ti其中，Fi是算法中用到的某种运算i的次数，ti是该运算执行一次所用的时间。3）工作数据集的选择编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。测试数据集的生成作为算法分析的数据集：典型特征作为程序性能测试的数据集：对执行指标产生影响的性质3.如何进行算法分析？对算法进行全面分析，可分两个阶段进行：事前分析：就算法本身，通过对其执行性能的理论分析，得出关于算法特性——时间和空间的一个特征函数（Ο、Ω）——与计算机物理软硬件没有直接关系。事后测试：将算法编制成程序后实际放到计算机上运行，收集其执行时间和空间占用等统计资料，进行分析判断——直接与物理实现有关。1）事前分析目的：试图得出关于算法执行特性的一种形式描述，以“理论上”衡量算法的“好坏”。如何给出反映算法执行特性的描述？最直接方法：统计算法中各种运算的执行情况，包括：运用了哪些运算每种运算被执行的次数该种运算执行一次所花费的时间等。

算法的执行时间=∑Fi*ti频率计数例：x←x+yfori←1tondofori←1tondox←x+yforj←1tondorepeatx←x+yrepeatrepeat(a)(b)(c)分析：(a)：x←x+y执行了1次(b)：x←x+y执行了n次(c)：x←x+y执行了n2次定义：

频率计数：一条语句或一种运算在算法（或程序）体中的执行次数。

算法2.7插入分类procedureINSERTIONSORT(A,n)//将A(1：n)中的元素按非降次序分类，n≥1//1A(0)←-∞//设置初始边界值2forj←2tondo//A(1:j-1)已分类//3item←A(j);i←j-14whileitem<A(i)do//0≤i<j//5A(i+1)←A(i);i←i-16repeat7A(i+1)←item;8repeatendINSERTIONSORT

(8,5,4,9)(8,5,4,9)

(5,8,4,9)(5,8,

4,9)(4,5,8,9)(4,5,8,9)一条语句在整个程序运行时实际执行时间=

频率计数*每执行一次该语句所需的时间如何刻画算法执行特性的形式描述实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，没有统一的描述模型。在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。数量级

语句的数量级：语句的执行频率例：1，n，n2

算法的数量级：算法所包含的所有语句的执行频率之和。算法的数量级从本质上反映了一个算法的执行特性。例：假如求解同一个问题的三个算法分别具有n，n2，n3数量级。若n=10，则可能的执行时间将分别是10，100，1000个单位时间——与环境因素无关。计算时间/频率计数的表示函数通过事前分析给出算法计算时间（频率计数）的一个函数表示形式，一般记为与输入规模n有关的函数形式：f(n)注：最高次项与函数整体的关系空间特性分析（略）2）事后测试目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论——包括正确性、执行性能等，比较、优化所设计的算法。分析手段：作时、空性能分布图4.计算时间的渐近表示记：算法的计算时间为f(n)数量级限界函数为g(n)其中，n是输入或输出规模的某种测度。f(n)表示算法的“实际”执行时间—与机器及语言有关。g(n)是形式简单的函数，如nm，logn，2n，n!等。是事前分析中通过对计算时间或频率计数统计分析所得的、与机器及语言无关的函数。

以下给出算法执行时间：上界（О）、下界（Ω）、“平均”（）的定义。1）上界函数定义1如果存在两个正常数c和n0，对于所有的n≥n0，有|f(n)|≤c|g(n)|则记作f(n)=Ο(g(n))含义：如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数。f(n)的数量级就是g(n)。试图求出最小的g(n)，使得f(n)=Ο(g(n))。

多项式定理:定理1若A(n)=amnm+…+a1n+a0是一个m次多项式，则有A(n)=Ο(nm)即：变量n的固定阶数为m的任一多项式，与此多项式的最高阶nm同阶。

证明：取n0=1,当n≥n0时，有|A(n)|≤|am|nm+…+|a1|n+|a0|≤(|am|+|am-1|/n+…+|a0|/nm)nm

≤(|am|+|am-1|+…+|a0|)nm

令c=|am|+|am-1|+…+|a0|则，定理得证。计算时间的数量级对算法有效性的影响数量级的大小对算法的有效性有决定性的影响。例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n2和nlogn。则，n=1024：分别需要1048576和10240次运算。n=2048：分别需要4194304和22528次运算。分析：在n加倍的情况下，一个Ο(n2)的算法计算时间增长4倍，而一个Ο(nlogn)算法则只用两倍多一点的时间即可完成。算法2.8归并分类

procedureMERGESORT(low,high)//A(low:high)是一个全程数组，它含有high-low+1≥0个待分类的元素//integerlow,highiflow<highthen

mid←//计算中分点//callMERGESORT(low,mid)//在第一个子集合上分类(递归)//callMERGESORT(mid+1,high)//在第二个子集合上分类(递归)//callMERGE(low,mid,high)//归并已分类的两子集合//endifendMERGESORTMerge算法示例(4,5,8,9)|(1,2,6,7)

(1,2,4,5,6,7,8,9)参数：low=1;high=8;mid=4(4,5,8,9)|(1,2,6,7)hjjjjhh(14256789)j算法分类（计算时间）多项式时间算法：可用多项式（函数）对其计算时间限界的算法。常见的多项式限界函数有：

Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指数时间算法：计算时间用指数函数限界的算法常见的指数时间限界函数：

Ο(2n)<Ο(n！)<Ο(nn)说明：当n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。典型的计算时间函数曲线当数据集的规模很大时，要在现有的计算机系统上运行具有比Ο(nlogn)复杂度还高的算法是比较困难的。指数时间算法只有在n取值非常小时才实用。要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度，而不是（仅仅依靠）提高计算机的速度。计算时间函数值比较定义1.2如果存在两个正常数c和n0，对于所有的n≥n0，有|f(n)|≥c|g(n)|则记作f(n)=Ω(g(n))含义：如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个下界函数。试图求出“最大”的g(n)，使得f(n)=Ω(g(n))。2）下界函数定义1.3如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(n)|≤|f(n)|≤c2|g(n)|则记作含义：算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作：既有f(n)=Ω(g(n))，又有f(n)=Ο(g(n))3）“平均情况”限界函数4）限界函数的性质1）若且，则。即О具有传递性。（同）2）当且仅当3）若，则。即，定义了一个等价关系（等价类）5.常用的整数求和公式在算法分析中，在统计语句的频率时，求和公式的一般表示形式为：如：1+1+…+1（有n项1）=n1+2+…+n=n212+22+…+n2=n320+21+…+2n=2n+11.3关于SPARKS语言本书为描述算法选用的一种类计算机语言类PASCAL语言结构化程序描述1.基本语法成分1）数据类型：整型、实型、布尔型、字符型2）变量声明：integeri,j;booleanb;charc3）赋值运算：（变量）←（表达式）4）逻辑运算：andornot5）关系运算：＜≤＝≠≥＞6）变量声明：类型说明符变量；7）数组声明：integerA（1：5，7：20）8）控制结构：

顺序:分支:

·ifconditionthenS1elseS2endif

·case:cond1:S1;:cond2:S2;…:condn:Sn:else:Sn+1endcase循环:

·whileconddoSrepeat

·loopSuntilcondrepeat

·forvble←starttofinishbyincrementdoSrepeat

2.同质异项3.其它

函数的定义与调用、函数和过程、变量与形式参数1.4基本数据结构1.栈和队列栈和队列：n个元素的线性表利用动态数据结构——链表实现栈或队列利用静态数据结构——数组实现栈或队列基于以上两种表示形式的栈和队列上的基本运算队列的数组表示栈的数组表示用一维数组STACKS（1:n）表示栈底：STACKS（1）第i个元素STACKS(i)栈顶指针：topprocedureADD(item,STACAK,n,top)iftop≥nthencallSTACKFULLendiftop←top+1STACK(top)←itemendaddprocedureDELETE(item,STACK,top)iftop≤0thencallSTACKEMPTYendifitem←STACK(top)top←top-1endDELETE栈的数组表示——增加、删除栈的链接表表示一种单向链接表两个信息段：DATA存放数据，LINK指向前一节点节点插入callGETNODE(T)DATA(T)←itemLINK(T)←STACKSTACK←T节点删除item←DATA(STACK)T←STACKSTACK←LINK(SATCK)callRETNODE(T)ASTACK0栈的链接表表示——增加、删除2.树1）树的一般定义定义1.4树（tree）是一个或多个结点的有限集合，它使得：有一个指定为根（root）的结点剩余结点被划分成m≥0个不相交的集合：T1，…，Tm这些集合的每一个又都是一棵树，并称T1，…，Tm为根的子树。关于树的重要概念结点的度（degree）：一个结点的子树数树的度：树中结点度的最大值结点的级（level）（又叫层）：设根是1级，若某结点在p级，则它的儿子在p+1级树的高度（或深度）：树中结点的最大级数叶子（终端结点）：度为0的结点内结点（非终端结点）：度不为0的结点森林：m≥0个不相交树的集合。树的表示方法用链接表表示

每个结点三个信息段：TAG,DATA,LINK

TAG＝0，DATA存数据；TAG=1,DATA存链接信息，指向一棵子树2）二元树定义1.5二元树（binarytree）是结点的有限集合，它或者为空，或者由一个根和两棵称为左子树和右子树的不相交二元树所组成。二元树与度为2的树的区别二元树性质1：引理1.1一棵二元树第i级的最大结点数是2i-1。深度为k的二元树的最大结点数为2k-1,k>0。

特殊形态的二元树

满二元树：深度为k且有2k-1个结点的二元树

完全二元树：一棵有n个结点深度为k的二元树，当它的结点相当于深度为k的满二元树中编号为1到n的结点时，称该二元树是完全的。完全二元树的叶子结点至多出现在相邻的两级上。完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理1.2）。二元树的表示方法1.数组表示法：对于完全二元树，空间效率好；其他二元树，要浪费大量空间2.链表法：结构简单，有效。链表中每个结点有三个信息段，LCHILD,DATA和RCHILD③堆：堆是一棵完全二元树，它的每个结点的值至少和该结点的儿子们（如果存在的话）的值一样大（max-堆）（或小，min-堆）。

④二分检索树：二分检索树Ｔ是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：·Ｔ的左子树的所有元素比根结点中的元素小；·Ｔ的右子树的所有元素比根结点中的元素大；·Ｔ的左子树和右子树也是二分检索树。

注：二分检索树要求树中所有结点的元素值互异3.树的应用——不相交集合的合并及搜索问题问题描述：给定一个全集U，该集合包含n个元素很明显该集合包含多个不相交的子集某些应用需要实现这些不相交子集的合并、查找操作，并且这些操作最终可形成序列如何高效率实现这些操作序列就是我们要解决的问题集合操作举例n=10，U={1,2,3,4,5,6,7,8,9,10}s1={1,7,8,9};s2={2,5,10};s3={3,4,6}合并运算：s1∪s2={1,7,8,9,2,5,10}查找运算：元素4包含在s1,s2,s3的哪个集合中？方法一——位向量方法一：位向量s1={1,0,0,0,0,0,1,1,1,0}；s2={0,1,0,0,1,0,0,0,0,1}；利用位运算可得出s1∪s2={1,1,0,0,1,0,1,1,1,1}缺点：n很大，超过一个机器字长，而参与运算的集合的势很小时，运算与n成正比。方法二——集合元素表s1={1,7,8,9};s2={2,5,10}合并操作：|s1|+|s2|查找操作：最坏为|n|方法三——树数据结构字符数组U={1,2,3,4,5,6,7,8,9,10}子集s1={1,7,8,9};s2={2,5,10}则用数组Parent表示集合s1和s2：数组中记录的是节点U[i]的父节点在Parent中的位置（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）00……2…1112合并操作U(1,2)后：（Parent[1]=2）（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）20……2…1112查找元素F(9)U操作为常量时间，F操作则与查找元素在集合树中的层数有关。U和F的性能问题——退化树问题描述：有集合如下：（1）（2）…（n）000依次作下列操作：U(1,2),F(1),U(2,3),F(1),…,U(n-1,n)按照算法U和F，最终得到的树及时间耗费分析U：每次都是常量时间，因此总共是O(n-1)F(1)：2+3+…+(n-1)，因此是O(n^2)症结？合并操作！加权规则节点数少的树合并到节点数多的树中。字符数组U={1,2,3,4,5,6,7,8,9,10}子集s1={1,7,8,9};s2={2,5,10}（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）-4-3……2…1112UnionF序列演示分析Union(1,2),F(1),Union(2,3),F(1),…,Union(n-1,n)Union合并的开销较u要大，但仍然是常量时间每次查找1耗费时间为2，常量时间，则执行n-2次查找耗费时间为O(n)注意：本例的查找耗时不是最坏情况最坏情况由引理1.3给出引理1.3引理1.3设T是一棵由算法union所产生的有n个节点的树。在T中没有节点的级数会大于（logn的下界+1）证明：n=1，显然引理为真；i为T的级数，假设当i<=n-1时，引理为真，现证对于i=n，引理也为真；令k和j是形成树T的最后一次合并，即Union(k,j)；用count()表示数的节点数，假设count(j)=m，那么count(k)=n-m；不失一般性，可假设1<=m<n/2，则有m<=n-m；那么经Union合并后，j的父亲为k；如右图：则T的级数：1）等于k的级数：log(n-m)的下界+1<=（logn的下界+1）2）或者等于（j的级数+1）：（logm的下界+2）<=（log(n/2)的下界+2）<=（logn的下界+1）得证压缩规则更快的平均查找时间，适用于频繁查找操作例1.2在下图示例中实现8次对元素8的查找，用Find(8)算法实现总共20次，优于使用F的8*3=24次结论：对于m次Find和n次Union的混合序列（m>=n），处理时间接近O(m)，但稍差。详细描述见引理1.4。例1.24.图图Ｇ由称之为结点Ｖ和边Ｅ的两个集合组成，记为G=（V，E）。其中，Ｖ是一个有限非空的结点集合；Ｅ是结点对偶的集合，Ｅ的每一对偶表示Ｇ的一条边。有关图的的重要概念无向图：边的表示（ｉ，ｊ）有向图：边的表示〈ｉ，ｊ〉成本：带有成本的图称为网络邻接：结点的度（出度／