《数据结构 基本概念-1》课件.ppt

时间复杂性和度量 编译时间 与编译程序有关，与实例特性无关。 运行时间 从程序结构着手，统计算法的程序步数。 语法上或语义上有意义的一段指令序列 执行时间与实例特性无关 程序步数举例： 注 释：0 声明语句：0 表达式：1 赋值语句：0 例 以迭代方式求累加和的函数 行 float sum ( float a[ ], const int n ) 1 { 2 float s = 0.0; 3 for ( int i=0; in; i++ ) 4 s += a[i]; 5 return s; 6 } 程序步确定方法 在程序中插入计数全局变量count； 建表，列出程序内各个语句的程序步数。 在求累加和程序中加入count语句 float sum ( float a[ ], const int n ) { float s = 0.0; count++; //count是全局变量，统计执行语句条数 for ( int i=0; in; i++ ) { count++; //针对for语句 s += a[i]; count++; } //针对赋值语句 count++; //针对for的最后一次 count++; //针对return语句 return s; } 执行结束得 程序步数count =2 * n + 3 程序的简化形式 void sum ( float a[ ], const int n ) { for ( int i=0; in; i++ ) count += 2; count += 3; } 注意： 一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。 例如：赋值语句 x = sum (R, n); 本身的程序步数为1； 一次执行对函数 sum (R, n) 的调用需要的程序步数为 2*n+3； 一次执行的程序步数为 1+2*n+3 = 2*n+4 时间复杂性的渐进表示法 全面分析一个算法，需要考虑在最坏、最好、平均情况下的时间代价。 大O表示法——最坏情况 当且仅当存在正整数c和n0，使得T(n)≤cf(n)对所有的n≥n0成立，则称该算法的渐进时间复杂度为T(n)=O(f(n))。 当实例特性n充分大时，算法的时间复杂度随n变化，在最坏情况下若存在一个增长的上界，即cf(n) ，则该算法的时间复杂度增长的数量级为f(n) ，即称该算法的渐进时间复杂度为T(n)=O(f(n))。 大O表示法的使用 需要考虑关键操作的程序步数； 关键操作大多在循环和递归中； 在大多数场合中，程序步骤与执行频度一一对应。 如果给出的是渐进值，可直接考虑关键操作的执行频度，提出其与实例特性n的函数关系g(n)，从而得到渐进时间复杂度。 渐进时间复杂度的计算 单个循环 在循环内的简单语句即为关键操作，该程序段的渐进时间复杂度应是此关键操作的执行频度的大O表示。 几个并列的循环 先分析每个循环的渐进时间复杂度，然后利用大O表示法的加法规则来计算渐进时间复杂度。 大O表示法的加法规则 当两个并列的程序段的时间代价分别为T1(n)=O(f(n))和T2(m)=O(g(m))时， 则将两个程序段连在一起后整个程序段的时间代价为： T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m))) 所谓(max (f (n), g (m))，是指当n与m充分大时f (n)与g (m)中的大值，具有如下关系： c log2n n nlog2n n2 n3 2n 3n n! 取c、log2n、n、nlog2n时间效率比较高； 取n2、n3时间效率差强人意； 取2n、3n、n!当n稍微大一点，算法的时间代价变为很大，以至于不能计算。 两个并列循环的例子 void example (float x[ ][ ], int m, int n, int k) { float sum [ ]; for ( int i=0; im; i++ ) { //x[ ][ ]中各行 sum[i] = 0.0; //数据累加 for ( int j=0; jn;