Сортировка Хана — различия между версиями
| Строка 5: | Строка 5: | ||
== Andersson's exponential search tree == | == Andersson's exponential search tree == | ||
| − | Э.П.дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> (0<<tex>e</tex><1) Э.П.поддеревьев, в каждом из которых <tex>n^{1-e}</tex> листьев; каждое Э.П.поддерево является сыном корня <tex>r</tex>. В этом дереве <tex>O(log(logn))</tex> уровней. При нарушении баланса дерева, необходимо балансирование, которое требует <tex>O(nlog(logn))</tex> времени при <tex>n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон. | + | Э.П.дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> (0<<tex>e</tex><1) Э.П.поддеревьев, в каждом из которых <tex>n^{1 - e}</tex> листьев; каждое Э.П.поддерево является сыном корня <tex>r</tex>. В этом дереве <tex>O(log(logn))</tex> уровней. При нарушении баланса дерева, необходимо балансирование, которое требует <tex>O(nlog(logn))</tex> времени при <tex>n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон. |
| + | |||
| + | ==Определения== | ||
| + | {{Консервативный алгоритм | ||
| + | |id=def1. | ||
| + | |Алгоритм сортирующий <tex>n</tex> целых чисел из множества {0, 1, ..., <tex>m</tex> - 1} называется консервативным, если число бит, используемое для хранения данных целых чисел является <tex>O(log(m + n))</tex>. Если используется большее число бит, то алгоритм не консервативный. | ||
| + | }} | ||
Версия 20:59, 10 июня 2012
Сортировка Хана (Yijie Han) — сложный алгоритм сортировки целых чисел со сложностью , где — количество элементов для сортировки.
Алгоритм
Алгоритм построен на основе экспоненциального поискового дерева (далее - Э.П.дерево) Андерсона (Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в Э.П.дерево.
Andersson's exponential search tree
Э.П.дерево с листьями состоит из корня и (0<<1) Э.П.поддеревьев, в каждом из которых листьев; каждое Э.П.поддерево является сыном корня . В этом дереве уровней. При нарушении баланса дерева, необходимо балансирование, которое требует времени при вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.
