数据结构第01章概论3.pptVIP

1.3.2算法的时间和空间复杂性 一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量，算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。 算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n的数据处理问题，用T(n)表示算法基本操作的执行次数。 平均情况和最坏情况 Best Case Running Time: 同样的输入规模，不同的数据分布情况下，最快情况的运行时间。 Worst Case Running Time: 同样的输入规模，不同的数据分布情况下，最慢或运行步数最多时的运行时间。 Average Case Running Time: 同样的输入规模，不同的数据分布情况下，平均所需的运行时间，通常指概率平均或期望值 。 评价一个算法的一般作法： （1）合理地选择一个或几个操作作为“标准操作”。 （2）计算量=给定输入下执行标准操作的次数。 事实：一个算法的计算量通常依赖于问题的规模。 为了便于讨论，我们把问题规模假定为n，则算法在问题规模（Size）为n的输入下的计算量为T（n）。 定义：设f（n）与g（n）是定义在正整数集合上的两个函数，如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n) ︳≦c.g(n) 则记作 f(n)=O(g(n)) 。也就是说对几乎所有的n值，函数f（n）以函数g（n）为上界。 渐近记号（一） f (n)=O(g(n))表明，当 n→∞ 时， f (n)趋于无穷大的阶不大于(即小于等于) g(n)趋于无穷大的阶. 例1：证明n2/2+3为O（n2） 证明：要使n2/2+3c* n2 有c ?+3/ n2 当n 6时，必有1/2+ 3/n2〈1 故取c=1，n0=3，则对任意n3，有 n2/2+3〈c* n2 故n2/2+3为O（n2） 渐近记号（二） ⑵ 大? 记号： 定义: f (n)=Ω(g(n)) 意味着存在正常数 C 和 n0 ,使得 当 n ≥ n0 , 均有 0≤ C g(n) ≤f (n) 成立。 f (n)=Ω (g(n))表明，当 n→∞ 时， f (n)趋于无穷大的阶不小于 g(n) 趋于无穷大的阶. 渐近记号（三） ⑶ 大Θ 记号： 定义: f (n)=Θ(g(n)) 意味着存在正常数C1, C2和n0使 得当n≥n0 , 均有 0≤C1g(n)≤f (n)≤C2g(n)成立。 f (n)=Θ(g(n))表明，当 n→∞ 时， f (n) 和g(n)趋于无穷大的阶是相同的。 退出 * * * * 李云清 杨庆红 揭安全 高等学校精品课程 人民邮电出版社 （第2版） 什么是数据结构 数据类型和抽象数据类型 算法和算法分析 第一章 概述 瑞士著名的计算机科学家Nicklaus Wirth在1976年出版了一本书，书名为《算法+数据结构 = 程序设计》，它正说明了数据结构在程序设计中的作用。程序设计的实质即为计算机处理问题编制一组指令，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构即为问题的数学模型。　　很多数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述，而大量非数值计算问题的数学模型正是本门课程要讨论的数据结构。 第一章 概述 　　例1、求 n 个整数中的最大值。这似乎不成问题，但如果这些整数的值有可能达到1012，那么对32位的计算机来说，就存在一个如何表示的问题。 　　例2、交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、直行和右拐，那么如何控制这些红绿灯既使交通不堵塞，又使流量最大呢？若要编制程序解决问题，首先要解决一个如何表示的问题。 　　例3、煤气管道的铺设问题。如图需为城市的各小区之间铺设煤气管道，对 n 个小区只需铺设 n-1 条管线，由于地理环境不同等因素使各条管线所需投资不同(如图上所标识)，如何使投资成本最低？这是一个讨论图的生成树的问题。 A B H I G C E D F 18 12 9 79 52 56 31 10 85 98 67 21 45 8 34 （a）城市距离图 A B H I G C E D F 12 9 79