4551
правка
Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями
Перейти к навигации
Перейти к поиску
Рандомизированный алгоритм нахождения минимального остовного дерева (посмотреть исходный код)
Версия от 23:41, 16 апреля 2016
, 16 апреля 2016→Дополнительные соображения
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 56: | Строка 56: | ||
== Дополнительные соображения == | == Дополнительные соображения == | ||
• После создания в 1995 году алгоритма KKT были разработаны два новых детерминированных алгоритма для нахождения минимального остовного дерева, предложенные Шазелем [4] и Петти-Рамачандраном [ ]. Первый [4] исполняется за время O(n + | • После создания в 1995 году алгоритма KKT были разработаны два новых детерминированных алгоритма для нахождения минимального остовного дерева, предложенные Шазелем [4] и Петти-Рамачандраном [14]. Первый [4] исполняется за время <math>O(n + m \alpha(m, n)) \;</math>, где <math>\alpha \;</math> – обратная функция Аккермана, которая растет даже медленнее, чем функция <math>\beta \;</math>, ранее упоминавшаяся в качестве наилучшего результата, известного до публикации алгоритма KKT [4]. Второй алгоритм [14] доказуемо исполняется за время, не более чем на константный множитель отличающееся от сложности дерева решений задачи минимального остовного дерева и, следовательно, являющееся оптимальным; его временные границы составляют <math>O(n + m \alphaa(m, n)) \;</math> и <math>\Omega (n + m) \;</math>, точные границы еще не определены. | ||
• Хотя ожидаемое время исполнения алгоритма KKT является линейным (с экспоненциально высокой вероятностью), это не лучший показатель среди рандомизированных MST-алгоритмов. Рандомизированный MST-алгоритм, исполняющийся за ожидаемое линейное время и использующий только <math>O(log^* \; n)</math> случайных бит, приведен в работах [16, 17]. Для сравнения, алгоритм KKT использует линейное количество случайных бит. | |||
== Применение == | == Применение == | ||