403
правки
Изменения
→Время работы
|proof =
Рассмотрим пару <tex>(C,a)</tex>, где <tex>p \in C</tex>, которую мы удаляем из очереди. И пусть <tex>(C',a)</tex> следующая пара, где <tex>p \in C'</tex> и которую мы удалим из очереди. Согласно нашему алгоритму класс <tex>C'</tex> мог появиться в очереди только после операции <tex>Replace</tex>. Но после первого же разбиения класса <tex>C</tex> на подклассы мы добавим в очередь пару <tex>(C'', a)</tex>, где <tex>C''</tex> меньший из образовавшихся подклассов, то есть <tex>|C''| \leqslant |C| \ / \ 2</tex>. Так же заметим, что <tex>C' \subseteq C''</tex>, а следовательно <tex>|C'| \leqslant |C| \ / \ 2</tex>. Но тогда таких пар не может быть больше, чем <tex>\log_2(|Q|)</tex>.
}}
{{Лемма
|about = 4
|id = Лемма4
|statement =
<tex>\sum |Inverse|</tex> по всем итерациям цикла <tex>while</tex> не превосходит <tex>|\Sigma| \cdot |Q| \cdot \log_2(|Q|)</tex>.
|proof =
Пусть <tex>x, y \in Q</tex>, <tex>a \in \Sigma</tex> и <tex> \delta(x, a) = y</tex>. Зафиксируем эту тройку. Заметим, что количество раз, которое <tex>x</tex> встречается в <tex>Inverse</tex> при условии, что <tex> \delta(x, a) = y</tex>, совпадает с числом удаленных из очереди пар <tex>(C, a)</tex>, где <tex>y \in C</tex>. Но по [[#Лемма3 | лемме(3)]] эта величина не превосходит <tex>\log_2(|Q|)</tex>. Просуммировав по всем <tex> x \in Q </tex> и по всем <tex> a \in \Sigma</tex> мы получим утверждение леммы.
}}
