Сравнения «сравнение» сортирует

я прочитал следующее заявление, сравнивая кучи сортировки и сортировки слияния:Сравнения «сравнение» сортирует

Merge сортировка может быть адаптирована для работы со связанными списками с O (1) дополнительное местом. Сортировка кучи может быть адаптирована для работы с двусвязными списками с дополнительными дополнительными расходами O (1).

Поблагодарите за помощь в объяснении этого (я не образован информатики), хотя я понимаю, как эти виды работают на элементарном уровне.

источник

2013-07-26 IUnknown

Вы должны быть более конкретными, о которых аспекте вы не понимаете, - или ждать кого-то, кто имеет много терпения, чтобы ввести объяснение алгоритмов всех. –

Я пытаюсь понять актуальность «лишнего» слова здесь. Мне действительно не нужно понимать алгоритмы. Какая причина для этого лишнего места для связанного списка. – IUnknown

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

Это Big O Notation. Он используется для описания сложности (времени/памяти) алгоритма (проверьте ссылку для получения более подробной информации). Здесь имеется в виду, что алгоритмы, о которых вы читаете, могут быть расширены для работы в указанных случаях, и изменение, которое необходимо сделать, приведет к необходимости в постоянном увеличении пространства. Это дополнительное пространство не будет зависеть от размера структуры. Он будет постоянным - например, одной переменной больше.

РЕДАКТИРОВАТЬ:

Некоторые из наиболее часто используемых обозначений:

O (1) - константа - время или память используется не зависит от размера структуры алгоритм работает на
о (п) - линейно - зависит от размера структуры - чем больше структура - тем больше времени/памяти требуется
O (LogN) - logarithmic .. .

Для получения более подробной информации проверить here

источник

2013-07-26 08:32:44 stan0

Сравнения «сравнение» сортирует

ответ

Смежные вопросы