Алгоритмы для жизни: Простые способы принимать верные решения - [34]
«В качестве математического обоснования можно сказать следующее, – продолжил он. – Вероятность того, что второй по мастерству игрок получит приз, который он заслуживает, может оцениваться только как 16 к 31. В то время как вероятность того, что четыре лучших игрока получат соответствующие призы, настолько мала, что может расцениваться как 12 к 1 против того, что это случится!»
Но, несмотря на всю силу своего пера, Доджсон не оказал значительного влияния на мир большого тенниса. Его предложение использовать неудобный принцип тройного выбывания, при котором проигрыш игрока, которого вы победили, мог бы также выбить из турнира и вас, так и не прижилось. Но, если решение Доджсона было громоздким, его критика существующих проблем тем не менее попала в цель. (Хотя, к сожалению, серебряные медали и по сей день все так же выдаются в турнирах на выбывание.)
Но логику Доджсона можно понять и на более глубоком уровне. Мы, люди, сортируем не только наши данные, не только наше окружение. Мы сортируем сами себя.
Чемпионаты мира, Олимпийские игры, турниры Национальной ассоциации студенческого спорта, Национальной футбольной, хоккейной, баскетбольной лиги, Главной лиги бейсбола – все эти соревнования неявно реализуют принципы сортировки. Сезонные соревнования, турниры, игры на выбывание и т. д. есть не что иное, как алгоритмы, способствующие определению места в общей «табели о рангах».
Один из наиболее известных алгоритмов в спорте – циклический алгоритм, при котором каждая из n команд в конечном итоге играет с каждой из остальных (n − 1) команд. Это один из самых распространенных форматов, но и один из самых трудоемких. Ситуация, при которой каждая команда сражается с каждой из остальных, схожа с тем, как если бы у вас на вечеринке все гости решили обменяться объятиями: появляется страшная формула O(n2), или квадратичное время.
Турнир на выбывание, популярный в таких видах спорта, как бадминтон, сквош и ракетбол, расставляет игроков с использованием линейного рейтинга. При этом каждый игрок имеет право бросить прямой вызов игроку, находящемуся непосредственно над ним в этом рейтинге. А в случае победы – поменяться с ним местами. Турнир на выбывание, будучи типичным примером пузырьковой сортировки в спорте, также характеризуется квадратичной зависимостью, требуя O(n2) количества игр для формирования стабильного рейтинга.
Тем не менее, возможно, наиболее распространенным форматом состязаний среди многих других является соревнование с использованием турнирной сетки – как, например, в известном баскетбольном турнире March Madness, проводимом Национальной ассоциацией студенческого спорта. Этот турнир прогрессирует от одной тридцатой финала и одной шестнадцатой финала к одной восьмой, затем – элитная восьмерка, финальная четверка и, наконец, финал. Каждый последующий раунд сокращает список участников наполовину, что выглядит привычно, не так ли? Эти турниры – эффективный пример использования сортировки с объединением, когда дело начинается с несортированных пар команд, которые затем сопоставляются и сравниваются.
А поскольку мы знаем, что сортировка с объединением характеризуется линейно-логарифмической зависимостью от времени – O(n log n), то, с учетом того факта, что соревнуются 64 команды, мы можем ожидать, что для проведения турнира потребуется всего около 6 раундов (192 игры), а не бесконечных 63 раунда (2016 игр), которые понадобились бы, чтобы сформировать турнир.
«Шесть раундов March Madness» – звучит прекрасно. Но погодите секунду: 192 игры? Ведь этот турнир Национальной ассоциации студенческого спорта длится всего 63 игры.
В реальности турнир March Madness не может служить полноценным примером сортировки слиянием, поскольку в его рамках не производится полное упорядочение всех 64 команд. Ведь для того, чтобы по-настоящему ранжировать все команды, организаторы должны были бы вспомнить о линейно-логарифмической зависимости и назначить ряд дополнительных игр, чтобы определить серебряного призера, затем еще – для определения бронзового призера и т. д. Но этого не происходит на турнире. Вместо этого, точно копируя подход теннисного турнира, на который жаловался Доджсон, March Madness использует формат поочередного выбывания, где проигравшая команда, выбывая из соревнований, выбывает и из дальнейшей сортировки. Преимущество такого подхода заключается в том, что он использует линейную зависимость от времени, поскольку каждая игра исключает ровно одну команду. Поэтому, чтобы осталась одна команда, на турнире должно быть сыграно только (n − 1) игр. Минусом является тот факт, что вы никогда не поймете, какое место занимает ваша команда в общей турнирной таблице, если только не займете первое место.
