ch2算法分析(2).pptVIP

王 璐 dqx_wl@163.com 中原工学院计算机学院 2010-9 ch2 算法分析 算法分析的目的 通过对算法分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好算法，改进差算法，避免无益的人力和物力浪费。 算法分析的基本原则 正确性 方法的正确性证明 软件测试 工作量——时间复杂性分析 分析目的:改进算法/程序运行时间上限/实时系统的要求 占用空间——空间复杂性分析 存储中间结果或操作单元所占用空间——额外空间 简单性 简单的算法效率不一定高,需要折中. 最优性 寻找求解某类问题中效率最高的算法 算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。 这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。 如何进行算法分析？ 事前分析：就算法本身，通过对其执行性能的理论分析，得出关于算法特性——时间和空间的一个特征函数（Ο、Ω）——与计算机软硬件没有直接关系。 事后测试：将算法编制成程序后放到计算机上运行，收集其执行时间和空间占用等统计资料，进行分析判断——直接与物理实现有关。 1）事前分析 目的：试图得出关于算法执行特性的一种形式描述，以“理论上”衡量算法 “好坏”。 如何给出反映算法执行特性的描述？ 最直接方法：统计算法中各种运算的执行情况： 运用了哪些运算 每种运算被执行的次数 该种运算执行一次所花费的时间 算法的执行时间=∑Fi*ti 频率计数：算法中语句或运算的执行次数。 例： x=x+y for (i =1;i=n;i++) for (i =1;i=n;i++) x=x+y; for (j=1;j=n;j++) x=x+y; (a) (b) (c) 分析： (a)： x=x+y执行了1次 (b)： x=x+y执行了n次 (c)： x=x+y执行了n2次 注：在事前分析中，只限于确定与所使用机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。 数量级(阶) 语句的数量级：语句的执行频率。例：1，n ，n2 算法的数量级：算法包含所有语句的执行频率之和。 算法的数量级从本质上反映了一个算法的执行特性. 通过事前分析给出算法计算时间（频率计数）的一个函数表示形式，一般记为与输入规模n有关的函数形式：T(n) 例：求解同一问题的三个算法分别具有n, n2 , n3数量级。 若n=10，则可能的执行时间将分别是10，100，1000 个单位时间——与环境因素无关。 计算时间的数量级对算法有效性的影响 数量级的大小对算法的有效性有决定性的影响。 例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n2和nlogn。则： n=1024：分别需要1048576和10240次运算。 n=2048：分别需要4194304和22528次运算。 分析：在n加倍的情况下，一个Ο(n2)的算法计算时间增长4倍，而一个Ο(nlogn)算法则只用两倍多一点的时间即可完成。 计算时间的渐近表示 记：算法的计算时间为f(n) 数量级限界函数为g(n) 对于f(n) ，如果存在函数g(n) ，使得当N→ ∞使有(f(n) - g(n))/ f(n) →0，那么我们就说g(n)是f(n)当N→ ∞时的渐近性态。 在数学上， g(n)是f(n)当N→ ∞时的渐近表达式。 例如：3N2+4NlogN+7与3N2。 其中， g(n)是形式简单的函数，即数量级(阶),如nm，logn，2n，n!等。 以下给出渐进意义下的算法复杂性评价：上界（О）、下界（Ω）、“平均”（ ）的定义。 渐进意义下的记号：O,?, 定义1 如果存在