Поиск победителя и второго победителя

Question

Я просматривал этот пост о сложности поиска победителя и второго победителя в наименьших сравнениях.

В сообщении говорится, что для этого потребуется n + log(n) - 2 сравнений. Я понимаю, что для построения кучи и определения победителя потребуется n-1 сравнений. Но кроме этого, я не могу понять, как дополнительные log(n) - 1 сравнения необходимы, чтобы узнать второго победителя.

Насколько я понимаю, для определения второго победителя требуется постоянное количество сравнений, потому что нам просто нужно найти двух самых последних игроков, которые соревновались с победителем, из построенной кучи, и это не в сумме составляет log n - 1.

Answer 1

Сбалансированный турнир с одиночным выбыванием с n участниками состоит из k = ceil(log2(n)) раундов: половина участников выбывает в каждом раунде;только последние два будут играть за все k раундов.

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

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