算法分析的基本概念和方法.ppt

第第1 1章章 算法分析的基本概念和方法算法分析的基本概念和方法 内容提要 一、算法及其特性 二、算法的时间空间复杂度 三、算法分析(Algorithm Analysis) 1.分析算法时间复杂度的基本步骤 2.算法时间复杂度的有关概念 3.分析、求解算法复杂度的方法 四、最优算法(optimal algorithm) 知识要点 v算法分析的概念 复杂度渐近表示的记号：O, , 平均时间复杂度，最坏时间复杂度，最好时间复杂度 最优算法 v分析算法复杂度的基本方法 分析算法时间复杂度的步骤 基本运算执行频数的统计方法 v数学知识：求和公式、定积分近似求和、递归方 程的求解 学习要求 v掌握算法复杂度的基本概念 v熟悉算法复杂度分析的基本方法 1.1算法及其特性 v一、 算法(algorithm) 算法就是一组有穷的规则，它们规定了解决某 一特定类型问题的一系列运算。 v二、算法的五个特性 v确定性 v能行性 v有穷性 v输入 v输出 1.1算法及其特性 衡量算法性能一般有下面几个标准： 确定性 易读性 健壮性 算法的时间和空间性能：高效率和低存储空间 本课程中主要讨论算法的时间和空间性能，并以此作为衡 量算法性能的重要标准，而且主要侧重于时间方面。 三、衡量算法性能的标准 1.2. 算法的时间空间复杂度 v算法的时间复杂度：在算法运行期间所花费的时间。 v通常用渐进形式表示。比如，T(n)= O (n2)、 (n2) 或 (n2) 一、算法的时间复杂度(Time Complexity) 1.2. 算法的时间空间复杂度 v算法的空间复杂度：在算法运行期间所需要的内存空间， 通常指除开容纳输入数据之外的附加空间（auxiliary space, or work space）。 v通常用渐进形式表示。比如，S(n)= O(n2)、(n2)或 (n2) 二、算法的空间复杂度(Space Complexity) 1.2. 算法的时间空间复杂度 v 算法分析是指对于计算机算法的时间和空间复杂度进行 定量的分析。为了确切起见，假定执行算法的计算机是满 足如下条件的“通用型”计算机： 顺序处理机：每次执行程序中的一条指令； RAM足够大； 在固定的时间内可把一个数从一个单元取出或者存入。 下面将学习算法分析的主要内容： 分析算法时间复杂度的基本步骤 算法时间复杂度的有关概念 分析、求解算法复杂度的数学知识 三、 算法分析 (Algorithm Analysis) 1.3. 分析复杂度的基本步骤 v对算法的分析必须脱离具体的计算机结构和程序设计语言 。因此，比较两个算法的好坏，看其中所需的运算时间的 长短是由算法所需的运算次数决定的。任何一个算法都可 能有几种运算，因此，我们抓住其中影响算法运行时间最 大的运算作为基本运算。如在一个字表中寻找Z的问题， 把Z和表中元素的比较作为基本运算。两个实数矩阵相乘 的问题中，则把两个实数相乘作为基本运算。 一、选取一种运算作为基本运算(basic operation) 1.3. 分析复杂度的基本步骤 v一个计算步骤，如果其时间耗费总是不超过某个 常量，而与输入和算法无关，则称之为元运算。 元运算(elementary operation) 常见的元运算 v算术运算：加、减、乘、除； v比较和逻辑运算； v赋值运算，包括指针赋值（比如，在遍历表或树 时的指针赋值）；等等。 1.3. 分析复杂度的基本步骤 同一个问题对不同的输入，基本运算的次数亦可能不同 。因此，我们引进问题大小（即规模，size）的概念。例 如，在一个姓名表中寻找给定的Z的问题，问题的大小可 用表中姓名的数目表示。对于两个实数矩阵相乘的问题， 其大小可用矩阵的阶来表示。而对于遍历一棵二叉树的问 题，其大小是用树中结点数来表示等等。这样，一个算法 的基本运算的次数就可用问题的大小n的函数f(n)来表示。 二、表示出在算法运行期间基本运算执行的总频数 1.3. 分析复杂度的基本步骤 v 在一个算法中，出现的频数最高（在相差一个常数因子 的意义上）的元运算称为基本元算。 基本运算(basic operation) 常见的基本运算 v 当分析查找和排序的算法时，如果元素的比较是元运算， 则可作为基本运算； v在矩阵乘法的算法中，数的乘法可作为基本运算； v当遍历链表时，给指针赋值或者更新指针的操作可作为基 本运算； v在图的遍历中，可以将访问节点的操作为基本运算；等等 。 1.3. 分析复杂度的基本步骤 在实际中精确地求一个算法的基本运算次数f(n)等于多 少，往往不容易，甚至有时根本不可能，有些即使求出结 果很长，很繁琐，不易比较，需要简化。这时候我们可以 不精确地估计f(n)。此外，我们分析算法的时间目的主要 在于，能区分不同算法的优劣，在n很小时候，差别不大 ，随着n的逐渐增大，差别越来越大，是个极限行为。基 于上述原因，引进下面渐近表示的方法。复杂度渐近表示 可以将简洁地表示出复杂度的数量级别。 三 、渐近时间复杂度(asymptotic time complexity) 1.3. 分析复杂度的基本步骤 v设f(n)和g(n)均是从自然数集到非负实数集上的 函数。如果存在常数c0和一个自然数n0，使 得对于任意的nn0 ，均有 f(n)cg(n),则f(n)=O(g(n)。 v含义：阶至多为g(n)的函数，即上限。 v读法： O(g(n)读作“大Oh g(n)”。 1. O-记号 1.3. 分析复杂度的基本步骤 v设f(n)和g(n)均是从自然数集到非负实数集上的 函数。如果存在常数c0和一个自然数n0，使 得对于任意的nn0 ，均有 f(n)cg(n),则，f(n)= (g(n)。 v含义： 阶至少为g(n)的函数，即下限。 v读法： (g(n)读作“omega g(n)”。 2. -记号 1.3. 分析复杂度的基本步骤 v设f(n)和g(n)均是从自然数集到非负实数集上的 函数。如果存在一个自然数n0和两个正常数c1 ，c2，使得对于任意的nn0 ，均有 c1g(n)f(n)c2g(n),则，f(n)= (g(n)。 v含义： 阶恰好为g(n)的函数。 v读法： (g(n)读作“theta g(n)”。 3. -记号 1.3. 分析复杂度的基本步骤 例1 设f(n)=10n2+20n。则有 f(n)=O(n2) f(n)=(n2) f(n)= (n2) 例2 设f(n)=aknk+ak-1nk-1+a1n+ a0 ,(ak0)。则有 f(n)=O(nk) f(n)=(nk) f(n)= (nk) 四、举例 1.3. 分析复杂度的基本步骤 例3 设f(n)= 2n ，g(n)= n! 。则有 f(n)=O(g(n) 但是，f(n)(g(n) 因此，f(n) (g(n) 此时，记作O(f(n) int seqSearch(Type *a, int n, Type k) for(int i=0;i void insertion_sort(Type *a, int n) Type key; / cost times for (int i = 1; i =0 / c5 sum of (ti-1) j-; / c6 sum og (ti-1) aj+1=key; / c7 n-1 v在最好情况下，ti=1, for 1 i =2) return F(n-1)+F(n-2); 解：该算法的计算时间T(n)满足递归方程： T(n)=T(n-1)+T(n-2)+1, n1； 初始条件 T(0)=T(1)=0。 1.5. 分析和求解复杂度的方法 例3 用平摊的办法来统计基本操作的次数（Amortized Analysis） (1.13) 整型数组A(1：n)初始化为n个正整数的集合,双链表List初始化为仅含一个 元素0 for(j=1;j=n;j+) x=A(j); 将 x 插入到表List尾 if x 是偶数 then while 表List中x的前面元素为奇数 在表List中删除x的前面的那个元素 end while end if end for v解：算法的基本操作为元素的插入和删除操作。算法中插 入操作的次数为 n 次，而删除操作的次数最多为n-1次， 所以，算法的基本操作最少n次，最多2n-1次。 1.5. 分析和求解复杂度的方法 1典型的求和公式 0 i n f(i) 二、求解算法复杂度的基本方法 1.5. 分析和求解复杂度的方法 2. 积分近似求和 v 如果连续函数f(n)是单调递减的，则有 v 如果连续函数f(n)是单调递增的，则有 1.5. 分析和求解复杂度的方法 1.5. 分析和求解复杂度的方法 1.5. 分析和求解复杂度的方法 1.5. 分析和求解复杂度的方法 递归是一种重要的程序设计方法。有些问题的算法运用 递归过程来表示不仅自然简洁，而且也易于验证其正确性 。递归算法的特点就是：易读，易写，易证。递归和归纳 紧密相关。归纳定义的东西往往易写出其递归的算法；而 递归的算法往往可用归纳法来证明 。递归算法的时间复杂 度分析往往需要借助于求解递归方程或者递归不等式的解 得到。 递归方程的类型较多，涉及到的数学知识也较多。这里 我们仅简单地介绍分析算法复杂度时常见的几类简单递归 方程的求法。 三、递归关系 1.5. 分析和求解复杂度的方法 常用方法：展开法、差分方程法、换元法、数学归纳法等。 三、递归关系 1.5. 分析和求解复杂度的方法 （1） 线性非齐次递归方程 主要解法：差分方程法、数学归纳法等。 1.5. 分析和求解复杂度的方法 1.5. 分析和求解复杂度的方法 1.5. 分析和求解复杂度的方法