1 ГЛАВА 'Наглядное представление «О-большое»'
Чтобы повторить следующий практический пример, достаточно иметь несколько листков бумаги и карандаш. Допустим, вы должны построить сетку из 16 квадратов.
Алгоритм 1
Как вариант можно нарисовать 16 квадратов, по одному за раз. Напоминаю: 'О-большое' подсчитывает количество операций. В данном примере рисование квадрата считается одной операцией. Нужно нарисовать 16 квадратов. Сколько операций по рисованию одного квадрата придется выполнить?
Чтобы нарисовать 16 квадратов, потребуется 16 шагов. Как выглядит время выполнения этого алгоритма?
Алгоритм 2
А теперь попробуем иначе. Сложите лист пополам.
На этот раз операцией считается сложение листка. Получается, что одна операция создает сразу два прямоугольника!
Сложите бумагу еще раз, а потом еще и еще.
Разверните листок после четырех сложений - получилась замечательная сетка! Каждое сложение удваивает количество прямоугольников. За 4 операции вы создали 16 прямоугольников!
При каждом складывании количество прямоугольников увеличивается вдвое, так что 16 прямоугольников строятся за 4 шага. Как записать время выполнения этого алгоритма? Напишите время выполнения обоих алгоритмов, прежде чем двигаться дальше.
Ответы: алгоритм 1 выполняется за время О(n) , а алгоритм 2 - за времяO(log n).