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

算法分析基础

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(上界)


1.3.2大 O 比率定理


只要极限值是一个正数,即有界限。则极限分母是上界,若极限等于0,则是一个松散上界估计。


1.3.3渐近符号 Ω(下界)



注意求极限的分子分母!!!

1.3.4渐近符号 Θ(双界)






1.3.5 简化 Master 定理











算法分析基础