算法设计与分析课堂

1

算法设计与分析

DesignandAnalysisofAlgorithms2算法的应用[基因问题]人类基因工程的目标是识别人类DNA中的所有10万个基因，确定30亿个化学基对的序列，在数据库中存储这类信息并为数据分析开发工具，求解生物问题可采用复杂的算法，有效地使用资源以完成任务。算法设计与分析>教学安排3算法设计与分析>教学安排[网络中的问题]

使用算法解决数据传输寻找好的路由(最短路径问题),使用一个搜索引擎来快速的找到信息所在的网页(散列表、字符串匹配)。谷歌搜索业务负责人艾米特·辛格哈尔（AmitSinghal）日前在Google+上发表文章称，仅在去年一年，谷歌就对搜索进行了超过890次改进。他们每天都要对核心搜索算法进行一次修改。4算法设计与分析>教学安排

[旅行商问题]

设有n个城市，已知任意两城市之间距离，现有一推销员想从某一城市出发经过每一城市（且只经过一次）最后又回到出发点，问如何找一条最短路径。5生活中的算法算法设计与分析>教学安排同学们经常会面对一个共同的问题，就是有时有太多的事情要做.

如何合理安排各项事情，确保都能如期完成？如果根本不可能全部按期完成，你该怎么办？6例如：第17周上交报告的安排如下，16周周日早上发现什么报告都没有写，如何安排时间以确保每门课的报告都能如期完成？若不能全部按期完成，也能尽量使迟交报告的数目减到最小？算法设计与分析>教学安排学科算法设计与分析数据库原理计算机体系结构微机原理生物认证技术高级程序设计原理期限/星期几星期二星期五星期二星期四星期二星期一所需时间/天120.510.50.57算法如下：①把这些作业按到期日的顺序从左到右排列，从最早到期的到最晚到期的；②假设从左到右一项一项做这些作业的话，计算出从开始到完成某一项作业时所花的时间.

依次做此计算直到完成了所列表中的全部作业而没有一项作业会超期，停止；或算出某项作业将会超期，继续第三步；③考虑第一项将会超期的作业以及它左边的所有作业，从中取出花费时间最长的那项作业，并把它从表中去掉；④回到第二步，并重复第二到四步，直到做完.

算法设计与分析>教学安排8算法设计与分析>教学安排

为什么要学习算法？所有的计算机系统软件和应用软件都要用到各种类型的数据结构和算法。算法是一种像计算机硬件一样的技术现代计算机技术例如:有线与无线网络技术、图形用户界面、面向对象的系统都广泛依赖于算法。9算法设计与分析>教学安排

为什么要学习算法？“算法+数据结构=程序“——N.wirth对算法的研究被公认为是计算机科学的基石。

“算法不仅是计算机科学的一个分支，它更是计算机科学的核心。而且，可以毫不夸张地说，它同大多数科学、商业和技术都相关。”

——

DavidHarel10递归与分治动态规划贪心算法回朔法分支限界法随机化算法算法设计与分析算法设计与分析>教学安排寻找解决问题的众多个候选解中一个真正的解或者一个最好/较好的解.1、介绍算法设计的一般方法和策略11算法设计与分析>教学安排不同算法在效率方面有着显著的差别,可能比硬件和软件造成的差别要重要得多.例如:需要排序100万个数据,

计算机A每秒处理能力为(1GHz),计算机B每秒处理能力(100MHz)插入排序归并排序时间复杂度2n2

O(n2)

时间复杂度50nlgn

O(nlogn)12在给定的计算模型下，研究算法或问题的复杂性：上界、下界、平均以及问题固有复杂性2、对给定的算法如何分析它的运行效率（复杂性）算法设计与分析>教学安排算法设计与分析13

使学生掌握计算机算法的通用设计方法，学会分析算法的空间和时间复杂性。对一定的实际问题,能够设计求解算法并分析算法的效率。

算法设计与分析>教学安排课程目标14算法设计与分析>教学安排程序员必须知道的10大基础实用算法快速排序算法堆排序算法归并算法二分查找算法深度优先搜索算法

广度优先搜索算法

Dijkstra算法动态规划算法朴素贝叶斯分类算法15基本内容：

第一章算法概述

第二章递归与分治

第三章动态规划

第四章贪心算法

第五章回朔法

第六章分支限界法

第七章随机化算法预备知识:离散数学、数据结构、程序设计语言C、C＋＋算法设计与分析>教学安排16教材及参考书《计算机算法设计与分析》（第四版）王晓东电子工业出版社1.《IntroducitontoAlgorithms（第三版）》.

