algorithm - 算法的空间效率

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)）。