数据结构算法与应用-c++语言描述002

《数据结构算法与应用-c++语言描述002》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、下载下载第2章程序性能以下是本章中所介绍的有关程序性能分析与测量的概念：¥确定一个程序对内存及时间的需求。¥使用操作数和执行步数来测量一个程序的时间需求。¥采用渐进符号描述复杂性，如O、、、o。¥利用计时函数测量一个程序的实际运行时间。除了上述概念以外，本章还给出了许多应用代码，在后续章节中将可以看到，这些代码有很多用处。这些应用包括：¥在一个数组中搜索具有指定特征的元素。本章中所使用的方法是顺序搜索和折半搜索。¥对数组元素进行排序。本章给出了计数排序、选择排序、冒泡排序及插入排序的实现代码。¥

2、采用Horner法则计算一个多项式。¥执行矩阵运算，如矩阵加、矩阵转置和矩阵乘。2.1引言所谓程序性能（programperformance），是指运行一个程序所需要的内存大小和时间。可以采用两种方法来确定一个程序的性能，一个是分析的方法，一个是实验的方法。在进行性能分析（performanceanalysis）时，采用分析的方法，而在进行性能测量（performancemeasurement）时，借助于实验的方法。程序的空间复杂性（spacecomplexity）是指运行完一个程序所需要的内存

3、大小。对一个程序的空间复杂性感兴趣的主要原因如下：¥如果程序将要运行在一个多用户计算机系统中，可能需要指明分配给该程序的内存大小。¥对任何一个计算机系统，想提前知道是否有足够可用的内存来运行该程序。¥一个问题可能有若干个内存需求各不相同的解决方案。比如，对于你的计算机来说，某个C++编译器仅需要1MB的空间，而另一个C++编译器可能需要4MB的空间。如果你的计算机中内存少于4MB，你只能选择1MB的编译器。如果较小编译器的性能比得上较大的编译器，即使用户的计算机中有额外的内存，也宁愿使用较小的编

4、译器。¥可以利用空间复杂性来估算一个程序所能解决的问题的最大规模。例如，有一个电路模拟程序，用它模拟一个有c个元件、w个连线的电路需要280K+10*（c+w）字节的内存。如果可利用的内存总量为640K字节，那么最大可以模拟c+w≤36K的电路。程序的时间复杂性（timecomplexity）是指运行完该程序所需要的时间。对一个程序的时间复杂性感兴趣的主要原因如下：¥有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限，程序将被强制结束。一种简易的办法是简单地指定时间上限为几千年。然而这种

5、办法可能会造成严重的财政问题，因为如果由于数据问题导致你的程序进入一个死循环，你可能需要为你所使用的机时付出巨额资金。因此我们希望能提供一个稍大于所期望运行时间的时间上限。第2章程序性能31下载¥正在开发的程序可能需要提供一个满意的实时响应。例如，所有交互式程序都必须提供实时响应。一个需要1分钟才能把光标上移一页或下移一页的文本编辑器不可能被众多的用户接受；一个电子表格程序需要花费几分钟才能对一个表单中的单元进行重新计值，那么只有非常耐心的用户才会乐意使用它；如果一个数据库管理系统在对一个关系进

6、行排序时，用户可以有时间去喝两杯咖啡，那么它也很难被用户接受。为交互式应用所设计的程序必须提供满意的实时响应。根据程序或程序模块的时间复杂性，可以决定其响应时间是否可以接受，如果不能接受，要么重新设计正在使用的算法，要么为用户提供一台更快的计算机。¥如果有多种可选的方案来解决一个问题，那么具体决定采用哪一个主要基于这些方案之间的性能差异。对于各种解决方案的时间及空间复杂性将采用加权的方式进行评价。练习1.给出两种以上的原因说明为什么程序分析员对程序的空间复杂性感兴趣？2.给出两种以上的原因说明为

7、什么程序分析员对程序的时间复杂性感兴趣？2.2空间复杂性2.2.1空间复杂性的组成程序所需要的空间主要由以下部分构成：¥指令空间（instructionspace）指令空间是指用来存储经过编译之后的程序指令所需的空间。¥数据空间（dataspace）数据空间是指用来存储所有常量和所有变量值所需的空间。数据空间由两个部分构成：1)存储常量（见程序1-1至1-9中的数0、1和4）和简单变量（见程序1-1至1-6中的a、b和c）所需要的空间。2)存储复合变量（见程序1-8和1-9中的数组a）所需要的空

8、间。这一类空间包括数据结构所需的空间及动态分配的空间。¥环境栈空间（environmentstackspace）环境栈用来保存函数调用返回时恢复运行所需要的信息。例如，如果函数fun1调用了函数fun2，那么至少必须保存fun2结束时fun1将要继续执行的指令的地址。1.指令空间程序所需要的指令空间的数量取决于如下因素：¥把程序编译成机器代码的编译器。¥编译时实际采用的编译器选项。¥目标计算机。在决定最终代码需要多少空间的时候，编译器是一个最重要的因素。图2-1给出了用来计算表达式a+b+b*c