算法的空间效率

Question

似乎没有一本算法教科书提到那么多关于空间效率的问题，所以当我遇到要求仅需要恒定内存的算法的问题时，我不太明白。

使用常量内存的算法和不使用常量内存的算法的一些示例是什么？

Answer 1

如果一个算法：

a) 递归多个取决于 N 的深度，或

b) 分配一定数量的内存，取决于 N，

那么它就不是常量内存。否则可能是：如果算法使用的内存量有一个恒定的上限，无论输入的大小/值是什么，形式上它就是常量内存。输入占用的内存不包括在内，因此有时为了清楚起见，您会谈论常量“额外”内存。

因此，这是一个常量内存算法，用于在 C 中查找整数数组的最大值：

int max(int *start, int *end) {
    int result = INT_MIN;
    while (start != end) {
        if (*start > result) result = *start;
        ++start;
    }
    return result;
}

这是一个非常量内存算法，因为它使用与输入数组中的元素数量成比例的堆栈空间。然而，如果编译器能够以某种方式将其优化为非递归等效项（C 编译器通常不会费心，除非有时使用尾部调用优化，而这在此处不起作用），则它可能会成为常量内存):

int max(int *start, int *end) {
    if (start == end) return INT_MIN;
    int tail = max(start+1, end);
    return (*start > tail) ? *start : tail;
}

这是一个常量空间排序算法（这次是在 C++ 中），时间复杂度为 O(N!) 左右（也许是 O(N*N!)）：

void sort(int *start, int *end) {
    while (std::next_permutation(start,end));
}

这是一个 O(N) 空间排序算法，它是 O(N^2) 时间：

void sort(int *start, int *end) {
    std::vector<int> work;
    for (int *current = start; current != end; ++current) {
        work.insert(
            std::upper_bound(work.begin(), work.end(), *current),
            *current
        );
    }
    std::copy(work.begin(), work.end(), start);
}

Answer 2

非常简单的例子：计算字符串中的字符数。它可以是迭代的：

int length( const char* str )
{
    int count = 0;
    while( *str != 0 ) {
       str++;
       count++
    }
    return count;
}

或递归的：

int length( const char* str )
{
    if( *str == 0 ) {
        return 0;
    }
    return 1 + length( str + 1 );
}

第一个变体仅使用几个局部变量，无论字符串长度如何 - 它的空间复杂度为O(1)。第二个如果在没有递归消除的情况下执行，则需要一个单独的堆栈帧来存储与每个深度级别相对应的返回地址和局部变量 - 其空间复杂度为 O(n) 其中 n是字符串长度。

Answer 3

以数组的排序算法为例。您可以使用与原始数组长度相同的新数组，将排序后的元素放入 (θ(n)) 中。或者您对数组就地进行排序，然后使用一个用于交换两个元素的附加临时变量 (θ(1))。