174
правки
Изменения
→Доказательство
=== Доказательство ===
На <tex>i-</tex>''i-ом'' шаге выполняется следующий инвариант: если <tex>count > 0</tex>, то <tex>candidate</tex> - мажорирующий элемент на подмассиве <tex>a[0..i]</tex>, либо мажорирующего элемента на данном подмассиве не существует. Тогда на ''N-ом'' шаге <tex>candidate</tex> будет содержать мажорирующий элемент на всем массиве, т.к. гарантируется его существование. Покажем, что данный инвариант всегда выполняется.
Пусть данный инвариант выполняется на <tex>k-</tex>''k-ом'' шаге. Тогда на ''<tex>(k+1)-</tex>''ом'' шаге возможны 3 варианта:
# <tex>count = 0</tex><p>Очевидно, что на подмассиве <tex>a[0..k]</tex> мажорирующего элемента не существует, так как все элементы разбились на пары. Тогда только <tex>a[k+1]</tex> может быть мажорирующим элементом.</p>
# <tex>count > 0</tex> и <tex>a[k+1] = candidate</tex><p>Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элемент, то он находится в <tex>candidate</tex>. Тогда, в силу равенства <tex>a[k+1]</tex> и <tex>candidate</tex>, если на подмассиве <tex>a[0..(k+1)]</tex> существует мажорирующий элемент, то он тоже будет равен <tex>candidate</tex>.</p>
