4551
правка
Полностью динамические минимальные остовные деревья: различия между версиями
Материал из WEGA
Полностью динамические минимальные остовные деревья (посмотреть исходный код)
Версия от 12:58, 19 июля 2014
, 19 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 61: | Строка 61: | ||
Теорема 4. Любому алгоритму на RAM-машине с единичной стоимостью, способной выполнять операции сложения, вычитания, умножения и сравнения с нулем, но не поддерживающей деление и поразрядные булевы операции, для динамической поддержки минимального остовного дерева требуется амортизированное время <math>\Omega (log \; n)</math> на операцию. | '''Теорема 4. Любому алгоритму на RAM-машине с единичной стоимостью, способной выполнять операции сложения, вычитания, умножения и сравнения с нулем, но не поддерживающей деление и поразрядные булевы операции, для динамической поддержки минимального остовного дерева требуется амортизированное время <math>\Omega (log \; n)</math> на операцию.''' | ||
== Применение == | == Применение == | ||
