内蒙古大学《算法与数据结构》讲义02程序性能
45页1、下载第2章程 序 性 能以下是本章中所介绍的有关程序性能分析与测量的概念: 确定一个程序对内存及时间的需求。 使用操作数和执行步数来测量一个程序的时间需求。 采用渐进符号描述复杂性,如 O、 、o。 利用计时函数测量一个程序的实际运行时间。除了上述概念以外,本章还给出了许多应用代码,在后续章节中将可以看到,这些代码有很多用处。这些应用包括: 在一个数组中搜索具有指定特征的元素。本章中所使用的方法是顺序搜索和折半搜索。 对数组元素进行排序。本章给出了计数排序、选择排序、冒泡排序及插入排序的实现代码。 采用Horner 法则计算一个多项式。 执行矩阵运算,如矩阵加、矩阵转置和矩阵乘。2.1 引言所谓程序性能( program performance) ,是指运行一个程序所需要的内存大小和时间。可以采用两种方法来确定一个程序的性能,一个是分析的方法,一个是实验的方法。在进行性能分析( performance analysis)时,采用分析的方法,而在进行性能测量( p e r f o r m a n c em e a s u r e m e n t)时,借助于实验的方法。程序的空间复杂性(s
2、pace complexity)是指运行完一个程序所需要的内存大小。对一个程序的空间复杂性感兴趣的主要原因如下: 如果程序将要运行在一个多用户计算机系统中,可能需要指明分配给该程序的内存大小。 对任何一个计算机系统,想提前知道是否有足够可用的内存来运行该程序。 一个问题可能有若干个内存需求各不相同的解决方案。比如,对于你的计算机来说,某个C + +编译器仅需要1 M B的空间,而另一个C + +编译器可能需要4 M B的空间。如果你的计算机中内存少于4 M B,你只能选择1 M B的编译器。如果较小编译器的性能比得上较大的编译器,即使用户的计算机中有额外的内存,也宁愿使用较小的编译器。 可以利用空间复杂性来估算一个程序所能解决的问题的最大规模。例如,有一个电路模拟程序,用它模拟一个有 c个元件、w个连线的电路需要2 8 0 K + 1 0 *(c+w)字节的内存。如果可利用的内存总量为6 4 0 K字节,那么最大可以模拟c+w3 6 K的电路。程序的时间复杂性(time complexity)是指运行完该程序所需要的时间。对一个程序的时间复杂性感兴趣的主要原因如下: 有些计算机需要用户
3、提供程序运行时间的上限,一旦达到这个上限,程序将被强制结束。一种简易的办法是简单地指定时间上限为几千年。然而这种办法可能会造成严重的财政问题,因为如果由于数据问题导致你的程序进入一个死循环,你可能需要为你所使用的机时付出巨额资金。因此我们希望能提供一个稍大于所期望运行时间的时间上限。 正在开发的程序可能需要提供一个满意的实时响应。例如,所有交互式程序都必须提供实时响应。一个需要 1分钟才能把光标上移一页或下移一页的文本编辑器不可能被众多的用户接受;一个电子表格程序需要花费几分钟才能对一个表单中的单元进行重新计值,那么只有非常耐心的用户才会乐意使用它;如果一个数据库管理系统在对一个关系进行排序时,用户可以有时间去喝两杯咖啡,那么它也很难被用户接受。为交互式应用所设计的程序必须提供满意的实时响应。根据程序或程序模块的时间复杂性,可以决定其响应时间是否可以接受,如果不能接受,要么重新设计正在使用的算法,要么为用户提供一台更快的计算机。 如果有多种可选的方案来解决一个问题,那么具体决定采用哪一个主要基于这些方案之间的性能差异。对于各种解决方案的时间及空间复杂性将采用加权的方式进行评价。练习1.
4、 给出两种以上的原因说明为什么程序分析员对程序的空间复杂性感兴趣?2. 给出两种以上的原因说明为什么程序分析员对程序的时间复杂性感兴趣?2.2 空间复杂性2.2.1 空间复杂性的组成程序所需要的空间主要由以下部分构成: 指令空间(instruction space)指令空间是指用来存储经过编译之后的程序指令所需的空间。 数据空间(data space)数据空间是指用来存储所有常量和所有变量值所需的空间。数据空间由两个部分构成:1) 存储常量(见程序1 - 1至1 - 9中的数0、1和4)和简单变量(见程序1 - 1至1 - 6中的a、b和c)所需要的空间。2) 存储复合变量(见程序 1 - 8和1 - 9中的数组a)所需要的空间。这一类空间包括数据结构所需的空间及动态分配的空间。 环境栈空间(environment stack space) 环境栈用来保存函数调用返回时恢复运行所需要的信息。例如,如果函数f u n 1调用了函数f u n 2,那么至少必须保存f u n 2结束时f u n 1将要继续执行的指令的地址。1. 指令空间程序所需要的指令空间的数量取决于如下因素: 把程序编译
5、成机器代码的编译器。 编译时实际采用的编译器选项。 目标计算机。在决定最终代码需要多少空间的时候,编译器是一个最重要的因素。图 2 - 1给出了用来计算表达式a + b + b * c + ( a + b - c ) / ( a + b ) + 4的三段可能的代码,它们都执行完全相同的算术操作(如,每个操作符都有相同的操作数) ,但每段代码所需要的空间都不一样。所使用的编译器将确定产生哪一种代码。第2章程 序 性 能3 1下载L O A DaL O A DaL O A DaA D DbA D DbA D DbS TO R Et 1S TO R Et 1S TO R Et 1L O A DbS U BcS U BcM U LTcD I Vt 1D I Vt 1S TO R Et 2S TO R Et 2S TO R Et 2L O A Dt 1L O A DbL O A DbA D Dt 2M U LcM U LcS TO R Et 3S TO R Et 3A D Dt 2L O A DaL O A Dt 1A D Dt 1A D DbA D Dt 3A D D4S U BcA D Dt
《内蒙古大学《算法与数据结构》讲义02程序性能》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》讲义02程序性能》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页