Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще - [16]
Джо, конечно, не пасует перед трудностями, но все равно она выиграет, узнав о быстром способе исправить ожерелье. Кстати, точно так же сценаристы правили свои сценарии до изобретения компьютерных программ и текстовых редакторов. Они разрезали лист и прилепляли к нему нужный кусок.
Вот как метод Джон выглядит на графике.
10
Возьми коробку
Людвик продает компьютерные товары в магазине на Миссион-Стрит. Он живет рядом на 14-м этаже сорокаэтажного жилого комплекса, где все помещения общего пользования находятся под видеонаблюдением. Чтобы зарабатывать и покрывать расходы на растущую аренду, Людвик часто подбирает картонные коробки из склада утильсырья в своем доме и использует их для отправки модулей памяти клиентам за границу. Помещение для утиля есть на каждом этаже здания.
Недавно поступил заказ, который нужно выполнить сегодня, а почта закрывается через 15 минут. Людвику нужно срочно найти картонную коробку для посылки.
ЦЕЛЬ: ПРОЙТИ КАК МОЖНО МЕНЬШЕ ЭТАЖЕЙ, ЧТОБЫ НАЙТИ ПУСТУЮ КОРОБКУ.
МЕТОД 1: ПЕРЕХОДИТЬ С ЭТАЖА НА ЭТАЖ В ПОИСКАХ КОРОБКИ.
МЕТОД 2: ПОПРОСИТЬ ВАХТЕРА ПОСМОТРЕТЬ ЗАПИСИ КАМЕР ИЗ ПОМЕЩЕНИЙ УТИЛЬСЫРЬЯ.
Давайте обсудим, как Людвику достичь цели и найти коробку в своем здании.
Метод 1 – это внутренний алгоритм Людвика. Он начинает с верхнего этажа и идет вниз, преодолевая по одному лестничному пролету. Время, которое потребуется для выполнения задания по этому методу, можно разделить пополам, если попросить друга просмотреть четные этажи, а сам Людвик в это время займется нечетными. Но такой алгоритм остается линейно-временным по причинам, которые мы рассмотрим немного позже.
Метод 2 предлагает более удачный алгоритм и позволяет Людвику выяснить, в какой из комнат есть пустые коробки, если он попросит вахтера просмотреть записи камер. Такой алгоритм дает возможность найти пустую коробку в постоянное время, а не в линейное, так как для этого придется посетить только один этаж. Звонок на вахту – постоянная единовременная цена, которую заплатит Людвик, чтобы избежать линейного роста времени.
Возможно, настал момент обсудить способ, с помощью которого мы измеряем скорость роста. В этой книге мы намеренно идем на упрощение ради ясности. Но все равно важно понимать, что есть разные пути для описания скорости роста определенного алгоритма или функции. Один из них известен как «нотация большой теты» (Big-Theta Notation) и характеризует функцию посредством установки верхнего и нижнего предела. Для большого числа элементов он означает, что функция может расти не быстрее, чем линейная функция (n) или логарифмическая функция (log n), и не медленней, чем другие функции,[39] с которыми она связана.
Поэтому мы позволяем себе утверждать: «Бинарный поиск лучше линейного, потому что в худшем случае он занимает логарифмическое время». Как мы видели в главе 2, бинарный поиск (метод логарифмического времени) позволяет нам найти рубашку на вешалке с сотней рубашек за семь шагов, а на гипотетической вешалке с тысячью рубашками – всего за десять шагов или около того. Сравните это с сотней и тысячью шагов соответственно в случае линейного поиска.
Есть два момента, которые предполагает нотация большой теты. Первое: она опускает коэффициенты, объясняя, что их значения становятся непоследовательными по мере увеличения количества предметов.[40] Итак, степень роста n или n/2 будет характеризоваться линейным временем и записываться как θ(n) – читается «большая тета n». Второе: большая тета рассматривает только главный член в функции, предполагая, что он максимально воздействует на результат функции по отношению к другим членам. До сих пор мы называли этот главный член основной операцией. Приводя пример из информатики, профессор Марк Вайсе разъясняет этот вопрос:
В функции 10N>3+N>2+40N+80, для N =1 000 величина функции есть 10 001 040 080, из которых 10 000 000 000 приходится на член 10N>3.
Итак, если метод 1 заставляет Людвика посетить этаж, где он живет, скажем, два раза, мы охарактеризуем время, которое уходит у него на достижение цели в худшем случае как t(n)=n+1, где +1 обозначает этот дополнительный визит, и он записывается в нотации большой теты как θ(n).
Это допущение требует нескольких оговорок.
Например, бывают случаи, в которых второстепенные члены оказывают серьезное влияние на функцию. Вспомните Джо и ее ожерелье из главы 9. Мы сконцентрировались на добавлении бусин и рассматривали первый метод как линейно-временной, а второй – как постоянно-временной и при этом более привлекательный. Мы по умолчанию признавали, что склеивание свободных концов шпагата было простым заданием – но если клею нужно пять минут, чтобы схватиться? Повлияет ли это на выбор Джо? Такие постоянные величины наиболее заметны, когда мы имеем дело с малым числом элементов и должны учитывать их наличие.
Две другие нотации, которые дополняют большую тету и оперируют при тех же условиях, –
