Как мне достичь сложности O (n ^ 2) для алгоритма Гейла-Шепли?

Question

Алгоритм Гейла-Шепли предназначен для решения задачи стабильного сопоставления с O (n2). В задаче сопоставления есть n женщин и n мужчин. У каждого человека есть список предпочтений, в котором каждый член противоположного пола вступает в брак. Цель состоит в том, чтобы создать пары так, чтобы никому не было бы лучше оставить свой брак для кого-то другого.

Ниже приведен псевдокод из Википедии:

algorithm stable_matching is
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to do
        w := first woman on m's list to whom m has not yet proposed
        if w is free then
            (m, w) become engaged
        else some pair (m', w) already exists
            if w prefers m to m' then
                m' becomes free
                (m, w) become engaged 
            else
                (m', w) remain engaged
            end if
        end if
    repeat

Каждый мужчина (n) может предложить до n раз в худшем случае. Это дает время l oop O (n ^ 2). Но во внутренней l oop есть строка, которая касается меня:

if w prefers m to m' then

Разве это не значит, что нам нужно перебирать список предпочтений, чтобы найти, кто появляется первым? Разве это не будет O (n), что делает алгоритм O (n ³ )?

Мои списки предпочтений для мужчин и женщин относятся к типу int[n][n]. Внешний индекс - это идентификатор человека, которому принадлежит внутренний список. Внутренний список содержит идентификаторы каждого противоположного пола, упорядоченные по предпочтению владельца.

Answer 1

Разве это не означает, что нам нужно перебирать список предпочтений, чтобы найти, кто появляется первым? Разве это не O (n), что делает алгоритм O (n3)?

Нет.

Мои списки предпочтений для мужчин и женщин относятся к типу INT [N] [N]. Внешний индекс - это идентификатор человека, которому принадлежит внутренний список. Внутренний список содержит идентификаторы всех лиц противоположного пола, упорядоченные по предпочтениям владельца.

То, что вам нужно сделать с настройками, определяет подходящую структуру данных для них. Вам нужна женщина, чтобы иметь возможность сравнивать свои предпочтения для двух разных мужчин в одно и то же время, поэтому вам следует использовать структуру данных, которая это поддерживает. Например, вы можете инвертировать списки предпочтений женщин, чтобы создать карту рангов, так что rank[m] возвращает ранг мужчины m в ее первоначальном списке предпочтений.

Создание всех карт рангов занимает O (n ² ) времени (по количеству человек), поэтому это не увеличивает общую сложность алгоритма.

Answer 2

Нет. Вам не нужно повторять, чтобы найти предпочтения. Потому что предпочтение отдается по порядку. Здесь определение предпочтения - это порядок над мужчинами или женщинами. Следовательно, вам не нужно повторяться, чтобы найти, что m предпочтительнее, чем m' или нет.