算法分析基础

首页 > 代码库 > 算法分析基础

2024-07-28 08:29:22 223人阅读

1、程序的性能

程序的性能由时间复杂度和空间复杂度决定。

1.1空间复杂度

程序所需要的空间主要由以下部分构成：
 指令空间。存储经过编译之后的程序指令。指令有操作数和操作码构成。
 数据空间。存储所有常量和所有变量值所需的空间。
 环境栈空间。保存函数调用返回时恢复运行所需要的信
息。

（1）指令空间
程序所需指令空间的大小取决于如下因素：
 把程序编译成机器代码的编译器。所使用的编译器不同，
则产生的机器代码长度就会有所差异。
 编译时实际采用的编译器选项。有些编译器带有选项，如
优化模式、覆盖模式等等。所取的选项不同，产生的机器
代码也会不同。
 目标计算机。目标计算机的配置也会影响代码的规模。例
如，如果计算机具有浮点处理硬件，那么，每个浮点操作
可以转化为一条机器指令。否则，必须生成仿真的浮点计
算代码，使整个机器代码加长。

（2）数据空间
分成两部分：存储常量和简单变量；存储复合变量。
 存储常量和简单变量。取决于所用的计算机和编译器，以
及变量与常量的数目。
 存储复合变量。包括数据结构所需的空间及动态分配的空
间。
（3）环境栈空间
调用一个函数时，下面数据保存在环境栈中：
 返回地址。
 所有局部变量的值、传值形式参数的参数值。
 所有引用参数的定义。

所以一个程序所需要的空间可分为两部分：
① 固定部分。独立于实例特征，主要包括指令空间、简单变
量以及定长复合变量占用的空间、常量占用的空间。
② 可变部分。主要包括复合变量所需空间、动态分配的空间、
递归栈所需要的空间。
 复合变量所需的空间依赖于所解决的具体问题。
 动态分配的空间和递归栈所需要的空间依赖于实例特征

例：template <class T> //
int Find( const T a[], int n, const T&x)
{ int i ;
for(i = 0; i<n&& a[i] != x; ++i){}
return(i== n) ? -1: i ;
}

问题。在a[0..(n-1)]中搜索x，
若找到则回所在的位置，否
则返回-1。
 实例特征。采用数组的长度n
作为实例特征。
 分析。数组地址a需要4字节，参数x需要4字节，n需要4
字节，局部变量i需要4字节，整数常量-1需要4字节，总
共需要20字节，独立于n，所以＝
Find
( ) 0 S n 。
 注意。数组a所需要的空间是在其他函数中分配的，不能
算作函数Find所需要的空间。

1.2时间复杂度

一个程序所占时间 ( ) T P =编译时间+运行时间。
 编译时间与实例特征无关，而且，一个编译好的程序可以
运行若干次，所以，人们主要关心运行时间。

1.3渐近符号

1.3.1渐近符号 O（上界）