ThomasH.CormenCharlesE.LerisersonRonaldL.RivestCliffordStein著.殷建平等译.机械工业出版社2.《AlgorithmDesignFoundations,Analysis,andInternetExamples》.MichaelT.Goodrich,RobertoTamassia著.霍红卫译.人民邮电出版社3.《算法设计与分析》.屈婉玲等.清华大学出版社4.《算法设计技巧与分析》.M.H.Alsuwaiyel著.吴伟昶，方世昌等译.电子工业出版社5.计算机算法设计与分析习题解答.王晓东著.电子工业出版社算法设计与分析>教学安排17

算法设计与分析>教学安排学时安排:

课程总学时48，上课学时32其中上机学时为16学时.上机安排:

信息楼二楼考核办法:总成绩=平时成绩30%+试卷成绩70%

平时成绩=考勤+上机实验教学安排18算法设计与分析>教学安排教学要求19第一章算法概述第二章递归与分治策略第三章动态规划第四章贪心算法第五章回朔法第六章分支限界法第七章随机化算法算法设计与分析>目录20算法概述第一章

介绍算法设计的基本概念及算法分析的方法和准则.算法设计与分析211.1算法与程序1.2算法复杂度分析1.3

NP完全性理论算法设计与分析>第一章目录22“算法是任何定义好的计算程式，它取某些值或值的集合作为输入，并产生某些值或值的集合作为输出。”1.1算法与程序

>算法概述算法设计与分析>算法概述算法:是将问题的输入转化为输出的一系列计算或操作步骤.1算法定义及其特性

23算法设计与分析>算法概述注意：虽然绝大多数算法最终会靠计算机来执行，但算法概念本身并不依赖于这一假说。24>算法概述算法设计与分析>算法概述例：求两个不全为0的非负整数m,n的最大公约数

gcd(m,n)的欧几里德算法描述:1.如果n=0,返回m的值作为结果，过程结束；否则，进入第二步；

2.用n去除m，将余数赋给r;3.将n的值赋给m，将r的值赋给n,返回第一步。算法描述举例25计算机算法与人工算法>算法概述例如求定积分:s=

人工处理步骤为找出f(x)的源函数F(x)利用牛-莱公式:s=F(b)-F(a)算法设计与分析>算法概述有些问题没有计算机算法.有些问题计算机算法与人工算法不同.计算机算法：计算定积分采用数值积分的方法,得到一个近似解.26算法的特征1.有穷性

一个算法须在执行有限个运算步后终止,每一步必须在有限时间内完成.实际应用中,算法的有穷性应该包括执行时间的合理性.>算法概述算法设计与分析>算法概述

程序是算法的程序设计语言的具体实现.可不满足性质1.

一个算法面向一个问题，而不是仅仅求解一个问题的实例

操作系统程序：是一个在无限循环中执行的程序，而不是一个算法。27>算法概述算法设计与分析>算法概述例如计算分段函数f(x)=算法描述：输入变量x,1x>1000x<10若x大于100的数，输出1;若x小于10的数，输出0.输入10<=x<=100,则算法在异常情况下,执行结果是不确定的.2.确定性

算法的每一步骤必须有确定的含义,对每一种可能出现的情况,算法都应给出确定的操作,不能有多义性.283.能行性

算法中的每个步骤是能实现的,如x/0;负数开方…

算法的执行结果达到预期目的,正确,有效.4.输入

有0个或多个输入项.>算法概述算法设计与分析>算法概述5.输出

算法产生至少有一个输出项291.问题的陈述理解问题，并用科学规范的语言把所求解问题进行准确的描述,包括所有已知条件和输出要求.2.建立数学模型

通过对问题分析,找出其中所有操作对象以及对象之间的关系,并用数学语言加以描述.对非数值型解法来说,数学模型通常是链表,树,图,集合等数据结构.

2.算法设计过程(程序设计过程)算法设计与分析>算法概述303.算法设计

根据数据模型,给出求解问题的一系列步骤,且这些步骤可通过计算机的各种操作来实现.4.算法的正确性证明

算法的正确性:对一切合法的输入,算法均能在有限次的计算后产生正确的输出.算法设计与分析>算法概述5.算法的程序实现

将一个算法描述正确地编写成机器语言程序.31>问题的求解过程>算法概述6.算法分析

对执行该算法所消耗的计算机资源进行估算,对数值型算法还需分析算法的稳定性和误差等问题.

计算机资源中最重要的是时间和空间资源,执行一个算法程序需要的时间和占用的内存空间分别称为算法的时间复杂度和空间复杂性

