算法分析第一章导论

1主讲教师：孙成敏[e-mail]2015年3月---2015年6月计算机算法设计与分析2课程设置类别：专业必修课学分：3学分理论学时：48习题课学时：8开课周数：1-14周3基本内容导引（第一、二章）基本的算法设计策略分治法（第四章）贪心方法（第五章）动态规划（第六章）回溯法（第八章）分支－限界法（第九章）基本算法分析方法NP-难度和NP-完全问题（第十章）4学习目标掌握基本的算法设计方法掌握进行算法分析的基本方法（时间、空间复杂度分析）灵活运用基本的算法设计方法，解决实际问题5参考书目计算机算法设计与分析王晓东电子工业计算机算法设计与分析苏德富电子工业6算法分析课程开始这门课程和其他课程的区别是什么?从这门课程上我能学到哪些东西是在别的课程上学不到的。这门课程的研究范畴是什么?这门课程的知识可以用来解决什么类型的问题，应用到什么领域。7问题能解决吗？假设某一负责人交给你一个很难的任务，几天后询问你问题解决了没有。可能会发生如下图这样的情况：问：“交给你的问题，解决方法想出来了吗？”答：“我找不到一个有效的方法来解决它，没能完成任务。”8问：“交给你的问题，解决方法想出来了吗？”答：“我找不到一个有效的方法来解决它，因为这样的方法是不存在的。”要证明一个问题不存在有效的方法，往往比寻找一种有效方法更难。9问：“交给你的问题，解决方法想出来了吗？”答：“我找到了一方法来解决它，理论上可实现的，但是以我们目前的力量实现它是不可能的。”方法消耗的资源太大了。问题解决的好吗？10现实世界的两个问题问题能解决吗？(可计算性)问题解决的好吗？(计算复杂性)11可计算性研究的范畴计算机虽然神通广大，还是在人的控制下工作。计算机并非什么都能做，有的事情理论上它根本做不了。讨论哪些事计算机能做，哪些事计算机做不了，属于可计算性理论研究的范畴。12一个满足可计算性的问题26个英文字母全排列，它的排列数为26！≈4×1026以每年365天计算，共有365×24×3600＝3.1536×107秒。以每秒能完成107个排列的超高速电子计算机来做这项工作，需要4×1026/(3.1536×107×107)≈1.2×1012年（千亿年）。13有一些问题虽然在理论上能够由计算机解决，但因其算法占用资源太多而无法实际完成，因此需要选择其他算法或改进算法。要知道算法的优劣好坏，就要对算法需要多少计算时间和存储空间做定量的分析。算法分析研究的范畴迄今为止，已有20%左右的计算机科学家因其在计算复杂性方面的研究工作而获得图灵奖。14本课程的计算机本课程指的计算机是和图灵机计算能力等价的、冯诺伊曼体系结构计算机，即确定性图灵机。量子计算机是非确定性图灵机，其算法和计算复杂性完全不同。15几个典型的非数值计算问题巡回推销员问题n皇后问题背包问题16巡回推销员问题[动态规划]设有n个城市，已知任意两城市间之距离，现有一推销员想从某一城市出发巡回经过每一城市（且每城市只经过一次），最后又回到出发点，问如何找一条最短路径。试一试求出最短路径。17n皇后问题[回溯法]这是高斯1850年提出的一个著名问题：国际象棋中的“皇后”在横向、竖向和斜向都能走步和吃子，问在nn格的棋盘上如何能摆上n个皇后而使她们都不能互相吃。当n很大时，问题很难。对于n8，现已知此问题共有92种解，但只有12种是独立的，其余的都可以由这12种利用对称性或旋转而得到。设n4，试一试。18背包问题有一旅行者要从3种物品中选取不超过50公斤重的行李随身携带，要求总价值最大。物品1重10千克，价值60元；物品2重20千克，价值100元；物品3重30千克，价值120元。[动态规划]物品不可分割的前提下，求总价值最大。[贪心算法]物品可以分割的前提下，求总价值最大。19发展历史D.Knuth《TheArtofComputerProgramming》A.V.Aho,J.Hopcroft,J.Ullman《TheDesignandAnalysisofcomputerAlgothms》ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest《IntroductiontoAlgorithms》20第二章导引与基本数据结构2.1算法2.2分析算法及数学基础2.3用SPARKS语言写算法2.4基本数据结构（略）212.1算法什么是算法算法的重要特性计算过程与算法的区别问题的求解过程算法学习的基本内容22什么是算法算法是解决一确定类问题的任意一种特殊的方法。数值计算方法非数值计算方法算法的非形式描述：算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。求解数值问题，插值计算、数值积分等。求解非数值问题，主要进行判断比较。23算法的五个重要特性确定性：每一种运算必须要有确切的定义，无二义性；能行性：运算都是基本运算，原则上能在有限时间内完成；输入：有0个或多个输入；输出：一个或多个输出；有穷性：在执行了有穷步运算后终止；仅仅有穷还不够，还要在现代计算机上有效才行。24计算过程与算法的区别计算过程可以不满足算法的性质(5)有穷性。例如操作系统，当没有任务时，操作系统并不终止，而是处于等待状态，直到有新的任务启动，因而不是一个算法。程序算法数据结构(ByWirth)25问题的求解过程证明正确性分析算法理解问题精确解或近似解算法设计策略选择数据结构设计算法设计程序26算法学习的基本内容如何设计算法如何表示算法如何确认算法如何分析算法如何测试程序27如何设计算法面对具体问题，运用一些基本设计策略，规划算法。被实践证明是有用的计算机科学、运筹学、电器工程等领域设计出很多精致有效的好算法掌握这些策略，设计出更多的好算法。28如何表示算法设计的算法要用恰当的方式表示出来采用结构程序设计的方式SPARKS程序设计语言——简单明了29如何确认算法算法确认(algorithmvalidation)——证明该算法对所有可能的合法输入，都能给出正确答案算法确认的目的——确保该算法能正确无误地工作穷举法推理——数学归纳法、反证法构造性证明测试30如何分析算法分析执行一个算法时，占用CPU时间完成运算；占用存储器的存储空间，存放程序和数据。即对一个算法需要多少计算时间和存储空间，做定量分析。31测试程序调试——调试只能指出有错误，而不能指出它们不存在错误。源于程序正确性的证明还没有取得突破性进展。时空分布图用各种给定数据执行调试后的程序测定计算时间和空间印证之前的分析是否正确指出实现最优化的有效逻辑位置32第二章导引2.1算法2.2分析算法及数学基础2.3用SPARKS语言写算法2.4基本数据结构332.2分析算法算法分析目的算法分析的准备工作计算时间的渐进表示一些证明方法作时空性能分布图34算法分析的目的算法分析(analysisofalgorithms)是对一个算法需要多少计算时间和存储空间作定量的分析。——确定算法在什么样的环境下能够有效地运行。分析在最好、最坏和平均情况下的执行情况。——对同一问题不同算法的有效性作出比较。35算法运行假定的计算机类型要求独立于具体的软硬件环境单纯分析算法。假定使用一台通用计算机顺序处理每条指令；存储容量足够大；存取时间恒定。//第1次课程36第二章作业1.证明：n2O(n3)；2.证明：2n211n10O(n2)；3.证明：O的以下两个性质成立，其中c是一个正常数：O(f(n))O(g(n))O(f(n)g(n))；O(cf(n))O(f(n))；4.证明：n3O(n2)；37判断以下命题是否成立，若成立，证明之；不成立，举反例。5.如果g(n)(f(n))，则(f(n))(g(n))(f(n))；？6.(cf(n))(f(n))，其中c是一个正常数；？7.f(n)(f(n))；？8.(f(n))(g(n))(min(f(n),g(n))；？9.(f(n))(g(n))(max(f(n),g(n))；？10.(f(n))(g(n))(f(n)g(n))；？38算法分析过程确定算法所涉及的运算分析算法语句的执行次数分析算法的执行时间的渐进表示确定出能反映算法在各种情况下工作的数据集作时空性能分布图事前分析准备工作事后测试全面分析的两个阶段39准备工作(一)首先确定使用哪些运算以及执行这些运算所用的时间。基本运算由一些更基本的任意长序列的运算所组成的复杂运算40基本运算时间囿界于常数的运算加、减、乘、除整数算术运算浮点算术、字符比较、对变量赋值、过程调用等每种运算所用时间虽然不同，但都只花费一个固定量的时间41复杂运算由一些更基本的任意长序列的运算组成如：两个字符串的比较运算一系列字符比较指令一个字符的比较时间——囿界于常数字符串比较的时间总量则取决于字符串的长度42准备工作(二)其次是要确定出能反映算法在各种情况下工作的数据集。编造出能产生最好、最坏和有代表性情况的数据配置通过使用这些数据来运行算法，以更了解算法的性能。算法分析最重要和最富于创造性的工作。43全面分析算法的两个阶段事前分析(aprioranalysis)确定每条语句的执行次数。求出该算法的一个时间限界函数(一些关于参数的函数)事后测试(aposteriortesting)收集此算法的实际执行时间和占用空间的统计资料44算法的执行时间同一条语句在一个算法中的执行次数(frequencycount)称为频率计数语句的时间总量频率计数执行一次该语句所需要的时间算法的执行时间就是构成算法的所有语句的执行时间总量之和由算法就可直接确定，与所用的机器无关，且独立于程序设计语言。依赖机器、程序设计语言、编译程序45例：计算语句xxy在下面三个程序段中的频率计数beginxxyendFC:1beginfori1tondoxxyendFC:nbeginfori1tondoforj1tondoxxyendFC:n2语句的数量级是指执行它的频率计数之和算法的数量级是指算法的所有语句的执行频率之和确定一个算法的数量级十分重要，因为它在本质上反映了算法所需的计算时间。46计算时间的基本特性描述算法数量级的多项表达式最高次项最高次项的系数最高次项的次数×××√准确分析出算法数量级的多项式表达式是很困难的，因此我们对事前分析的计算时间进行渐进表示。47时间复杂性的形式化定义算法的时间复杂性表示为T(n)，其中n是问题的规模。最坏情况下：Tmax(n)max{T(I)|size(I)n}最好情况下：Tmin(n)min{T(I)|size(I)n}平均情况下：Tavg(n)P(I)T(I)其中I是问题规模为n的实例，p(I)是实例I出现的概率。size(I)n48计算时间的渐进表示定义2.1：f(n)O(g(n))定义2.2：f(n)(g(n))定义2.3：f(n)(g(n))定理2.149f(n)表示算法的计算时间n表示问题的规模输入或输出量；两者之和；其中之一的某种测度。g(n)是在事前分析中确定的某个形式简单的函数变量和函数的含义f(n)与机器和语言有关，而g(n)是独立于机器和语言的。50定义2.1如果存在两个正常数c和n0，对于所有的nn0，有|f(n)|c|g(n)|，则记做f(n)O(g(n)).当n充分大时，f(n)有上界，一个常数倍的g(n)是f(n)的一个上界，f(n)的数量级就是g(n)。f(n)的阶不高于g(n)的阶。在确定f(n)的数量级时，总是试图求出最小的g(n)。有关证明中，找出c和n0是关键。51例子判断f(n