Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями

• После создания в 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>, точные границы еще не определены.