Изменения

Перейти к: навигация, поиск

Сортировка Хана

22 байта добавлено, 14:43, 12 июня 2012
Нет описания правки
Заметим, что если длина контейнера <tex>\log m \log\log n</tex> и только <tex>\log m</tex> бит используется для упаковки <tex>g <= \log n</tex> чисел в один контейнер, тогда выбор в лемме три может быть сделан за время и место <tex>O(n/g)</tex>, потому, что упаковка в доказатльстве леммы три теперь может быть сделана за время <tex>O(n/g)</tex>.
==Сортировка n целых чисел в <tex>sqrt(n) </tex> наборов==
Постановка задачи и решение некоторых проблем:
Время работы алгоритма <tex>O(n \log\log n/ \log k)</tex>, что доказывает лемму 2.
==Собственно сортировка с использованием <tex>O(n \log\log n) </tex> времени и памяти==
Для сортировки <tex>n</tex> целых чисел в диапазоне от {<tex>0, 1, ..., m - 1</tex>} мы предполагаем, что используем контейнер длины <tex>O(\log (m + n))</tex> в нашем консервативном алгоритме. Мы всегда считаем что все числа упакованы в контейнеры одинаковой длины.
81
правка

Навигация