4430
правок
Супердерево максимального соответствия: различия между версиями
Перейти к навигации
Перейти к поиску
м
Супердерево максимального соответствия (посмотреть исходный код)
Версия от 00:14, 2 ноября 2015
, 2 ноября 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
Теорема 2. ([8]) Если k = 2 (имеются два дерева), супердерево максимального соответствия может быть найдено за время O( | Теорема 2. ([8]) Если k = 2 (имеются два дерева), супердерево максимального соответствия может быть найдено за время <math>O(T_{MAST} + n) \;</math>, где <math>T_{MAST} \;</math> – время, необходимое для вычисления поддерева максимального соответствия двух деревьев с O(n) листьями. Заметим, что <math>T_{MAST} = O( \sqrt{Dn} \; log(2n/D)) \;</math> (см. [9]). | ||
В [11] было приведено обобщение теоремы 2 и предложено следующее решение. | В [11] было приведено обобщение теоремы 2 и предложено следующее решение. | ||