空间复杂度Sp(n)

1.定义

指程序运行时所需的内存空间大小和实例特征的函数关系。

2.程序运行时所需空间包括

指令空间:与实例特征无关的常数;

数据空间:常量和简单变量-与实例无关;

​ 复合变量-数组,链表,树和图等;

​ 环境栈空间-函数调用-是否递归;

复合变量所需空间尝尝和问题实例特征有关;

3.计算

S§=c+Sp(instance characteristics)

其中c为常量(实例无关部分),Sp为可变部分。在使用解析方法研究程序p的空间复杂度时仅考虑Sp。在分析空间复杂度时我们忽略与实例特征无关的空间需求量。

4.例题

1
2
3
4
5
6
7
8
9
10
template <class T>
int SequentialSearch(T a[], const T& x, int n)
{
//Search the unordered list a[0:n-1] for x.
//Return position if found; Return -1 otherwise.
int i;
for(i=0;i<n&&a[i]!=x;i++)
if(i==n) return -1;
return i;
}

实例特征:n,S(n)=0;

该程序所占空间均为常量,与实例特征无关,所以S(n)=0。

时间复杂度T(n)

1.定义

指程序执行时所用的时间。

2.计算

在使用解析方法时程序p的时间复杂度表示为输入量的函数T。

在解析地分析时间复杂度时,使用以下两种时间单位并计算:

​ 操作步数(operation count):算法的基本操作;

​ (程序)步计数(step count):分析全部程序。

要点:基本操作或程序步执行的时间必须时常数。

3.例题

s/e:代表该语句执行后步数(count)的变化(增量);

Frequency:代表该语句执行的次数;

Total steps:代表该语句在整个程序执行过程中引发的总步数。

Statement s/e Frequency Total steps
T Sum(T a[],int n) 0 0 0
{ 0 0 0
T tsum=0; 1 1 1
for(int i=0;i<n;i++) 1 n+1 n+1
tsum+=a[i]; 1 n n
return tsum; 1 1 1
} 0 0 0
Total 2n+3

渐进分析(O,Ω,Θ)

1.定义

计算机科学使用最多的符号-讨论算法时使用的共同语言

O:上界;Ω:下界;Θ:同阶。

2.随n的增加T(n)的增长率

1

3.渐进分析时用到的一些等式

2

E8:i form 1 to n. ∑1/i -> Θ(logn)

4.例题

Statement s/e Frequency Total steps
T Sum(T a[], int n) 0 0 Θ(0)
{ 0 0 Θ(0)
T tsum=0; 1 1 Θ(1)
for(int i=0;i<n;i++) 1 n+1 Θ(n)
tsum+=a[i]; 1 n Θ(n)
return tsum; 1 1 Θ(1)
} 0 0 Θ(0)

∴ t(n)=Θ(max{})=Θ(n)