Временная сложность алгоритма, который находит «звезду» среди множества людей

Question

Я столкнулся с проблемой, которая попросила найти звезду среди множества нормальных людей. Определение звезды - «тот, кто никого не знает, но все знают их». Входные данные представляют собой массив из n человек, и элементарный тест, который вы можете сделать, - это спросить человека i «знаете ли вы человека j», на который они отвечают «true», если они знают его, и false, если нет. Задавая минимальное количество вопросов.

Лучшее решение для наихудшего сценария, которое я нашел для этого алгоритма, - это O (nlog) (вы спрашиваете человека, знают ли они человека после него, я + 1, если они делают,вы удаляете их из потенциальной звезды, если нет, вы убираете i + 1 из потенциальной звезды, с каждым прогоном массива я могу вдвое сократить количество потенциальных звезд) Но отрывок сказал: «Докажите, что это можно сделать вO (n) в худшем случае

Answer 1

Определение звезды - это "тот, кто никого не знает, но все знают его.

. По этому определению в группе людей может быть не более одной" звезды ". Если бы было больше одной звезды, то они оба должны были бы знать другую, иначе другая не была бы звездой, но тогда они сами не были бы звездами.

Таким образом, есть две подзадачи.

1. Найдите потенциальные звезды.

Если таких людей более одного, звезды нет, если такой человек точно:

Проверьте, все ли знают этого человека.

Первая часть может быть выполнена с помощью предложенного вами алгоритма. Независимо от того, спрашиваете ли вы, знает ли А В, знает ли С, знает ли D и т. Д., Или если вы спросите, знает ли «победитель» А или В и т. вам потребуется не более O (n) шагов, а не O (nlogn). После этого у вас осталась одна потенциальная звезда, и вы можете выполнить второй шаг, который представляет собой простой цикл над всеми другими людьми в группе.

Сложность по времени для обоих шагов равна O (n) длявсего (все еще) O (n).