Сортировка Хана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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>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> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.

Версия 20:40, 10 июня 2012

Сортировка Хана (Yijie Han) — сложный алгоритм сортировки целых чисел со сложностью [math]O(nlog(logn))[/math], где [math]n[/math] — количество элементов для сортировки.

Алгоритм

Алгоритм построен на основе экспоненциального поискового дерева (далее - Э.П.дерево) Андерсона (Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в Э.П.дерево.

Andersson's exponential search tree

Э.П.дерево с [math]n[/math] листьями состоит из корня [math]r[/math] и [math]n^e[/math] (0<[math]e[/math]<1) Э.П.поддеревьев, в каждом из которых [math]n^{1-e}[/math] листьев; каждое Э.П.поддерево является сыном корня [math]r[/math]. В этом дереве [math]O(log(logn))[/math] уровней. При нарушении баланса дерева, необходимо балансирование, которое требует [math]O(nlog(logn))[/math] времени при [math]n[/math] вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.