4551
правка
Аппроксимация метрических пространств древесными метриками: различия между версиями
Перейти к навигации
Перейти к поиску
м
Аппроксимация метрических пространств древесными метриками (посмотреть исходный код)
Версия от 11:48, 1 ноября 2016
, 1 ноября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 37: | Строка 37: | ||
Теорема 1. Пусть имеется n-точечная метрика (V, d). Существует рандомизированный алгоритм, который за время <math>O(n^2) \;</math> осуществляет выборку древесной метрики из распределения <math>\mathcal{D} \;</math> над древесными метриками, которая O(log n)-вероятностно аппроксимирует (V, d). Это дерево также является 2-HST-деревом. | '''Теорема 1. Пусть имеется n-точечная метрика (V, d). Существует рандомизированный алгоритм, который за время <math>O(n^2) \;</math> осуществляет выборку древесной метрики из распределения <math>\mathcal{D} \;</math> над древесными метриками, которая O(log n)-вероятностно аппроксимирует (V, d). Это дерево также является 2-HST-деревом.''' | ||
| Строка 52: | Строка 52: | ||
Теорема 2. Пусть имеется n-точечная метрика (V, d). Существует детерминированный алгоритм с полиномиальным временем выполнения, который находит распределение <math>\mathcal{D} \;</math> над O(n log n) древесных метрик, которая O(log n)-вероятностно аппроксимирует (V, d). | '''Теорема 2. Пусть имеется n-точечная метрика (V, d). Существует детерминированный алгоритм с полиномиальным временем выполнения, который находит распределение <math>\mathcal{D} \;</math> над O(n log n) древесных метрик, которая O(log n)-вероятностно аппроксимирует (V, d).''' | ||