程序性能

空间复杂性

程序所需要的空间主要由以下部分构成：

指令空间（instruction space）指令空间是指用来存储经过编译之后的程序指令所需的空间。

数据空间（data space）数据空间是指用来存储所有常量和所有变量值所需的空间。数据空间由两个部分构成：

存储常量和简单变量所需要的空间：如4是常量，a、b、c是简单变量。
1
2
3
4
int example(int a, int b, int c)
{
return a + b + c + 4;
}

存储复合变量所需要的空间。这一类包括数据结构所需的空间及动态分配的空间。如数组a。

int example(int a[], int n)
{
    int sum = 0;
    for(int i = 0; i < n; i++)
        sum += a[i];
    return sum;
}

环境栈空间（environment stack space）环境栈用来保存函数调用返回时恢复运行所需要的信息。例如，如果函数fun1调用了函数fun2，那么至少必须保存fun2结束时fun1将要继续执行的指令的地址。

指令空间

程序所需要的指令空间的数量取决于如下因素：

把程序编译成机器代码的编译器

编译时实际采用的编译器选项

目标计算机

数据空间

对于简单变量和常量来说，所需要的空间取决于所使用的使用的计算机和编译器以及变量与常量的数目。

环境栈

当一个函数被调用时，下面的数据将被保存在环境栈中：

返回地址

函数被调用时所有局部变量的值以及传值形式参数的值

所有引用参数及常量引用参数的定义

template <class T>
T Rsum(T a[], int n)
{
    if(n > 0)
        return Rsum(a, n - 1) + a[n - 1];
    return 0;
}

当Rsum被调用时，不管该调用是来自外部或第4行，a的当前赋值、n的值以及程序运行结束时的返回地址都被存储在环境栈之中。

值得注意的是，有些编译器在保留局部变量的值、传值形式参数的值以及引用参数和常量引用参数的定义时，对于递归函数和非递归函数一视同仁，而有些编译器则仅为递归函数保存上述内容。所以实际使用的编译器将影响环境栈所需要的空间。

可以把一个程序所需要的空间分成两部分：

固定部分：它独立于实例的特征。一般包含指令空间、简单变量和常量及定长复合变量所占空间等等。

可变部分：包含复合变量所需空间（这些变量的大小依赖于所解决的具体问题）、动态分配的空间（一般都依赖于实例特征）、递归栈所需空间（也依赖于实例特征）。

任意程序P所需要的空间S(P)可以表示为：

$S(P) = c + S_p$

其中c是一个常量，表示固定部分所需要的空间， Sp表示可变部分所需要的空间。

template <class T>
int seq_search(T a[], const T& x, int n)
{
    int i;
    for(i = 0; i < n && a[i] != x; i++);
    if(i == n) return -1;
    return i;
}

我们希望采用实例特征n来估算该函数的空间复杂性。假定T为int类型，则数组a中的每个元素需要2个字节，实参x需要2个字节，传值形式参数n需要2个字节，局部变量i需要2个字节，每个整型常量0和-1也分别需要2个字节。因此，所需要的总的数据空间为12字节。因为该空间独立于n，所以S(n) = 0。

template <class T>
T Sum(T a[], int n)
{
    T tsum = 0;
    for(int i = 0; i < n; i++)
        tsum += a[i];
    return tsum;
}

在该函数中，a、n、i和tsum需要分配空间，所以程序所需要的空间与n无关，因此有S(n) = 0。

int factorial(int n)
{
    if(n <= 1) return 1;
    else return n * factorial(n - 1);
}

该程序的空间复杂性是n的函数而不是输入（只有一个）或输出（也只有一个）个数的函数。递归深度为max{n, 1}。每次调用函数Factorial 时，递归栈需要保留返回地址（ 2个字节）和n的值（2个字节）。此外没有其他依赖于n的空间，所以S(n) = 4*max{n, 1}。

// 使用递归函数生成排列
void Perm(T list[], int k, int m)
{
    int i;
    if(k == m)
    {
        for(i = 1; i <= m; i++)
            cout << list[i] << " ";
        cout << endl;
    }
    else
    {
        for(i = k; i <= m; i++)
        {
            swap(list[k], list[i]);
            Perm(list, k + 1, m);
            swap(list[k], list[i]);
        }
    }
}

对于初始调用Perm(list, 0, n-1)，递归的深度为n。由于每次调用需要10个字节的递归栈空间（每个返回地址、list、k、m以及i各需要2个字节），所以需要10n字节的递归栈空间，S(n) = 10n。

时间复杂性

有两个更可行的方法可以用来估算运行时间：

确定关键操作所需要的执行时间；
确定程序执行的总步数。

操作计数

// 计算名次
void Rank(T a[], int n, int r[])
{
    for(int i = 0; i < n; i++)
        r[i] = 0;
    for(int i = 1; i < n; i++)
        for(int j = 0; j < i; j++)
            if(a[j] >= a[i]) r[j]++;
            else r[i]++; 
}

注意在估算时间复杂性时没有考虑for循环的额外开销、初始化数组r的开销以及每次比较a中两个元素时对r进行增值的开销。

// 原地重排
void rearrange()
{
    // rank: r[], array: a[]
    // int r[5] = {2, 0, 4, 1, 3};
    // int a[5] = {4, 3, 9, 3, 7};
    for(int i = 0; i < 5; i++)
    {
        while(r[i] != i)
        {
            int t = r[i];
            swap(a[t], a[i]);
            swap(r[t], r[i]);
        }
    }
}

执行步数

程序步（program step）可以定义为一个语法或语义意义上的程序片段，该片段的执行时间独立于实例特征。

数据结构与算法学习笔记1