170
правок
Изменения
м
→Вторая нижняя оценка Уилберра (Wilber)
Можно показать, что <tex>OPT(x) >= M + 1/2* MP</tex>, где <tex>M</tex> -- число запросов, <tex>MP</tex> -- максимальное число независимых прямоугольников.
==Вторая нижняя оценка Уилберра Уилбера (Wilber) ==
Для каждого запроса <tex>x</tex> вычислим число УилберраУилбера.
Для ключа <tex>x_[j]</tex> рассмотрим ключи <tex>x_{i} : x_{I} = x_{j}, i = 0..j - 1</tex>
Напишем <tex>r</tex>, если изменяется правая граница <tex>b_{i}</tex> и <tex>l</tex> - если левая.
Числом Уилберра Уилбера <tex>ch(i)</tex> называется количество смен <tex>r</tex> на <tex>l</tex> и обратно.
Получаем следующую оценку
