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