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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Сортировка Хана (Yijie Han)''' {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex>...»)
 
Строка 2: Строка 2:
  
 
== Алгоритм ==
 
== Алгоритм ==
Алгоритм построен на основе экспоненциального поискового дерева (далее - Э.П.дерево) Андерсона (<tex>Andersson's exponential search tree</tex>). Сортировка происходит за счет вставки целых чисел в Э.П.дерево.
+
Алгоритм построен на основе экспоненциального поискового дерева (далее - Э.П.дерево) Андерсона (Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в Э.П.дерево.
  
 
== Andersson's exponential search tree ==
 
== Andersson's exponential search tree ==
 
Э.П.дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> Э.П.поддеревьев (<tex>0<e<1</tex>), в каждом из которых <tex>n^(1-e)</tex> листьев; каждое Э.П.поддерево является сыном корня <tex>r</tex>.
 
Э.П.дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> Э.П.поддеревьев (<tex>0<e<1</tex>), в каждом из которых <tex>n^(1-e)</tex> листьев; каждое Э.П.поддерево является сыном корня <tex>r</tex>.

Версия 20:28, 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] Э.П.поддеревьев ([math]0\lt e\lt 1[/math]), в каждом из которых [math]n^(1-e)[/math] листьев; каждое Э.П.поддерево является сыном корня [math]r[/math].