Руководство для начинающих по оценке алгоритма использования памяти компьютера

Что такое пространственная сложность?

Пространственная сложность — это способ оценить, насколько эффективно алгоритм использует компьютерную память. Хотя мы говорим о памяти — подумайте о байтах — сложность пространства выражается с помощью нотации big-O, т. е. сколько дополнительной памяти требуется в зависимости от размера входных данных.

Вы выделили курсивом слово "дополнительная" в слове "дополнительная память". Почему?

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

Подождите, прежде чем мы продолжим…

Что такое вспомогательное пространство?

Вспомогательное пространство — это дополнительное пространство, необходимое для выполнения алгоритма.

Примеры. Какова пространственная сложность следующего алгоритма?

ПРИМЕР 1

В приведенном выше примере нам не нужно выделять или копировать какие-либо новые данные; мы модифицируем данный массив. Никаких дополнительных данных не требуется, даже если входной массив большой. Таким образом, пространственная сложность равна O(1), поскольку мы используем постоянный объем пространства независимо от размера входных данных.

ПРИМЕР 2

Первое, на что следует обратить внимание, это то, что этот алгоритм использует рекурсию. Почему это важно? Ну, каждый раз, когда мы делаем новую функцию, вызываем новый кадр стека в память стека. Это означает, что если n равно 100, то стек рекурсии будет равен 100. Таким образом, пространственная сложность равна 0(n).

Можем ли мы написать этот рефакторинг этого алгоритма, чтобы улучшить сложность пространства?

С петлей:

Этот алгоритм имеет пространственную сложность O(1), поскольку использует постоянное число переменных независимо от размера входных данных.

Квадратично:

При использовании этого квадратичного алгоритма пространственная сложность составляет O(1), поскольку дополнительное пространство не требуется.

Надеемся, что это краткое введение в пространственную сложность поможет начать ваше путешествие к демистификации пространства, временной сложности и нотации с большой буквой О.