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. Прочитайте ответ -         скорее всего, он вас удивит!)