3622
правки
Изменения
м
→КНФ в форме Хорна
Обозначим за <tex>N</tex> число вхождений переменных в формулу.
Итерация состоит из шагов, каждый из которых выполняется за <tex>O(N)</tex>. Всего итераций будет не больше <tex>N</tex>, так как если первый шаг не завершил алгоритм, то уменьшил размер формулы на одинодно вхождение. Итого, асимптотика алгоритма составляет <tex>O(N^2)</tex>.
}}
{{Утверждение