.算法设计与分析>算法概述32算法的复杂性分析具有极重要的实际意义。有许多实际应用问题,理论上是有计算机解的,但由于求解所需的时间或或空间耗费巨大,如成千上万年,以至于实际上无法办到；对有些时效性很强的问题,如实时控制,即使算法执行时间很短,只有一两秒,也可能是无法忍受的。算法设计与分析>算法概述33算法设计与分析>算法概述算法评估标准：正确性,运算时间,占用空间,简单性,健壮性34

描述算法的方式一般有三种:自然语言,流程图,伪代码语言。

伪代码描述介于自然语言与程序设计语言之间。3.算法的描述>算法概述算法设计与分析>算法概述35>算法概述算法设计与分析>算法概述36>算法概述算法设计与分析>算法概述开始输入aa>=0?输出“输入的数据非法”b=a+10输入b结束YN

(1)椭圆：表示起始、终止

(2)平行四边形：输入输出

(3)菱形：判断

(4)矩形：执行表达式和赋值

(5)开口矩形：注释框

(6)箭头：数据流向37>算法概述算法设计与分析>算法概述{}缩进表示块结构,while循环退出后计数器保持其值,//表示注释,

i=j=e表示将e的值赋给i和j,一般不使用全局变量,过程调用按传值参数处理384.算法结构>算法概述算法设计与分析>算法概述任何算法都可由顺序结构、选择结构、循环结构这三块“积木”通过组合和嵌套表达出来，遵循这种方法的程序设计，即为结构化程序设计。39数值型算法:算法中的基本运算为算术运算.非数值型算法:算法中的基本运算为逻辑运算.串行算法:串行计算机上执行的算法.并行算法:并行计算机上执行的算法.从处理方式上5.算法分类从解法上>算法概述算法设计与分析>算法概述本课程主要介绍非数值型的串行算法.40算法的复杂性:指执行算法所消耗或占用的资源的数量一个算法所需资源越多,我们就说它的复杂性越高,反之则低.>算法复杂性分析

时间复杂性空间复杂性算法的复杂性1.2算法的复杂性分析>算法概述算法设计与分析>算法概述41考虑空间复杂性的理由在多用户系统中运行时，需指明分给该程序的内存大小；需预先知道计算机系统是否有足够的内存来运行该程序；一个问题可能有若干个不同的内存解决方案，从中择取；用空间复杂性估计一个程序可能解决的问题的最大规模。算法设计与分析>算法概述42>算法复杂性分析>算法概述算法设计与分析>算法概述考虑时间复杂性的理由某些计算机用户需要提供程序运行时间的上限（用户可接受的）；所开发的程序需要提供一个满意的实时反应。43>算法复杂性分析>算法概述算法设计与分析>算法概述算法分析:(渐进算法分析):对执行算法所消耗或占用的资源进行估算,给出算法耗费的限界函数.需解决两个问题:如何度量复杂性?如何分析复杂性?44

算法的复杂性:算法运行所需的时间和空间的数量.它与算法求解问题的规模n,算法的输入数I

及算法本身有关.

例如在数组中找分量c,n:数组中分量的个数两个矩阵相乘,n:矩阵的维数表中排序,n:数组中分量的个数遍历一棵树,n:树中节点数1.复杂性的计量>算法复杂性分析问题的规模n:指问题的输入数据或初始数据的量.

在不同的问题中,n有不同的表现形式：>复杂性的计量>算法概述算法设计与分析>算法概述45算法设计与分析>算法概述

算法效率与计算机的性能有关，但此因素对所有算法的影响相同。5*5的矩阵相乘与10*10矩阵的矩阵相乘所需时间空间均不相同；<问题规模不同>找c在数组A中的位置,c=A(1),与c=A(100),所需时间显然也不同<输入数不同>顺序查找还是折半查找速度也是不一样的.

<算法不同>算法设计与分析>算法概述46令n:问题规模I:输入数据A:算法本身C:算法的复杂性,则

C=f(n,I,A)

将时间复杂性和空间复杂性分别考虑,并用T和S表示.则有:T=T(n,I,A)S=S(n,I,A)将算法A隐含在函数名中,不同函数名代表不同算法,则简化为

T=T(n,I)S=S(n,I)算法设计与分析>算法概述47设一台抽象计算机提供的元运算有k种,记作O1,…,Ok;设这些元运算每执行一次所需时间分别为t1,…,tk

;设在算法A中用到Oi的次数为ei,i=1,…,k,则ei=ei(n,I)

T=T(n,I)=

当问题的规模n和算法确定后,T是输入变元I的函数.仅以时间复杂性为例将复杂性函数具体化.>算法复杂性分析>复杂性的计量>算法概述算法设计与分析>算法概述48总结：

