Пространственная эффективность алгоритмов

Question

Кажется, что ни один из учебников алгоритмов не упоминает об эффективности использования пространства, поэтому я не совсем понимаю, когда сталкиваюсь с вопросами, требующими алгоритма, который требует только постоянной памяти.

Что было бы примером нескольких примеров алгоритмов, которые используют постоянную память и алгоритмы, которые не используют постоянную память?

Answer 1

Очень простой пример: подсчет количества символов в строке. Это может быть итеративным:

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 2

Если алгоритм:

а) рекурсивен несколько уровней глубокого который зависит от N, или

б) распределяет объем памяти, которая зависит от 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 3

Возьмите алгоритмы сортировки для массива, например. Вы можете использовать новый массив той же длины, что и исходный массив, в который вы помещали отсортированные элементы (Θ (n)). Или вы сортируете массив in-place и просто используете одну дополнительную временную переменную для замены двух элементов (Θ (1)).