算法的空间效率

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);
}