Грокаем алгоритмы

При каждом складывании количество прямоугольников увеличивается вдвое, так что 16 прямоугольников строятся за 4 шага. Как записать время выполнения этого алгоритма? Напишите время выполнения обоих алгоритмов, прежде чем двигаться дальше.

Ответы: алгоритм 1 выполняется за время O(n), а алгоритм 2 — за время O(log n).

«O-большое» определяет время выполнения в худшем случае

Предположим, вы используете простой поиск для поиска фамилии в телефонной книге. Вы знаете, что простой поиск выполняется за время O(n), то есть в худшем случае вам придется просмотреть каждую без исключения запись в телефонной книге. Но представьте, что искомая фамилия начинается на букву «А» и этот человек стоит на самом первом месте в вашей телефонной книге. В общем, вам не пришлось просматривать все записи — вы нашли нужную фамилию с первой попытки. Отработал ли алгоритм за время O(n)? А может, он занял время O(1), потому что результат был получен с первой попытки?

Простой поиск все равно выполняется за время O(n). Просто в данном случае вы нашли нужное значение моментально; это лучший возможный случай. Однако «O-большое» описывает худший возможный случай. Фактически вы утверждаете, что в худшем случае придется просмотреть каждую запись в телефонной книге по одному разу. Это и есть время O(n). И это дает определенные гарантии — вы знаете, что простой поиск никогда не будет работать медленнее O(n).

примечание

Наряду с временем худшего случая также полезно учитывать среднее время выполнения. Тема худшего и среднего времени выполнения обсуждается в главе 4.

Типичные примеры «O-большого»

Ниже перечислены пять разновидностей «O-большого», которые будут встречаться вам особенно часто, в порядке убывания скорости выполнения:

• O(log n), или логарифмическое время. Пример: бинарный поиск.

• O(n), или линейное время. Пример: простой поиск.

• O(n* log n). Пример: эффективные алгоритмы сортировки (быстрая сортировка — но об этом в главе 4).

• O(n2). Пример: медленные алгоритмы сортировки (сортировка выбором — см. главу 2).

• O(n!). Пример: очень медленные алгоритмы (задача о коммивояжере — о ней будет рассказано в следующем разделе).

Предположим, вы снова строите сетку из 16 квадратов, и вы можете выбрать для решения этой задачи один из 5 алгоритмов. При использовании первого алгоритма сетка будет построена за время O(log n). В секунду выполняются до 10 операций. С временем O(log n) для построения сетки из 16 квадратов потребуются 4 операции (log 16 равен 4). Итак, сетка будет построена за 0,4 секунды. А если бы было нужно построить 1024 квадрата? На это бы потребовалось log 1024 = 10 операций, или 1 секунда. Напомню, что эти числа получены при использовании первого алгоритма.

Второй алгоритм работает медленнее: за время O(n). Для построения 16 прямо­угольников потребуется 16 операций, а для построения 1024 прямоугольников — 1024 операции. Сколько это составит в секундах?

Ниже показано, сколько времени потребуется для построения сетки с остальными алгоритмами, от самого быстрого до самого медленного:

Существуют и другие варианты времени выполнения, но эти пять встречаются чаще всего.

Помните, что эта запись является упрощением. На практике «O-большое» не удается легко преобразовать в количество операций с такой точностью, но пока нам хватит и этого. Мы еще вернемся к «O-большому» в главе 4, после рассмотрения еще нескольких алгоритмов. А пока перечислим основные результаты:

• Скорость алгоритмов измеряется не в секундах, а в темпе роста количества операций.

• По сути формула описывает, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных.

• Время выполнения алгоритмов выражается как «O-большое».

• Время выполнения O(log n) быстрее O(n), а с увеличением размера списка, в котором ищется значение, оно становится намного быстрее.

Упражнения

Приведите время выполнения «O-большое» для каждого из следующих сценариев.

1.3 Известна фамилия, нужно найти номер в телефонной книге.

1.4 Известен номер, нужно найти фамилию в телефонной книге. (Подсказка: вам придется провести поиск по всей книге!)

1.5 Нужно прочитать телефоны всех людей в телефонной книге.

1.6 Нужно прочитать телефоны всех людей, фамилии которых начинаются с буквы «А». (Вопрос с подвохом! В нем задействованы концепции, которые более подробно рассматриваются в главе 4. Прочитайте ответ — скорее всего, он вас удивит!)

Задача о коммивояжере