1 ГЛАВА 'Типичные примеры «О-большого»'
Ниже перечислены пять разновидностей «О-большого», которые будут встречаться вам особенно часто, в порядке убывания скорости выполнения:
* O(log n ), или логарифмическое время. Пример: бинарный поиск.
* О(n), или линейное время. Пример: простой поиск.
* О(n * log n). Пример: эффективные алгоритмы сортировки (быстрая сортировка - но об этом в главе 4).
* О(n^2 ). Пример: медленные алгоритмы сортировки (сортировка выбором-см. главу 2).
* О(n!). Пример: очень медленные алгоритмы (задача о коммивояжере - о ней будет рассказано в следующем разделе).
Предположим, вы снова строите сетку из 16 квадратов, и вы можете выбрать для решения этой задачи один из 5 алгоритмов. При использовании первого алгоритма сетка будет построена за время O(log n ). В секунду выполняются до 10 операций. С временем O(log n) для построения сетки из 16 квадратов потребуются 4 операции (log 16 равен 4). Итак , сетка будет построена за 0,4 секунды. А если бы было нужно построить 1024 квадрата? На это бы потребовалось log 1024 = 10 операций, или 1 секунда. Напомню, что эти числа получены при использовании первого алгоритма.
Второй алгоритм работает медленнее: за время О(n). Для построения 16 прямоугольников потребуется 16 операций , а для построения 1024 прямоугольников - 1024 операции. Сколько это составит в секундах?
Ниже показано, сколько времени потребуется для построения сетки с остальными алгоритмами, от самого быстрого до самого медленного:
Существуют и другие варианты времени выполнения, но эти пять встречаются чаще всего.
Помните, что эта запись является упрощением . На практике «О-большое»не удается легко преобразовать в количество операций с такой точностью,но пока нам хватит и этого. Мы еще вернемся к «О-большому» в главе 4, после рассмотрения еще нескольких алгоритмов. А пока перечислим основные результаты :
*Скорость алгоритмов измеряется не в секундах, а в темпе роста количества операций.
*По сути формула описывает, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных.
*Время выполнения алгоритмов выражается как «О-большое».
*Бремя выполнения O(log n) быстрее О(n), а с увеличением размера списка, в котором ищется значение, оно становится намного быстрее.
Упражнения
Приведите время выполнения «О-большое» для каждого из следующих сценариев.
1.3 Известна фамилия, нужно найти номер в телефонной книге.
1.4 Известен номер, нужно найти фамилию в телефонной книге. (Подсказка: вам придется провести поиск по всей книге!)
1.5 Нужно прочитать телефоны всех людей в телефонной книге.
1.6 Нужно прочитать телефоны всех людей, фамилии которых начинаются с буквы «А». (Вопрос с подвохом! В нем задействованы концепции, которые более подробно рассматриваются в главе 4. Прочитайте ответ - скорее всего, он вас удивит!)