Изменения
→Время работы
==Время работы==
{{Лемма
|id=lemma2
|about=
#2
|statement=
<tex>\forall v \in V \ |S_v'| \le a_v - b_v + |Int(D_v, S_v')|</tex>.
|proof=
Утверждение напрямую вытекает из [[#lemma1|леммы]] (далее лемма №1) и очевидного факта, что для любого множества <tex>S \subset S_0</tex>, количество концов отрезков, лежащих в полосе <tex>\langle a_v, b_v \rangle</tex>, меньше чем <tex>b_v - a_v</tex>.
}}
{{Теорема
|about=
#1
|statement=
<tex>\sum_{v \in V} |S_v'| \le 2N \lceil logN + 1 \rceil + K</tex>
|proof=
Утверждение напрямую вытекает из [[#lemma2|леммы №2]] и следующего отношения <tex>\sum_v (b_v - a_v) \le 2N \lceil logN + 1 \rceil</tex>.
}}
{{Теорема
|about=
#2
|statement=
<tex>\sum_{v \in RT} |S_v| \le N \lceil 4logN + 5 \rceil + 2K</tex>
|proof=
Для всех узлов, кроме корня <tex>r</tex> имеет место выражение <tex>|S_v| \le |S_{ft(v)}'|</tex>, следовательно <tex>\sum_{v \in RT} |S_v| \le |S_r| + \sum_{v \in RT \setminus r} |S_{ft(v)}| \le N + 2 \sum_{v \in V} |s_v'| \le N \lceil 4 logN + 5 \rceil + 2K</tex>.
}}
Начальная сортировка и инициализация множеств <tex>L_r</tex> и <tex>I_r</tex> может быть произведена за <tex>O(N logN)</tex> времени. Время работы функции <tex>TreeSearch</tex> является суммой длительностей всех его вызовов. Каждый вызов от внешних узлов добавляет к этой сумме <tex></tex>. Для внутренних же узлов, время требуемое для выполнения равно <tex></tex>. Если мы все это сложим, то придем к выводу, что наш алгоритм работает за <tex></tex>. Заметим, что его скорость можно увеличить до <tex></tex>, если не будем учитывать время нахождения <tex></tex>. Соответственно в оптимальном алгоритме Балабана <tex></tex> находится за <tex></tex>.
==Примечания==
