第二章 复杂性分析初步
程序性能(program performance)是指运行一个程序所需的内存大小和时间多少。所以,程序的性能一般指程序的空间复杂性和时间复杂性。性能评估主要包含两方面,即性能分析(performance analysis)与性能测量(performance measurement),前者采用分析的方法,后者采用实验的方法。
考虑空间复杂性的理由
在多用户系统中运行时,需指明分配给该程序的内存大小; 想预先知道计算机系统是否有足够的内存来运行该程序;
一个问题可能有若干个不同的内存需求解决方案,从中择取; 用空间复杂性来估计一个程序可能解决的问题的最大规模。 考虑时间复杂性的理由
某些计算机用户需要提供程序运行时间的上限(用户可接受的); 所开发的程序需要提供一个满意的实时反应。
选取方案的规则:如果对于解决一个问题有多种可选的方案,那么方案的选取要基于这些方案之间的性能差异。对于各种方案的时间及空间的复杂性,最好采取加权的方式进行评价。但是随着计算机技术的迅速发展,对空间的要求往往不如对时间的要求那样强烈。因此我们这里的分析主要强调时间复杂性的分析。
§1 空间复杂性
程序所需要的空间:
指令空间-用来存储经过编译之后的程序指令。程序所需的指令空间的大小取决于如下因素:
把程序编译成机器代码的编译器;
编译时实际采用的编译器选项;
目标计算机。
所使用的编译器不同,则产生的机器代码的长度就会有差异;有些编译器带有选项,如优化模式、覆盖模式等等。所取的选项不同,产生机器代码也会不同。此外,目标计算机的配置也会影响代码的规模。例如,如果计算机具有浮点处理硬件,那么,每个浮点操作可以转化为一条机器指令。否则,必须生成仿真的浮点计算代码,使整个机器代码加长。一般情况下,指令空间对于所解决的特定问题不够敏感。
数据空间-用来存储所有常量和变量的值。分成两部分:a).存储常量和简单变量;b).存储复合变量。前者所需的空间取决于所使用的计算机和编译
算法设计与分析 第一二章 引言 复杂性分析初步 算法设计与分析算法设计与分析隐藏>> 第一章 引 言 凡是学习了一种语言(不论是初级的还是高级的)程序设计课程...
算法设计与分析 第三章 图... 15页 免费 算法设计与分析 第一二章 ... ... 复杂性分析初步是研究复杂系统的基础复杂性分析初步是研究复杂系统的基础隐藏>>...
《算法设计与分析》-第七章 随机算法及计算复杂性_工学_高等教育_教育专区。...? 7.1 随机算法引言 7.2 随机算法的类型 7.3 随机数发生器 7.4 数值...
? ? 第1章算法设计与分析基础 第2章递归与分治...掌握算法分析常用数学方法 1.1 引言——算法的定义...1.3 算法复杂性分析 ? 算法复杂性 = 算法运行所...
第1章 基础算法设计与分析_IT/计算机_专业资料。...算法与程序 1.2 算法复杂性分析初步 本章教学要求...(many others) 12 1.1 算法与程序 例1-1 求两...
通过本课程的学习,使学生掌握算法设计的基本 方法,熟悉算法分析的基本技术,并能...第1章 算法分析基本概念引言算法的复杂性分析法 算法的时间复杂性分析 1.1 ...
第1章_基础算法设计与分析_计算机软件及应用_IT/...算法与程序 1.2 算法复杂性分析初步 本章教学要求...(many others) 12 1.1 算法与程序 例 1- 1 ...
第12-13 章简单介绍了NP完全性理论和计算复杂性, 这是当前计算机算法领域的...12 ? 算法设计与分析在 《计算机科学与技术》专业中的 地位 引言 1.1 ? ...
算法设计与分析高尚 关于本课程 ?课程目的:计算机...本章主要知识点: ? 1.1 引言 ? 1.2 算法复杂...约有12人是由于在算法与数据结构、计 算复杂性理论...
算法设计与分析耿国华第八章_数学_自然科学_专业...8.5小结 Chapter 8 引言---P、NP类问题描述 ? ...(3)进行问题计算复杂性分析的第一步是建立求解 ...
热门文档