Алгоритмы для жизни: Простые способы принимать верные решения (Гриффитс, Кристиан) - страница 59
С теоретической точки зрения, организация работы в Престонском сортирочном центре тоже не может не впечатлить. Книги, проходящие через его системы, сортируются в условиях линейного времени O(n).
Важно отметить, что линейно-логарифмическое время O(n log n), которое применяется в методе сортировки с объединением, – действительно лучший показатель, которого мы только можем добиться. Было доказано, что если мы хотим полностью отсортировать n элементов посредством прямого сравнительного исследования, то у нас только один выход – сравнивать их O(n log n) количество раз. Это фундаментальный закон Вселенной, и нет способа его обойти.
Но это не значит, что мы можем закончить нашу книгу на алгоритмах сортировки. Потому что иногда вам и не нужен полностью упорядоченный комплект и порой сортировку можно выполнить и без непосредственного сравнения одного элемента с другим.
Два вышеупомянутых принципа, вместе взятые, предусматривают возможность проведения грубых практических сортировок быстрее линейно-логарифмического времени. Этот факт очень наглядно демонстрирует алгоритм, известный как сортировка группировками, который и применяется в Престонском сортировочном центре. При применении этого метода элементы разбиваются на группы по количеству категорий сортировки без проведения межкатегорийной сортировки (это можно сделать позднее). (В компьютерной науке термин «корзина» обозначает фрагмент неупорядоченных данных, но некоторые довольно-таки буквально воспринимают название метода и применяют его в своей работе, как, например, это делают в Библиотечной системе округа Кинг.)
А вот и изюминка этого метода: если вы хотите сгруппировать n единиц в m корзин, то весь процесс займет у вас время, рассчитываемое по формуле O(n · m), – то есть время, прямо пропорциональное количеству категорий, умноженному на количество корзин.
И поскольку количество корзин относительно невелико по сравнению с количеством сортируемых единиц, то «О большое» округлит показатель времени до O(n), или до линейного времени.
Ключ к преодолению линейно-логарифмического барьера – в знании классификации сортируемых элементов. Неправильно выбранные корзины загонят вас в тот же угол, в котором вы находились в начале процесса сортировки. Если, к примеру, в конце процесса все книги окажутся в одной корзине, то вы не добились никакого результата. Верно подобранные корзины разделят ваши элементы на примерно равные по величине группы, что само по себе – учитывая фундаментальную характеристику сортировки «масштаб убивает» – огромный шаг на пути к полному порядку. В Престонском сортировочном центре, задачей которого в первую очередь является сортировка книг по тематике и потом уже в алфавитном порядке, подбор корзин происходит на основании статистики обращения. Некоторые тематики пользуются гораздо большей популярностью, и для соответствующих книг может быть выделено несколько корзин.