我们不可能对规模为n的每一种合法输入I都计算ei次，因为输入可能是无穷集合,我们只能对规模为n的问题的某类具有代表性的合法输入统计相应的ei.>算法复杂性分析>复杂性的计量>算法概述算法设计与分析>算法概述49最好情况:Tmin(n)=T(n,I)=

==最坏情况:Tmax(n)=T(n,I)=

==平均情况:Tavg(n)==其中Dn:规模为n的所有合法输入的集合Dn中达到Tmin(n)的一个输入.Dn中达到Tmax(n)的一个输入.P(I):出现输入为I的概率>算法复杂性分析>复杂性的计量>算法概述算法设计与分析>算法概述50例题1-1插入排序.长度为n的一个待排序数组A[1..n],算法在数组A中重排这些数,其中使用常数个外部存储.算法设计与分析>算法概述

输入:n个数的一个序列<a1,a2,…,an>

输出:输入序列的一个排列<a’1,a’2,…,a’n>,满足a’1≤a’2≤…≤a’n

实例--输入:<8,5,7,9,6,4>

--输出:<4,5,6,7,8,9>51Insertion-Sort(A)

//插入排序算法forj=2toA.lengthkey=A[j]//将A[j]插入到数组A[1..j-1]中i=j-1whilei>0andA[i]>keyA[i+1]=A[i]i=i-1A[i+1]=key算法设计与分析>算法概述1nijsortedkey52654321469758初始654321469758j=2654321469785j=3654321469875j=4654321469875j=5654321498765j=6-∞-∞-∞-∞-∞-∞算法设计与分析>算法概述53算法设计与分析>算法概述Insertion-Sort(A)forj=2toA.lengthkey=A[j]//将A[j]插入到数组A[1..j-1]中i=j-1whilei>0andA[i]>keyA[i+1]=A[i]i=i-1A[i+1]=key代价次数t1nt2n-10n-1t4n-1t5

t6t7t8n-1t

表示每次执行的时间，ej

表示对应值j

执行的次数循环语句退出时，执行测试的次数比执行循环体的次数多154算法设计与分析>算法概述插入排序.运行时间

T(n),得到如果输入数组已排序，则出现最佳情况运行时间

T(n),得到：我们把该运行时间表示为an+b，其中常量a和b依赖于语句代价55如果输入数组已反向排序，必须将每个元素A[j]与整个已排序子数组A[1..j-1]比较，有ej=j,则出现最坏情况运行时间

T(n),得到：我们把该运行时间表示为an2+bn+c，其中常量a,b,c依赖于语句代价算法设计与分析>算法概述56算法设计与分析>算法概述平均情况:所有数据的出现概率相等ej=(j+1)/2，运行时间

T(n),得到：我们把该运行时间表示为an2+bn+c，其中常量a,b,c依赖于语句代价57>算法复杂性分析>渐进性态>算法概述算法设计与分析>算法概述当一个问题的输入规模很大时,算法的结构又很复杂时,采用前面介绍的精确分析就显得过于繁琐,为降低算法分析的代价,同时又保证估算的精确度,引入一个简化的计算模型来评估算法的开销.称为渐进分析.渐进分析是对问题的规模充分大的算法开销的估算。1.T(n)的渐进复杂性(渐进表达式):(T(n)-)/T(n)0，n

时2.渐进阶:O,,

3.渐进阶分析的规则:(最坏情况,8条)4.递归过程的渐进分析582.复杂性的渐进性态如果存在一个函数使得当n,有

(T(n)-)/T(n)0称是T(n)当n

时的渐进性态或渐进复杂性>算法复杂性分析1.渐进性态>渐进性态>算法概述算法设计与分析>算法概述设T(n)为算法A的时间复杂性函数(输入值固定.如Tmax,Tmin,Tavg),则它是n的单增函数。59当n充分大时用代替T(n)作为算法复杂性的度量,以简化分析

例如T(n)=3n2+4nlogn+7,则可以是3n2

>算法复杂性分析>渐进性态>算法概述算法设计与分析>算法概述在数学上,T(n)与有相同的最高阶项.可取为略去T(n)的低阶项后剩余的主项.比较两个算法时，如果他们的阶不同，就可分出效率高低。故此时只需关心最高限的阶即可。可忽略最高项系数或低阶项。602.渐进性态的阶例如3n=O(n),n+1024=O(n),n2=O(n3)?n3=O(n2)?2n2+11n-10=O(n2)若正常数c和自然数N0

使得当n

N0

