19
правок
Изменения
Нет описания правки
Причем, стоит отметить, что собственно наличие/отсутствие пары в очереди можно не проверять. Если для некоторого <tex>c</tex> пара <tex>\langle R_1, c \rangle</tex> уже была в очереди, то мы добавим её "вторую половинку" <tex>\langle R_2, c \rangle</tex>. Если её в очереди не было, то мы вольны сами выбирать, какой подкласс добавлять в очередь, и таким образом добавляем опять же <tex>\langle R_2, c \rangle</tex>.
И еще одна деталь. <tex>\mathtt{swapClasses}(R_1,\ R_2)</tex> вызывается только в том случае, когда <tex> \mathrm{cnt1} \leqslant \mathrm{cnt2} </tex>, из чего следует <tex>\mathrm{cnt1} + \mathrm{cnt2} <= 2 \cdot |\mathtt{Inverse}| </tex>, т.к. <tex>\mathrm{cnt2} = |\mathtt{Inverse}|</tex>. Таким образом, вызов <tex>\mathtt{swapClasses}(R_1,\ R_2)</tex> не ухудшает ассимптотику.
===Время работы===
