4551
правка
Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями
Перейти к навигации
Перейти к поиску
м
Рандомизированный алгоритм нахождения минимального остовного дерева (посмотреть исходный код)
Версия от 23:46, 28 апреля 2016
, 28 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 45: | Строка 45: | ||
Анализ ожидаемого времени исполнения и экспоненциально высокая граница вероятности для времени исполнения простейшим образом выводятся при помощи леммы выборки MST (леммы 1). | Анализ ожидаемого времени исполнения и экспоненциально высокая граница вероятности для времени исполнения простейшим образом выводятся при помощи леммы выборки MST (леммы 1). | ||
В работе [9] доказываются следующие положения. | В работе [9] доказываются следующие положения. | ||