数据结构基本概念—1.pptVIP

时间复杂性和度量 编译时间 与编译程序有关，与实例特性无关。 运行时间 从程序结构着手，统计算法的程序步数。 语法上或语义上有意义的一段指令序列 执行时间与实例特性无关 程序步数举例： 注 释：0 声明语句：0 表达式：1 赋值语句：0 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例 以迭代方式求累加和的函数 行 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； 建表，列出程序内各个语句的程序步数。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 在求累加和程序中加入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 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 程序的简化形式 void sum ( float a[ ], const int n ) { for ( int i=0; in; i++ ) count += 2; count += 3; } Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 注意： 一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。 例如：赋值语句 x = sum (R, n); 本身的程序步数为1； 一次执行对函数 sum (R, n) 的调用需要的程序步数为 2*n+3； 一次执行的程序步数为 1+2*n+3 = 2*n+4 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 时间复杂性的渐进表示法 全面分析一个算法，需要考虑在最坏、最好、平均情况下的时间代价。 大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))。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 大O表示法的使用 需要考虑关键操作的程序步数； 关键操作大多在循环和递归中； 在大多数场合中，程序步骤与执