Действительно ли побеждает ли разделение и завоевание против увеличения объема памяти?

Question

Я только что закончил кодирование некоторых классических алгоритмов разделяй и властвуй, и я придумал следующий вопрос: (больше для любопытства)

Следует признать, что во многих случаях, разделяй и властвуй алгоритм быстрее, чем традиционный алгоритм; например, в Fast Fourier Transform, это улучшает сложность от N^2 до Nlog2N. Однако через кодирование я узнал, что из-за «деления» у нас больше подзадач, а это значит, что мы должны создавать больше контейнеров и дополнительно выделять больше памяти на подзадачу. Подумайте об этом, в сортировке merge мы должны создать левый и правый массивы в каждой рекурсии, а в Fast Fourier Transform нам нужно создать нечетный и четный массив в каждой рекурсии. Это означает, что мы должны выделять больше памяти во время алгоритма.

Итак, на мой вопрос, на самом деле, например, в C++, действительно ли такие алгоритмы, как divide-and-conquer, действительно выигрывают, когда нам также нужно увеличить сложность в распределении памяти? (Или выделение памяти не будет занимать время выполнения, а стоимость равна нулю?)

Спасибо, что помогли мне!

Answer 1

Практически все, что касается оптимизации, является компромиссом между одним ресурсом и другим - в традиционной технике это обычно «стоимость и материал».

При вычислении часто используется время и использование памяти, что является компромиссом.

Я не думаю, что есть один простой ответ на ваш реальный вопрос - он действительно зависит от алгоритма - и в реальной жизни это может привести к компромиссным решениям, когда проблема разделена на более мелкие части, но не ВСЕ вплоть до минимального размера, только «пока не будет более эффективно делить его».

Распределение памяти не является нулевой стоимостью, если речь идет о new и delete. Память стека почти нулевая стоимость, как только фактическая память стека заполнена физической памятью ОС - это не более чем одна дополнительная инструкция на большинстве архитектур, чтобы сделать некоторое пространство в стеке, а иногда и одну дополнительную инструкцию на выходе, чтобы вернуть память ,

Реальный ответ - почти всегда, когда дело доходит до производительности, для сравнения различных решений.

Answer 2

Полезно понять, что получение «одного уровня лучше» в терминах большого О (например, переход от n^2 к n или от n к log n) обычно имеет большое значение. Рассмотрим ваш пример Фурье.

В O(n^2) с n=100 вы смотрите на 10000, и с n=1000 вы получите целый миллион, 1000000. С другой стороны, с O(n*log(n)) вы получаете 664 за n=100 и 9965 по адресу n=1000. Более медленный рост должен быть очевиден.

Разумеется, распределение памяти требует ресурсов, как и другой код, необходимый для разделения и управления, например, объединение частей. Но вся идея заключается в том, что накладные расходы из дополнительных распределений и т. Д. Намного меньше, чем дополнительное время, которое потребуется для небольшого алгоритма.

Время для дополнительных выделений обычно не является проблемой, но само использование памяти может быть. Это один из фундаментальных компромиссов в программировании. Вы должны выбирать между скоростью и использованием памяти. Иногда вы можете позволить дополнительной памяти получать более быстрые результаты, иногда вы должны сохранять всю память. Это одна из причин, почему для многих проблем нет «окончательного алгоритма».Скажем, mergesort велик, работает в O(n * log(n)) даже в худшем случае, но ему нужна дополнительная память. Если вы не используете версию на месте, которая затем работает медленнее. Или, может быть, вы знаете, что ваши данные, скорее всего, уже почти отсортированы, а затем что-то вроде smoothsort вам подходит.