Космическая сложность против вспомогательной космической сложности

Question

Я как будто путаюсь между этими двумя терминами, например: вспомогательное пространство сортировки слиянием, сортировки по типу heaps и сортировки вставкой равно O(1), тогда как сложность по пространству сортировки слиянием, сортировки вставки и сортировки по типу heapsort составляет O(n).

Итак, если кто-то спросит меня, что такое Пространственная сложность сортировки слиянием, сортировки по типу heaps или вставки, то что мне сказать им O(1) или O(n)?

Кроме того, обратите внимание, что в случае сортировки выбора, я прочитал, что Сложность пространства равна O(1), что является вспомогательным пространством.

Итак, возможен ли алгоритм, который использует "вычисления на месте", и для этих алгоритмов мы упоминаем вспомогательное пространство?

Кроме того, я знаю -

Сложность пространства = Вспомогательное пространство + пространство, занятое также по вводу.

Пожалуйста, помогите, спасибо!

Answer 1

Глядя на O(n), вы должны понимать, что это значит. Это "В МИРОВОМ СЛУЧАЕ ЭТОГО БУДЕТ N". Я использую http://bigocheatsheet.com/ в качестве ориентира.

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

Что касается вашего первого вопроса, он будет в большинстве случаев занимать N места, но общее количество, хранимое в памяти для ваших операций, будет равно O(1).

Когда вы имеете дело с SORTS, как вы перечислили выше, они в основном только O (1), потому что им просто нужно пространство tmp для хранения вещей во время перестановок. Сами структуры данных требуют БОЛЬШЕ места, потому что они имеют определенный размер в памяти для любых манипуляций.

Я использую связанный веб-сайт много..