数据结构课件C版第一章.ppt

* mayan 算法性能分析与度量 --算法效率的度量 事实上，算法运行时间要受输入规模、利用编译程序生成的目标代码的质量、计算机程序指令系统的品质和速度等制约。 * mayan 算法性能分析与度量 --算法效率的度量 算法的事前估计 算法的事前估计主要包括时间复杂性和空间复杂性的分析： 问题的规模：如：矩阵的阶数、图的结点个数、被分类序列的正整数个数等。 时间复杂性：算法所需时间和问题规模的函数，记为 T(n)。当 n??时的时间复杂性，称为渐进时间复杂性。 空间复杂性：算法所需空间和问题规模的函数。记为 S(n)。当 n??时的空间复杂性，称为渐进空间复杂性。 * mayan 算法性能分析与度量 --算法效率的度量 空间复杂度度量 存储空间的固定部分 程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间 可变部分 尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间 * mayan 算法性能分析与度量 --算法效率的度量 时间复杂度度量 程序步的概念 程序步：语法上或语义上有意义的一段指令序 列，而且这段指令序列的执行时间与问题规模 无关。 例如：声明语句：程序步数为0; 表达式：程序步数为1。 程序步确定方法 a) 插入计数全局变量count。 b) 建表，列出各语句的程序步。 * mayan 算法性能分析与度量 --算法效率的度量 通过插入计数全局变量count，计算程序步 例：以迭代方式求累加和的函数 float sum (float a[ ], int n) { float s = 0.0; for (int i = 0; i n; i++) s = s + a[i]; return s; } * mayan 算法性能分析与度量 --算法效率的度量 在求累加和程序中加入 count 语句 float sum (float a[ ], int n) { float s = 0.0; count++; //count 统计执行语句条数 for (int i = 0; i n; i++) { count += 2; //针对 for 语句 s += a[i]; count++; } //针对赋值语句 count += 2; //针对 for 的最后一次 count++; //针对 return 语句 return s; } 执行结束得程序步数 count = 3*n+4 * mayan 算法性能分析与度量 --算法效率的度量 为统计程序步，程序的简化形式： void sum (float a[ ], int n) { for (int i = 0; i n; i++) count += 3; count += 4; } * mayan 算法性能分析与度量 --算法效率的度量 注意： 一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。 例如： 赋值语句x = sum (R, n) 本身程序步数为 1； 一次执行对函数 sum (R, n) 的调用需要的程序步数为 3*n+4； 一次执行的程序步数为 1+3*n+4 = 3*n+5 * mayan 算法性能分析与度量 --算法效率的度量 通过建表，列出各语句的程序步 程序语句 一次执行所需程序步数 执行频度 程序步数 { 0 1 0 float s = 0.0; 1 1 1 for (int i = 0; i n; i++) 2 n+1 2(n+1) s = s + a[i]; 1 n n return s; 1 1 1 } 0 1 0 总程序步数 3n+4 * mayan 算法性能分析与度量 --算法效率的度量 算法的渐进分析 算法的渐进分析直接与它所求解的问题的规模n相关，通常将问题规模作为分析的参数，求算法的时间和空间开销与问题规模n的关系。 时间复杂度的渐进表示法 算法中所有语句的频度之和是矩阵阶数n的函数 T(n) = 3n3 + 5n2 + 4n +2 一般地，称 n 是问题的规模。则时间复杂度 T(n) 是问题规模 n 的函数。 * mayan 算法性能分析与