1 ГЛАВА 'Время выполнения алгоритмов растет с разной скоростью'
Боб пишет алгоритм поиска для NASA. Его алгоритм заработает, когда ракета будет подлетать к Луне, и поможет вычислить точку посадки.
Это один из примеров того, как время выполнения двух алгоритмов растет с разной скоростью. Боб пытается выбрать между простым и бинарным поиском. Его алгоритм должен работать быстро и правильно. С одной стороны , бинарный поиск работает быстрее. У Боба есть всего 10 секунд,чтобы выбрать место посадки; если он не уложится в это время, то момент для посадки будет упущен. С другой стороны, простой поиск пишется проще и вероятность ошибок в нем ниже ... Конечно , Боб совершенно не хочет допустить ошибку в коде посадки ракеты. И тогда для пущей уверенности Боб решает измерить время выполнения обоих алгоритмов для списка из 100 элементов.
Допустим, проверка одного элемента занимает 1 миллисекунду (мс) . При простом поиске Бобу придется проверить 100 элементов, поэтому поиск займет 100 мс. С другой стороны, при бинарном поиске достаточно проверить всего 7 элементов (log100 равен приблизительно 7), а поиск займет 7 мс. Но реальный список может содержать более миллиарда элементов. Сколько времени в таком случае потребуется для выполнения простого поиска? А при бинарном поиске? Обязательно ответьте на оба вопроса, прежде чем продолжить чтение.
Время выполнения простого и бинарного поиска для списка из 100 элементов
Боб проводит бинарный поиск с 1 миллиардом элементов, и на это уходит 30 мс (log1 ООО ООО ООО равен приблизительно 30). «32 мс! - думает Боб. -Бинарный поиск в 15 раз быстрее простого, потому что простой поиск для 100 элементов занял 100 мс, а бинарный поиск занял 7 мс. Значит, простой поиск займет 30 х 15 = 450 мс, верно? Гораздо меньше отведенных 10 секунд. И Боб выбирает простой поиск. Верен ли его выбор?
Нет, Боб ошибается. Глубоко ошибается. Время выполнения для простого поиска с 1 миллиардом элементов составит 1 миллиард миллисекунд, а это 11 дней! Проблема в том, что время выполнения для бинарного и простого поиска растет с разной скоростью.
Время выполнения растет с совершенно разной скоростью!
Другими словами, с увеличением количества элементов бинарный поиск занимает чуть больше времени. А простой поиск займет гораздо больше времени. Таким образом , с увеличением списка бинарный список внезапно начинает работать гораздо быстрее простого. Боб думал, что бинарный поиск работает в 15 раз быстрее простого, но это не так. Если список состоит из 1 миллиарда элементов, бинарный поиск работает приблизительно в 33 миллиона раз быстрее. Бот почему недостаточно знать, сколько времени должен работать алгоритм, - необходимо знать, как возрастает время выполнения с ростом размера списка. Здесь-то вам и пригодится 'О-большое'.
«О-большое» описывает, насколько быстро работает алгоритм. Предположим, имеется список размера п. Простой поиск должен проверить каждый элемент, поэтому ему придется выполнить п операций. Бремя выполнения « О-большое» имеет вид О(n). Постойте, но где же секунды? А их здесь нет - 'О-большое' не сообщает скорость в секундах, а позволяет сравнить количество операций . Оно указывает, насколько быстро возрастает время выполнения алгоритма.
А теперь другой пример. Для проверки списка размером п бинарному поиску потребуется log n операций. Как будет выглядеть «О-большое»? O(log n) . В общем случае 'О-большое' выглядит так:
Такая запись сооб щает количество операций, которые придется выполнить алгоритму. Она называется «О-большое», потому что перед количеством операций ставится символ «0» (а большое - потому что в верхнем регистре).
Теперь рассмотрим несколько примеров. Попробуйте самостоятельно оценить время выполнения этих алгоритмов.