清华大学与数据结构 .ppt

* 例：设有两个算法在同一机器上运行，其执行时间分别为 100n2 和 2n，问：要使前者快于后者，n 至少要取多大？ 解答： 问题是找出满足 100n2 2n 的最小的n。用试探法： n = 13时，100n2 = 16900 2n = 8192 n = 14时，100n2 = 19600 2n = 16384 n = 15时，100n2 = 22500 2n = 32768 取 n = 15 满足要求。//渐进分析与某些常系数的影响 * 小结 数据结构的概念与表示 数据的基本逻辑结构与分类 数据的四种基本存储结构 抽象数据类型 算法的定义与五种特性 时间复杂度的渐进表示法 * 　　　　Ω表示法 大Ω表示 当且仅当存在正常数c和n0, 使得T(n)≥c g(n) 对所有 n≥n0都成立， 则称g(n) 给出了T(n)的一个下界。记为 　 T(n)＝ Ω(g(n)) 　大Ω表示法是对算法效率的一种乐观估计，对于规模为n的任意输入，算法的运行时间都不会低于Ω(g(n))。 * 　　　　Θ表示法 如果存在正常数 ab, n0, 和一个函数h(n) 使得对所有 n≥n0 , 都有 ， a*h(n) ≤ T(n) ≤ b*h(n) 则称h(n) 给出了T(n)的一个确界。记为 　 T(n)＝ Θ(h(n)) 　Θ表示是对算法效率的一种准确估计，对于规模为n的任意输入，算法的运行时间都与Θ(h(n))同阶。 * ?记号的其他表示 T(n) = ?(h(n)) 当且仅当 T(n) = O(h(n)) 且 T(n) = ?(h(n)) （证明方法） O ? ? T(n) 0 f(n) 　O、?, ?表示法的图形示意: * 1.4 算法定义 定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 特性： 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切无歧义的 有穷性 算法应在执行有穷步后结束 能行性 每一步运算应足够基本 * 几点说明 注意算法与计算方法的区别 具有算法的其它特征, 但不具有有穷性的特性 计算方法可以只保证理论上收敛； 算法与程序的区别 程序可以处于无休止的“等待”循环中； 算法描述可以有多种形式，如伪码、框图、表格、图形等 * 事例学习：选择排序问题 明确问题：排序后关键字呈递增(非递减)排列 解决方案：逐个选择当前的最小元素 算法框架： for (int i = 0; i n-1; i++) { //n-1趟 //从a[i]检查到a[n-1]; //若最小元素为a[k], 则将a[i]与a[k]交换; } 细化程序：程序 SelectSort 算法设计 自顶向下，逐步求精 * void selectSort ( int a[ ], const int n ) { //对n个元素a[0],a[1],…,a[n-1]按递增顺序排序 for (int i = 0; i n-1; i++) { int k = i; //从a[i]查到a[n-1], 找最小元素 其位置在k for (int j = i+1; j n; j++) if (a[j] a[k]) k = j; int temp = a[i]; a[i] = a[k]; a[k] = temp; } } //有改进余地(何时必须交换) * 算法简单性能分析与度量 算法的性能标准 算法的后期测试 算法的事前估计 * 算法的性能标准 正确性 (Correctness ) 算法应正确执行预定的功能和性能要求。 可读性(Readability) 算法应该容易阅读。以有利于阅读者对程序的理解。 效率(Efficiency) 效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。 健壮性 (Robustness) 算法应具有容错处理的功能。当输入非法数据时，算法应对其作出反应，而不应产生莫名其妙的输出结果。 * 算法的后期测试 对一个算法要作出全面的分析大致可分成两个阶段进行，即事前分析和事后测试 事前分析要求事前求出该算法的一个时间界限函数。 事后测试则要求在算法执行后通过算法执行的时间和实际占用空间的统计资料来分析。 事后分析要求在算法