4501
правка
Супердерево максимального соответствия: различия между версиями
Материал из WEGA
Супердерево максимального соответствия (посмотреть исходный код)
Версия от 00:29, 2 ноября 2015
, 2 ноября 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
Также существуют алгоритмы вычисления MASP с фиксированными параметрами и полиномиальным временем решения. Случай с множеством k бинарных деревьев T с n различных меток листьев рассматривался множеством исследователей. Дженссон и коллеги [ ] первыми предложили алгоритм вычисления MAST на T с временем исполнения O(k( | Также существуют алгоритмы вычисления MASP с фиксированными параметрами и полиномиальным временем решения. Случай с множеством k бинарных деревьев T с n различных меток листьев рассматривался множеством исследователей. Дженссон и коллеги [8] первыми предложили алгоритм вычисления MAST на T с временем исполнения <math>O(k(2n^2)^{3k^2}) \;</math>. Недавно Гийемо и Берри [5] улучшили это время до <math>O((8n)^k) \;</math>; Хоанг и Сунг [7] снизили его до <math>O((6n)^k) \;</math>, что показано в теореме 7. | ||
Теорема 7 ([7]). Пусть дано множество k бинарных деревьев T с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время O((6n)k). | '''Теорема 7 ([7])'''. Пусть дано множество k бинарных деревьев T с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время <math>O((6n)^k) \;</math>. | ||
Для случая, когда множество k бинарных деревьев T имеют степень D и n различных меток листьев, Хоанг и Сунг [7] предложили следующее решение для нахождения MASP с фиксированными параметрами и полиномиальным временем исполнения. | Для случая, когда множество k бинарных деревьев T имеют степень D и n различных меток листьев, Хоанг и Сунг [7] предложили следующее решение для нахождения MASP с фиксированными параметрами и полиномиальным временем исполнения. | ||
Теорема 8 ([ ]). Пусть дано множество k бинарных деревьев T степени D с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время O((kD)kD+3(2n)k). | '''Теорема 8 ([7])'''. Пусть дано множество k бинарных деревьев T степени D с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время <math>O((kD)^{kD+3} (2n)^k) \;</math>. | ||
== Применение == | == Применение == | ||
