Супердерево максимального соответствия: различия между версиями

Супердерево максимального соответствия (посмотреть исходный код)

116 байт добавлено , 2 ноября 2015

4551

правка

Версия от 00:22, 2 ноября 2015 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) ← Предыдущая правка		Версия от 00:26, 2 ноября 2015 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Основные результаты) Следующая правка →
Строка 47:		Строка 47:


	Теорема 6 ([8]). Задача MASP может быть приближенно решена с множителем ~~lognn~~ за время O(n2) ■ min {O(k ■ (log log n)2); O (k + log n • log log n)}. MASP, ограниченная корневыми триплетами, может быть приближенно решена с множителем ~~lognn~~ за время O(k + n2 log n).		'''Теорема 6 ([8])'''. Задача MASP может быть приближенно решена с множителем <math>\frac{n}{log \; n}</math> за время <math>O(n^2) \cdot min \{ O(k \cdot (log \; log \; n)^2), O(k + log \; n \cdot log \; log \; n) \} </math>. MASP, ограниченная корневыми триплетами, может быть приближенно решена с множителем <math>\frac{n}{log \; n}</math> за время <math>O(k + n^2 log^2 \; n)</math>.