Пространственная сложность алгоритмов

В прошлом уроке мы говорили про вычислительную сложность алгоритмов, а в этом речь пойдет о пространственной. Иногда этот критерий даже важнее скорости вычислений. Ведь если алгоритму для работы не хватит памяти, он завершится быстрее, чем доработает до конца.

Рассмотрим два алгоритма сортировки и сравним объём дополнительной памяти, выделяемой при их работе.

В алгоритме сортировки выбором из предыдущего урока мы на каждом шаге i выбирали наименьший элемент в массиве и меняли его местами с элементом на позиции i. Сортировка в этом случае происходит без использования дополнительной памяти, за исключением одной временной переменной.

Другой алгоритм, решающий эту задачу: проходим по всем элементам массива и на каждом шаге i помещаем элемент на позиции i в определённое место в новом массиве. Получаем отсортированный массив чисел. Для решения задачи понадобится дополнительный объём памяти, равный объёму исходного массива.

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

Какой объём дополнительной памяти используется алгоритмом, реализованном в этом фрагменте кода? Под дополнительной памятью понимается любая память, используемая программой, помимо выделенной под массивы first_list и second_list

Скопировать кодPYTHON
first_list = [1, 3, 5, 2]
second_list = [5, 4, 1, 7]

for i in range(len(first_list)):
        if first_list[i] < second_list[i]:
                tmp = second_list[i]
                second_list[i] = first_list[i]
                first_list[i] = tmp

O(1)

O(n)

Нет. Всего в алгоритме n шагов, где n — длина первого массива. На каждом шаге происходит сравнение и, возможно, обмен значениями, то есть три операции: сохранения значения second_list[i] во временную переменную tmp, изменение значения second_list[i] и изменение значения first_list[i]. При этом дополнительная память нужна только для временной переменной tmp. Но на каждом шаге мы не создаем новую переменную, а перезаписываем значение старой. Значит, нам потребуется дополнительная память, не зависящая от размера входных данных. А это O(1).

O(n²)

O(2n)

Какой объём дополнительной памяти нужен для работы этого алгоритма? Два исходных массива имеют одинаковый размер.

В разных языках программирования выделение памяти под массив происходит по-разному. В Python, например, память выделяется с запасом. В данной задаче для упрощения будем считать, что выделяется память, соответствующая размеру массива.

Скопировать кодPYTHON
fruits_array = ["apple", "banana", "orange"]
vegetables_array = ["cucumber", "carrot", "tomato"]
vegan_array = []

for i in range(len(fruits_array)):
    vegan_array.append(fruits_array[i])
    
for i in range(len(vegetables_array)):
    vegan_array.append(vegetables_array[i])

Какой объём дополнительной памяти нужен для работы этого алгоритма, если предположить, что строка является неизменяемым объектом, как в языке Python, и каждый раз при добавлении нового символа создается новый объект?

Скопировать кодPYTHON
first_string = "Pay attention!"
second_string = "I am immutable"

for i in range(len(second_string)):
    first_string += second_string[i]
print(first_string)

O(1)

O(n)

Если строка — неизменяемый объект, то на каждом шаге алгоритма будет создаваться копия first_string. Получаем O(n²).

O(n²)

O(2n)

Есть алгоритм: пройти по каждому элементу входного массива, разделить полученное значение на 2, сравнить результат с переменной a. Если результат больше а, добавить элемент в новый массив. Какая объем дополнительной памяти будет при этом использован?

O(n²)

O(n)

O(1)