时,有f(n)cg(n)

则称函数f(n)在n充分大时有上界,且g(n)是它一个上界.记为f(n)=O(g(n)),也称f(n)

的阶不高于g(n)的阶.

设f(n)和g(n)是定义在正整数集上的正函数,(1)大O表示法(算法运行时间的上限)>算法复杂性分析>渐进性态>算法概述算法设计与分析>算法概述√≠61>算法复杂性分析>渐进性态三点注意:1．用来作比较的函数g(n)应该尽量接近f(n).

例如3n+2=O(n2)松散的界限；3n+2=O(n)较好的界限2．不要产生错误界限。

例如n2+100n+6，当n<3时，n2+100n+6<106n，由此就认为n2+100n+6＝O(n).3．f(n)=O(g(n))不能写成g(n)=O(f(n))

因为两者并不等价。实际上，这里的等号并不是通常相等的含义。>算法复杂性分析>渐进性态>算法概述算法设计与分析>算法概述621.O(f)+O(g)=O(max(f,g))2.O(f)+O(g)=O(f+g)3.O(f)·O(g)=O(f·g)4.如果g(n)=O(f(n)),则O(f)+O(g)=O(f)5.f=O(f)6.O(cf(n))=O(f(n))>渐进性态>算法概述算法设计与分析>算法概述运算规则63证明:O(f)+O(g)=O(max(f,g))算法设计与分析>算法概述设F(N)=O(f).根据O的定义,存在正常数C1和自然数N1,使得对所有N≥N1,有F(N)≤C1f(N).类似G(N)=O(g).根据O的定义,存在正常数C2和自然数N2,使得对所有N≥N2,有G(N)≤C2g(N).令C3=max{C1,C2},N3=max{N1,N2},h(N)=max{f,g},则对所有N≥N3,有

F(N)≤C1f(N)≤C1h(N)≤C3h(N).类似

G(N)≤C1g(N)≤C2h(N)≤C3h(N).O(f)+O(g)=F(N)+G(N)≤C3h(N)+C3h(N)=2C3h(N)=O(h)=O(max(f,g))64

例估计如下二重循环的

Tmax(n)的阶.分析:内循环体只需O(1)时间,故fori:=1tondoforj:=1toido{s1,s2,s3,s

4};s1,s2,s3,s4为单一赋值语句外循环共需内循环共需

>渐进性态>算法概述算法设计与分析>算法概述2.O(f)+O(g)=O(f+g)65(2)大

表示法(算法运行时间的下限）若正常数c和自然数N0使得当n

N0

时,有f(n)c

g(n)

则称函数f(n)在n充分大时有下限,且g(n)是它的一个下限,记为f(n)=(g(n))也称f(n)的阶不低于g(n)的阶>渐进性态>算法复杂性分析>算法概述算法设计与分析>算法概述例

T(n)=c1n2+c2n,

则

T(n)=(n2),

66

f(n)=(g(n))等价于f(n)=O(g(n))且f(n)=(g(n))称函数f(n)与g(n)同阶.(3)

表示法例

T(n)=c1n2+c2n,

则

T(n)=(n2)算法设计与分析>算法概述67>算法复杂性分析>渐进性态>算法概述算法设计与分析>算法概述Cg(n)f(n)F(n)=O(g(n))对于所有n≥n0,f(n)≤Cg(n)68>算法复杂性分析>渐进性态>算法概述算法设计与分析>算法概述Cg(n)f(n)

f(n)=

(g(n))对于所有n≥n0,f(n)≥Cg(n)69>渐进性态>算法概述算法设计与分析>算法概述>渐进性态>算法概述算法设计与分析>算法概述C1g(n)f(n)C2g(n)C1g(n)对于所有n≥n0,C2g(n)≥f(n)≥C1g(n)70不同时间函数的增长率>渐进性态>算法复杂性分析>算法概述算法设计与分析>算法概述71>算法复杂性分析>渐进性态>算法概述算法设计与分析>算法概述不同时间复杂性函数的对比可见，不同T(n)的算法当n增长时运算时间增长的快慢很不同。T(n)为指数形式的算法当n较大时实际上是无法应用的。有些算法T(n)与n！成正比，它随n的加大比指数函数增长还要快，这种算法更是没有实用价值。凡是T(n)为n的对数函数、线性函数或多项式的(幂函数也是多项式的特例)，称为“有效算法”。72多项式阶算法(有效算法):若算法的最坏情形时间复杂度T(n)=O(nk);指数阶算法:若算法的最坏情形时间复杂度T(n)=Ω(an),a>1.这类算法可认为计算上不可行的算法