Первый из рассмотренных примеров описывает худший сценарий, а второй — лучший. В худшем случае размер стека описывается как O(n). В лучшем случае он составит O(log n).
Теперь рассмотрим первый уровень стека. Один элемент выбирается опорным, а остальные элементы делятся на подмассивы. Вы перебираете все восемь элементов массива, поэтому первая операция выполняется за время O(n). На этом уровне стека вызовов вы обратились ко всем восьми элементам. Но на самом деле вы обращаетесь к O(n) элементам на каждом уровне стека вызовов!
Даже если массив будет разделен другим способом, вы все равно каждый раз обращаетесь к O(n) элементам.
Итак, завершение каждого уровня требует времени O(n).
В этом примере существуют O(log n) (с технической точки зрения правильнее сказать «высота стека вызовов равна O(log n)») уровней. А так как каждый уровень занимает время O(n), то весь алгоритм займет время O(n) * O(log n) = O(n log n). Это сценарий лучшего случая.
В худшем случае существуют O(n) уровней, поэтому алгоритм займет время O(n)* O(n) = O(n2).
А теперь сюрприз: лучший случай также является средним. Если вы всегда будете выбирать опорным элементом случайный элемент в массиве, быстрая сортировка в среднем завершится за время O(n log n). Это один из самых быстрых существующих алгоритмов сортировки, который заодно является хорошим примером стратегии «разделяй и властвуй».
Упражнения
Запишите «O-большое» для каждой из следующих операций ?
4.5 Вывод значения каждого элемента массива.
4.6 Удвоение значения каждого элемента массива.
4.7 Удвоение значения только первого элемента массива.
4.8 Создание таблицы умножения для всех элементов массива. Например, если массив состоит из элементов [2, 3, 7, 8, 10], сначала каждый элемент умножается на 2, затем каждый элемент умножается на 3, затем на 7 и т.д.
Шпаргалка
• Стратегия «разделяй и властвуй» основана на разбиении задачи на уменьшающиеся фрагменты. Если вы используете стратегию «разделяй и властвуй» со списком, то базовым случаем, скорее всего, является пустой массив или массив из одного элемента.
• Если вы реализуете алгоритм быстрой сортировки, выберите в качестве опорного случайный элемент. Среднее время выполнения быстрой сортировки составляет O(n log n)!
• Константы в «O-большом» иногда могут иметь значение. Именно по этой причине быстрая сортировка быстрее сортировки слиянием.
• При сравнении простой сортировки с бинарной константа почти никогда роли не играет, потому что O(log n) слишком сильно превосходит O(n) по скорости при большом размере списка.
5. Хеш-таблицы
В этой главе
• Вы узнаете о хеш-таблицах — одной из самых полезных базовых структур данных. Хеш-таблицы находят множество применений; в этой главе рассматриваются распространенные варианты использования.
• Вы изучите внутреннее устройство хеш-таблиц: реализацию, коллизии и хеш-функции. Это поможет вам понять, как анализируется производительность хеш-таблицы.
Представьте, что вы продавец в маленьком магазинчике. Когда клиент покупает товары, вы проверяете их цену по книге. Если записи в книге не упорядочены по алфавиту, то поиск слова «апельсины» в каждой строке займет слишком много времени. Фактически вам придется проводить простой поиск из главы 1, а для этого нужно проверить каждую запись. Помните, сколько времени это займет? O(n). Если же книга упорядочена по алфавиту, вы сможете воспользоваться бинарным поиском, время которого составляет всего O(log n).
На всякий случай напомню, что время O(n) и O(log n) — далеко не одно и то же! Предположим, вы можете просмотреть 10 записей в книге за секунду. В следующей таблице показано, сколько времени займет простой и бинарный поиск.
