SRT Поиск и сортировка Приём
Нижние границы сравнений
Также: Lower bounds · нижняя граница сортировки · почему нельзя быстрее n log n · дерево решений · decision tree · метод противника · adversary argument · второй по величине · second largest · минимум и максимум · турнир на выбывание · проверка различности · element distinctness
Как доказать, что задачу нельзя решить быстрее, — сразу для всех алгоритмов, даже не придуманных. Два способа: посчитать, сколько разных ответов нужно различить, и сыграть против судьи, который решает ответы по ходу игры. Первый даёт log₂ n! для сортировки, второй — n + ⌈log₂ n⌉ − 2 сравнения, чтобы честно найти второго в турнире, ⌈3n/2⌉ − 2 для минимума и максимума и 2n − 1 для слияния.
В 1883 году Чарльз Доджсон — тот самый Льюис Кэрролл — выпустил брошюру о теннисных турнирах. Его возмутило, что второй приз по олимпийской системе получает проигравший в финале: второй по силе игрок мог вылететь гораздо раньше, просто встретив чемпиона. Ниже турнир шестнадцати крупнейших городов, где «сила» — население. Финалист оказывается настоящим вторым в среднем лишь в восьми жеребьёвках из пятнадцати.
Починить это дёшево. Настоящий второй проиграл только чемпиону — значит, он среди тех четверых, кого чемпион обыграл, и трёх матчей между ними хватает. Всего 15 + 3 = 18 матчей, а не 29, как если бы второй тур начать заново. Но можно ли обойтись семнадцатью? Ответ «нет» — это утверждение уже не об одном алгоритме, а обо всех сразу, включая ещё не придуманные. Такие утверждения называют нижними границами, и ниже — два способа их доказывать.
Идея
Нижняя граница говорит про модель, а не про программу: о данных можно узнавать только из сравнений «меньше или нет», и мы считаем, сколько вопросов нужно. Первый способ — подсчёт исходов: k ответов «да» или «нет» различают не больше 2k случаев, поэтому задаче с N возможными ответами нужно ⌈log₂ N⌉ вопросов. Второй — противник: ответы даёт не заранее заданный вход, а судья, который решает их по ходу игры, не противореча себе, и тянет время.
Сортировка: log₂ n!
Любая сортировка сравнениями на n различных числах в худшем случае делает не меньше ⌈log₂ n!⌉ сравнений.
Что алгоритм делает дальше, зависит только от уже полученных ответов. Поэтому за k сравнений он проходит не больше 2k разных путей. Два разных порядка входа не могут пройти один и тот же путь: алгоритм сделал бы с ними одно и то же, а одна перестановка не упорядочивает два по-разному перепутанных списка. Порядков n!, поэтому 2k ≥ n! и k ≥ log₂ n!.
Пути удобно рисовать деревом вопросов; как оно выглядит для трёх и пяти карт и как играть в эту теорему против судьи, разобрано в главе курса о поиске и сортировке. По формуле Стирлинга log₂ n! ≈ n log₂ n − 1,44n. Для всех 45 227 городов GeoNames это 634 192 сравнения. Сортировка слиянием делает на них 641 358 — на 1,1 % больше границы.
И в среднем тоже
Худший случай бывает редко. Может быть, хотя бы в среднем удастся обойтись меньшим числом сравнений?
Если все n! порядков входа равновероятны, любая сортировка сравнениями делает в среднем не меньше log₂ n! сравнений.
Пусть порядок номер i сортируется за di сравнений. Ответы алгоритма на разных порядках — разные строки из нулей и единиц, и ни одна не начало другой: получив те же ответы, алгоритм остановился бы в том же месте и выдал бы тот же порядок. Для таких строк верно неравенство Крафта: Σ 2−di ≤ 1. Среднее геометрическое не больше среднего арифметического, поэтому 2−(среднее d) ≤ (1/n!) Σ 2−di ≤ 1/n!, то есть среднее d ≥ log₂ n!.
Отсюда следует и то, что случайность не помогает. Быструю сортировку со случайным опорным можно считать лотереей: монетки выбирают один из обычных, неслучайных алгоритмов. Каждый из них в среднем по входам делает не меньше log₂ n! сравнений, значит, и лотерея в среднем по входам — тоже. А раз в среднем по входам не меньше, то на каком-то входе ожидаемое число сравнений не меньше log₂ n!. Перемешав города, листинг ниже даёт сортировке слиянием случайный порядок, и она делает 643 494 сравнения — снова чуть больше границы.
Судья, который не загадывает
Подсчёт исходов работает не всегда. Самое большое из n чисел — один из n ответов, и подсчёт обещает лишь log₂ n сравнений. На деле нужно n − 1: каждое число, кроме самого большого, должно хоть раз проиграть, иначе оно может оказаться самым большим, а в каждом сравнении проигравший один. Пара «наибольшее и второе» — один из n(n − 1) ответов, около 2 log₂ n вопросов по подсчёту. Настоящую границу даёт другой приём.
Противник не загадывает числа заранее. На каждый вопрос он отвечает так, как ему выгоднее, следя только за одним: ответы не должны противоречить друг другу, то есть какие-то числа должны им удовлетворять. Если против такого судьи любой алгоритм задаёт не меньше k вопросов, то и для любого алгоритма найдётся вход, на котором вопросов не меньше k: это числа, которые судья «имел в виду» в конце игры. Сыграйте против него сами — восемь карт, найдите вторую по величине.
Чтобы найти второе по величине из n различных чисел, нужно в худшем случае не меньше n + ⌈log₂ n⌉ − 2 сравнений, и столько хватает.
Судья. У каждого числа вес, сначала 1. Если сравнивают два числа, которые ещё не проигрывали, побеждает более тяжёлое, и оно забирает вес побеждённого. Если не проигрывало только одно — побеждает оно. Если проигрывали оба, судья отвечает так, как следует из прежних ответов, а если не следует — как угодно. Ответы не противоречат друг другу: число, которое ни разу не проигрывало, ни разу не оказывалось меньше другого, и объявить его большим всегда можно.
Вес лидера. Пока непроигравших два или больше, неизвестно, какое из них самое большое. Значит, в конце непроигравший один — максимум m, и он собрал весь вес n: вес переходит только от проигравших к победителям. Выигрывая у непроигравшего, m побеждает не более тяжёлого, то есть его вес растёт не больше чем вдвое. Чтобы от 1 дойти до n, нужно не меньше ⌈log₂ n⌉ таких побед. Обозначим через k ≥ ⌈log₂ n⌉ число тех, кто проиграл m напрямую.
Подсчёт поражений. Число x, про которое известно только, что оно меньше m, ещё может быть вторым. Значит, каждое число, кроме m и второго, хоть раз проиграло кому-то, кроме m. Второе же проиграло именно m, иначе выше него стоял бы кто-то ещё. Сложим поражения. Те k, кто проиграл m, дают k поражений, и все они, кроме второго, проиграли ещё кому-то — это k − 1. Остальные n − 1 − k чисел проиграли хотя бы по разу. Всего не меньше k + (k − 1) + (n − 1 − k) = n + k − 2 ≥ n + ⌈log₂ n⌉ − 2 поражений, а каждое сравнение даёт ровно одно.
Хватает. Турнир на выбывание с ровной сеткой занимает n − 1 матч, и чемпион играет в нём не больше ⌈log₂ n⌉ раз. Второй проиграть мог только чемпиону, поэтому он среди обыгранных им, и самый сильный из них находится ещё не больше чем за ⌈log₂ n⌉ − 1 матч.
В игре видно, как работает судья: лидер тяжелеет не больше чем вдвое за победу, и восемь карт нельзя закончить быстрее девяти сравнений. Режим «минимум и максимум» — другая задача и другой судья.
Чтобы найти и наименьшее, и наибольшее из n чисел, нужно в худшем случае не меньше ⌈3n/2⌉ − 2 сравнений, и столько хватает.
Отметим про каждое число, выигрывало ли оно и проигрывало ли. В конце каждое число, кроме наибольшего, проигрывало, а каждое, кроме наименьшего, выигрывало, иначе ответ не определён: всего не меньше 2n − 2 отметок. Судья отвечает так: число, которое не проигрывало, побеждает проигравшее; число, которое не выигрывало, проигрывает выигравшему; в остальных случаях — как следует из прежних ответов, или как угодно. Противоречий нет по той же причине, что выше: непроигравшее ни разу не оказывалось меньше другого, невыигравшее — больше. Сравнение двух ещё не сравнивавшихся чисел даёт две новые отметки. Если не сравнивалось только одно, новая отметка появляется только у него: против проигрывавшего оно побеждает, против только выигрывавшего — проигрывает. Если сравнивались оба, у каждого уже есть отметка, и новых могло бы быть две только при победе числа, которое лишь проигрывало, над числом, которое лишь выигрывало, — а судья так не отвечает. Встреч двух несравнивавшихся не больше ⌊n/2⌋, поэтому сравнений не меньше 2n − 2 − ⌊n/2⌋ = ⌈3n/2⌉ − 2.
Хватает их так: разбить числа на пары и сравнить внутри пар, потом искать наибольшее среди победителей и наименьшее среди проигравших; число без пары, если n нечётно, идёт в обе группы. Это ⌊n/2⌋ + 2(⌈n/2⌉ − 1) = ⌈3n/2⌉ − 2 сравнения.
Соседей не обойти
У противника есть простая и сильная форма — она даёт границы, где подсчёт исходов немного не дотягивает.
Алгоритм сравнений, который определяет порядок всех чисел, на каждом входе напрямую сравнивает каждую пару соседей в итоговом порядке.
Пусть a и b — соседи, a < b, и их ни разу не сравнили. Поменяем их значения местами. Для любого третьего числа c ответы не изменятся: между a и b нет других чисел, поэтому c меньше a ровно тогда, когда c меньше b. Алгоритм получит те же ответы и выдаст тот же порядок, а он теперь неверен.
Отсюда две границы. Слияние. Два отсортированных списка по n чисел, которые чередуются: a1 < b1 < a2 < b2 < … < an < bn. Все 2n − 1 пар соседей — из разных списков, и если обменять значения у пары соседей, оба списка останутся отсортированными. Значит, рассуждение леммы проходит и здесь: каждую такую пару придётся сравнить. Обычное слияние тратит как раз 2n − 1 сравнений и, значит, оптимально. Подсчёт исходов дал бы меньше: способов перемешать два списка C(2n, n), и для n = 1000 это 1995 вопросов против настоящих 1999.
Проверка, что все числа разные. Пусть алгоритм сравнивает с ответами «меньше», «равно», «больше» и на числах, которые все различны, отвечает «различны». Тогда он сравнил каждую пару соседей: иначе соседа можно сделать равным другому соседу, ответы не изменятся, а «различны» станет неправдой. На различных числах ответ «равно» не выпадает, сравнения ветвятся надвое, и, зная все пары соседей, алгоритм знает порядок. Получается та же граница ⌈log₂ n!⌉: проверить, что все разные, сравнениями не легче, чем отсортировать. Хеш-таблица делает это в среднем за O(n) — потому что она не сравнивает, а вычисляет адрес.
Лемма о соседях — основа задачи статьи: по журналу сравнений, который оставила сортировка, решить, восстанавливается ли порядок.
Код
Листинг решает задачи статьи на 45 227 городах, сравнивая их по населению, и считает сравнения: два прохода против турнира с доигровкой, минимум и максимум по отдельности и парами, сортировку слиянием в порядке файла и после перемешивания. Рядом — нижняя граница для каждой задачи.
45227 towns, compared by population task comparisons lower bound the largest, one pass 45226 45226 largest and second: two passes 90451 45241 largest and second: knockout 45241 45241 smallest and largest: separately 90452 67839 smallest and largest: in pairs 67839 67839 merge sort, the file's order 641358 634192 merge sort, shuffled 643494 634192 the largest: 24874500, the second: 22000000
Турнир и пары выходят точно на границу, и это уже не совпадение, а теорема. Два прохода тратят на второе по величине почти вдвое больше. Сортировка слиянием отстаёт от ⌈log₂ n!⌉ примерно на процент — и в порядке файла, и на перемешанных данных.
Сколько это стоит
| Задача | Нижняя граница | Кто её достигает |
|---|---|---|
| наибольшее | n − 1 | один проход |
| наибольшее и второе | n + ⌈log₂ n⌉ − 2 | турнир и доигровка |
| наименьшее и наибольшее | ⌈3n/2⌉ − 2 | сравнение парами |
| слияние двух списков по n | 2n − 1 | обычное слияние |
| поиск места в отсортированном | ⌈log₂ (n + 1)⌉ | двоичный поиск |
| сортировка | ⌈log₂ n!⌉ ≈ n log₂ n − 1,44n | не всегда достижима; слияние на наших данных — на 1–1,5 % больше |
| все ли различны | ⌈log₂ n!⌉ | сортировка и проверка соседей |
Границы точные: для каждой задачи, кроме сортировки, есть алгоритм, который делает ровно столько сравнений в худшем случае. Для сортировки ⌈log₂ n!⌉ достижима не всегда: на двенадцати числах нужно 30 сравнений, а граница обещает 29.
Где граница кончается
Все эти границы — про модель, где о данных узнают только сравнениями. Выйдите из неё, и они перестают действовать.
- Подсчёт и разряды. Сортировка подсчётом задаёт вопрос «в какую из k ячеек?» с k вариантами ответа за одно обращение к памяти и сортирует за O(n + k).
- Хеширование. Найти повторы, посчитать различные — в среднем за O(n), хотя сравнениями нужно ⌈log₂ n!⌉.
- Машинные слова. Если ключи — целые числа в машинных словах, их можно сортировать быстрее n log n: Ицзе Хань в 2002 году показал O(n log log n) без случайности. На практике это остаётся теорией, но граница log₂ n! к таким ключам не относится.
- Вычисления, а не только сравнения. Если разрешить сложение и умножение чисел, граница для проверки различности сохраняется: Майкл Бен-Ор в 1983 году доказал Ω(n log n) для алгебраических деревьев решений, где в узлах проверяют знак многочлена от входа.
История
Задачу о втором месте поставил Кэрролл в 1883 году. В 1932 году Юзеф Шрейер описал способ найти первого и второго за n + ⌈log₂ n⌉ − 2 партий и предположил, что лучше нельзя. После нескольких неверных попыток первое правильное доказательство опубликовал в 1964 году Сергей Кислицын. Границу для минимума и максимума вместе с оптимальным способом опубликовал Айра Пол в 1972 году. Судья, который отвечает так, чтобы алгоритму было хуже всего, с тех пор — один из главных инструментов, когда нужно доказать, что быстрее нельзя.
Задачи
В задаче — журнал сравнений, который оставила настоящая сортировка, с частью стёртых записей. Восстанавливается ли порядок? Ответ даёт лемма о соседях.
Журнал сравненийДанные: Населённые пункты: GeoNames, CC BY 4.0