Этапы анализа алгоритмов

Для начала рассмотрим ситуацию с точки зрения женщины w во время выпол- нения алгоритма. Какое-то время она не получает предложений и остается сво- бодной. Потом мужчина m может сделать ей предложение, и она становится помолвленной. Со временем она может получить дополнительные предложения и принять те из них, в которых повышается оценка ее партнера. Итак, мы приходим к следующим выводам:

С точки зрения мужчины m, во время выполнения алгоритма все происходит иначе. Он остается свободным до тех пор, пока не сделает предложение женщине

с наивысшей оценкой в его списке; в этот момент он может вступить в помолвку — а может и не вступить. С течением времени он может переходить из свободного со- стояния в состояние помолвки и обратно; однако при этом продолжает действовать следующее утверждение.

(1.2) Последовательность женщин, которым m делает предложение, постоянно ухудшается (в контексте его списка предпочтений).

Теперь мы покажем, что алгоритм завершается, и оценим максимальное коли- чество итераций, необходимых для завершения.

(1.3) Алгоритм Гейла–Шепли завершается после выполнения максимум n2

итераций цикла «Пока».

Доказательство. Полезная стратегия определения верхней границы времени выполнения основана на поиске метрики продвижения, а именно: следует найти какую-то точную формулировку того, насколько каждый шаг, выполняемый алго- ритмом, приближает его к завершению.

В рассматриваемом алгоритме каждая итерация состоит из предложения, ко- торое некий мужчина делает (не более одного раза) женщине, к которой он еще не обращался ранее.

Итак, если обозначить P(t) множество пар (m, w), в которых мужчина m делал предложение w к моменту завершения итерации t, мы видим, что для всех t размер P(t + 1) строго больше размера P(t). Однако всего существует только n2 возможных пар, так что за время выполнения алгоритма значение P(·) может возрасти не более n2 раз. Следовательно, выполнение алгоритма может по- требовать не более n2 итераций. ■

В приведенном утверждении и его доказательстве заслуживают внимания два обстоятельства. Во-первых, некоторые выполнения алгоритма (с некоторыми списками предпочтений) могут потребовать около n2 итераций, так что анализ до- статочно близок к лучшей возможной оценке.

Во-вторых, существует много других метрик, которые не так хорошо подходят для оценки продвижения алгоритма, по- скольку они не обязательно строго возрастают при каждой итерации. Например, количество свободных участников (а также количество помолвленных пар) может оставаться постоянным между итерациями. Следовательно, эти величины не могут использоваться непосредственно для определения верхней границы максимально возможного количества итераций, как в предыдущем абзаце.