第数据结构与算法分析课件3章解读.ppt

数据结构与算法分析A Practical Introduction toData Structures and Algorithm Analysis陈 星  第3章 算法分析 疑问？ 通常对一个问题有多种解决方法(算法),如何挑选一种较好的方法？ → 了解方法（算法）的相对效率。 计算机编程的两大目标： 设计理解容易、编码简单和调试方便的算法。 → 软件工程 设计能够高效率地利用计算机资源的算法。 →数据结构和算法分析 如何检测算法的效率？ 实际测量算法的计算机运算时间。 问题：1. 需为每种算法都编写程序。 2. 代码质量对计算机耗时有影响。 3. 测试数据的选择对计算机耗时有影响。 4. 需要所有算法都运行一遍。 渐近算法分析（简称算法分析） 估算算法及实现它的程序的效率和开销。 计算机的关键资源 时间代价 空间代价（内存和磁盘空间） 分析算法效率的可行方法 可行的方法： 一定规模下，算法所需基本运算的执行次数。 基本运算的选择原则： 1、算法执行的运算总次数与基本运算的次数大体上成比例。 2、基本运算以外的其它运算的运算量可以忽略。 影响运行时间的因素 假设在代码质量、编译系统等与算法无关的因素 相同的条件下，影响某算法程序执行时间的因素： 1. 问题的规模。 运行时间T可以表示为规模n的函数T(n)。 2. 特定的输入。 问题规模对运行时间的影响 例1 : 查找数组元素中的最大值 int largest(int array[ ], int n) { int currlarge = 0; // Largest value seen for (int i=1; in; i++) // For each val if (array[currlarge] array[i]) currlarge = i; // Remember pos return currlarge; // Return largest } 问题的规模：数组的大小n 基本操作：整数的比较 设每次整数比较的时间为c，则运行时间 T(n) = cn 例2 : 将数组中第k元素赋给某变量 T(n) = c 常数运行时间：输入规模n对运行时间不产生影响。 例3 : sum = 0; for (i=1; i=n; i++) for (j=1; jn; j++) sum++; } T(n) = cn2 算法的增长率是指当输入的值增长时，算法代价的增长速率。 线性增长率： T(n) = cn 二次增长率： T(n) = cn2 指数增长率： T(n) = c1c2C3n …… 特定输入对运行时间的影响 例1 : 查找数组元素中的值为x的元素 int SearchX( int array[ ], int n ) { for (int i=1; in; i++) { // For each val if ( array[ i ] == x ) return i; } return 0; } 算法的最佳情况、最差情况、平均情况。 更快的计算机还是更快的算法？ 如果计算机的速度增快10倍？ T(n) n n’ Change n’/n 10n 1,000 10,000 n’ = 10n 10 20n 500 5,000 n’ = 10n 10 5n log n 250 1,842 n n’ 10n 7.37 2n2 70 223 n’ = n 3.16 2n 13 16 n’ = n + 3 ----- 渐近分析 当输入规模很大后，我们分析一种算法运行时间增长率时，可以忽略算法运行时间函数的系数。 上限 (大O表示法) 描述一种算法消耗某种资源（通常是时间）的最大值。 对非负函数T(n)，若存在两个正常数c和n0，对任意nn0，有T(n)≤cf(n)，则称T(n)在集合O(f(n))中。 例：某一算法平均情况下T(n)=