Грокаем а Иллюстрированное пособие для программистов и любопытствующих

Построение сетки за 4 сложения

азверните листок после четырех сложений — получилась замечательная сетка! Каждое сложение удваивает количество прямоугольников. За 4 опе­рации вы создали 16 прямоугольников!
При каждом складывании количество прямоугольников увеличивается вдвое, так что 16 прямоугольников строятся за 4 шага. Как записать время выполнения этого алгоритма? Напишите время выполнения обоих алго­ритмов, прежде чем двигаться дальше.
Ответы: алгоритм 1 выполняется за время 0(п), а алгоритм 2 — за время 0(log п).
«О-большое» определяет время выполнения в худшем случае
Предположим, вы используете простой поиск для поиска фамилии в теле­фонной книге. Вы знаете, что простой поиск выполняется за время О(п), то есть в худшем случае вам придется просмотреть каждую без исключения запись в телефонной книге. Но представьте, что искомая фамилия начи­нается на букву «А» и этот человек стоит на самом первом месте в вашей телефонной книге. В общем, вам не пришлось просматривать все записи — вы нашли нужную фамилию с первой попытки. Отработал ли алгоритм за время О(и)? А может, он занял время 0(1), потому что результат был получен с первой попытки?
П
ПРИМЕЧАНИЕ
Наряду с временем худшего случая также полезно учитывать среднее вре­мя выполнения. Тема худшего и среднего времени выполнения обсуждается в главе 4.

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

• 
  0(log п), или логарифмическое время. Пример: бинарный поиск.
  
• 
  0(п), или линейное время. Пример: простой поиск.
  
• 
  0(п * log п). Пример: эффективные алгоритмы сортировки (быстрая сортировка — но об этом в главе 4).
  
• 
  0(п²). Пример: медленные алгоритмы сортировки (сортировка выбо­ром — см. главу 2).
  
• 
  0(п!). Пример: очень медленные алгоритмы (задача о коммивояжере — о ней будет рассказано в следующем разделе).
  

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



КОЛИЧЕСТВО