《算法与算法分析.ppt

什么是算法？ 算法是对解决问题的方法的一种精确描述。 并非所有问题都有算法，有些问题经研究可行，则可能有相应算法；而有些问题经研究不可行，则没有相应算法。 因此，算法研究在某种意义上就是可行性研究。 算法的性质 算法可以理解为动作序列的有限集合 仅有一个初始动作 每个动作的后继动作是确定的 算法的终止表示问题得到解答或问题没有解答 算法分析与算法复杂度 算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性 算法的复杂度分时间复杂度和空间复杂度。 计算机理论科学中，按照计算复杂性研究问题求解的难易性，可把问题分为 P类、NP类 和 NP-完全类。 算法的效率 对于一个问题通常有多种解法（算法），应该选择哪一种呢？ 计算机程序设计的核心有两个目标（有时它们互相冲突） 设计一种容易理解、编码和调试的算法 设计一种能有效利用计算机资源的算法 算法的效率 (cont) 目标1涉及到软件工程原理 目标2涉及到数据结构与算法分析 本课程主要讲的是与目标2有关的问题 怎样度量算法的代价、效率呢？ 如何度量效率? 实验比较（运行程序） 渐近算法分析Asymptotic Algorithm Analysis 关键资源: 影响运行时间的因素: 对很多算法而言，运行时间依赖与输入的规模 执行算法所需要的时间T写成输入规模n的函数，记为T(n) 怎样比较两种算法解决问题的效率呢？ 实验比较 用源程序分别实现这两种算法，然后输入适当的数据运行，测算两个程序各自的开销 这是一种事后统计的方法 渐近算法分析(asymptotic algorithm analysis)，简称算法分析(algorithm analysis) 可以估算出当问题规模变大时，一种算法及实现它的程序的效率和开销 这是一种事前分析估算的方法 “规模”与“基本操作” 判断算法性能的一个基本考虑是处理一定“规模” (size)的输入时该算法所需执行的“基本操作” (basic operation)数 “规模”一般是指输入量的数目 比如，在排序问题中，问题的规模可以用被排序元素的个数来衡量 “规模”与“基本操作”（续） 一个“基本操作”必须具有这样的性质：完成该操作所需时间与操作数的具体取值无关 在大多数高级语言中，下列操作是基本操作： 赋值运算 简单算术运算 简单布尔运算 简单I／O操作 函数返回 n个整数累加不是基本操作 因为其代价依赖于n的值(即大小) 运行时间和增长率 由于影响运行时间的最主要因素一般是输入的规模，所以经常把执行算法所需要的时间T写成输入规模n的函数，记为T(n) 我们总是假设T(n)为非负值 算法的增长率(growth rate)是指当输入规模增长时，算法代价的增长速率 最佳、最差和平均情况 不是相同规模的所有输入的运行时间都相同 顺序有哪些信誉好的足球投注网站法（Sequential search）从一个n元一维数组中找出一个给定的值K : 从第一个元素开始，依次检索每一个元素，直到找到K为止 最佳情况: 最差情况: 平均情况: Growth Rate Graph 时间复杂度对解题速度的影响 算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性 算法的时间复杂度 规模 基本操作 增长率 平均情况 效率 渐近分析:大O 定义: 对于非负函数T(n)，若存在两个正常数c和n0，使得当nn0时有T(n)≤cf(n)， 则称T(n)在集合O(f(n))中。 用法: 这个算法[最佳、平均、最差]情况（下的增长率的上限）在O(n2)中. 含意: 对于问题的所有[最佳、平均、最差情况]输入，只要输入规模足够大(即 nn0), 该算法总能在cf(n) 步以内完成. 上限:大O (cont) 增长率的上限用符号O表示，称为大O表示法(big-Oh notation). Example: If T(n) = 3n2 then T(n) is in O(n2). 希望最“紧”（即最小）的上限: 虽然 T(n) = 3n2 可以说它在O(n3)中, 我们更喜欢用O(n2). 上限的例子 例1:考虑找出整数数组中某个元素的顺序检索法 (average cost). 如果访问并检查数组中的一个元素需要时间cs (cs为常数)， 那么在平均情况下T(n) = csn/2 。 当n 1时，csn/2 = csn ， 所以根据定义，T(n)在O(n)中，n0 =1，c = cs 上限的例子 例2:某一算法平均情况下 T(n) = c1n2 + c2n. c1、c2为正数。 当n 1，c1n2 + c2n = c1n2 + c2n2 = (c1 + c2)n2.