Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf

Если алгоритм — это последовательность шагов, которые мы можем выполнить самостоятельно, то программирование — это процесс записи этих шагов в формате, понятном компьютеру.

ЧТО ТАКОЕ АЛГОРИТМ? 29
Эти характеристики гарантируют, что алгоритм что-то делает. Он суще- ствует для того, чтобы делать что-то полезное. Бессмысленные алгоритмы тоже существуют, и специалисты в области компьютерных наук могут изо- бретать их для развлечения или по ошибке, но нас с вами интересуют ал- горитмы, имеющие реальное применение. При работе с алгоритмами недо- статочно просто показать возможность выполнить какую-либо задачу. Мы преследуем практические цели, поэтому наши алгоритмы должны выполнять свою работу хорошо.
В этом заключается принципиальное отличие между алгоритмами и ма- тематикой. На заре развития информатики большинство компьютерщиков были математиками, и в компьютерных науках используется много матема- тических концепций, но это не математическая дисциплина. Математик хо- чет доказать какое-то тождество; специалист в области информатики хочет
применить это тождество на практике.
Первая характеристика алгоритма, которую мы привели выше, требует, чтобы количество шагов было конечным. Но это не совсем точная формули- ровка. Конечного числа шагов недостаточно. Мы хотим, чтобы этих шагов было достаточно мало для того, чтобы их можно было выполнить на прак- тике и чтобы наш алгоритм мог завершиться за разумное время. Это озна- чает, что изобретение алгоритма — это лишь полдела; его еще нужно сделать эффективным. Давайте рассмотрим пример, чтобы проиллюстрировать от- личие между знанием чего-то и умением сделать что-то эффективно. Пред- ставьте, что у вас есть такая сетка:
Мы хотим найти кратчайший путь из левого верхнего угла сетки в правый нижний угол, но без посещения одного и того же места дважды. Длина каж- дого пути равна количеству звеньев между точками сетки. Это можно сделать так: найти все возможные пути, измерить длину каждого из них и выбрать са- мый короткий (или любой из них, если их несколько). Всего путей 12, и все они изображены ниже.

30 ГЛАВА 1
Существуют пять путей длиной 4, поэтому мы можем выбрать любой из них.
Но сетки бывают разных размеров: 4 × 4, 5 × 5 и больше. Получается, что наш метод не очень хорошо масштабируется. В сетке размером 4 × 4 суще- ствуют 184 пути из левого верхнего угла в правый нижний; в сетке 5 × 5 таких путей и вовсе 8512. Количество путей быстро растет (на самом деле очень бы- стро), поэтому даже просто подсчитать их бывает затруднительно. Если взять сетку размером 26 × 26, получится 8 402 974 857 881 133 471 007 083 745 436 809 127 296 054 293 775 383 549 824 742 623 937 028 497 898 215 256 929 178 577 083 970 960 121 625 602 506 027 316 549 718 402 106 494 049 978 375 604 247 408 путей. Это число состоит из 151 цифры; оно было вычислено компью- терной программой, реализующей алгоритм. Все верно: мы используем один алгоритм, чтобы разобраться в поведении другого.
Процедура прохождения всех возможных путей с последующим выбором кратчайшего, вне всяких сомнений, является правильной и всегда дает нам самый короткий путь (или один из них, если их несколько), но ее точно нельзя назвать практичной. К тому же она совершенно бесполезна, так как суще- ствуют алгоритмы, которые выдают тот же результат без прохождения всех возможных путей и тем самым экономят нам уйму времени и позволяют ра- ботать с сетками любого размера. Для поиска ответа в сетке 26 × 26 количе- ство необходимых шагов исчисляется сотнями; в следующей главе вы смо- жете сами в этом убедиться.
Вопрос, что такое практичный алгоритм и каким образом один алгоритм оказывается практичнее другого, лежит в основе их практического приме- нения. Читая эту книгу, вы будете сталкиваться с тем, что для решения од- ной и той же проблемы существует несколько алгоритмов, и выбирать сле- дует тот, который лучше всего подходит в каждой конкретной ситуации. Как это бывает с любыми инструментами, некоторые алгоритмы оказываются более подходящими для определенных сценариев использования, чем другие.
Но, в отличие от многих других инструментов, алгоритмы можно оценивать четко определенным способом.

ЧТО ТАКОЕ АЛГОРИТМ? 31
Аппаратное обеспечение постоянно развивается, и нам зачастую недо- статочно знать, как программа, реализующая алгоритм, работает на отдель- ном компьютере. Наш компьютер может быть быстрее или медленнее того, на котором анализировался алгоритм, и спустя несколько лет замеры произ- водительности на устаревшем устройстве будут представлять разве что исто- рическую ценность. Нам нужен метод оценки эффективности алгоритма в от- рыве от оборудования.
Однако то, как мы анализируем алгоритм, должно отражать масштаб за- дачи, которую мы пытаемся решить. Нас мало интересует, сколько времени займет сортировка 10 элементов; в крайнем случае это можно сделать даже вручную. А вот то, как долго будет сортироваться миллион элементов, уже интереснее. Мы хотим оценить поведение алгоритма в контексте нетриви- альных задач.
Для этого нам нужен способ определения масштабов задач, которые ре- шает алгоритм. Но подходящая величина зависит от конкретной задачи. Если мы хотим отсортировать на нашем компьютере ряд элементов, нужной нам величиной будет их количество (а не, скажем, их размер или то, как они структурированы). Если нам нужно умножить два числа, подходящей вели- чиной будет количество цифр в обоих числах (это имеет смысл и для нас, лю- дей: сложность умножения в столбик зависит от того, из скольких разрядов состоит каждое число). Анализируя задачу и подбирая алгоритм для ее реше- ния, мы всегда учитываем ее масштаб.
Масштаб каждой конкретной задачи можно оценить по-разному, но в лю- бом случае мы обозначаем его целым числом, n. Если вернуться к предыду- щим примерам, n — это либо количество элементов для сортировки, либо ко- личество разрядов в числах, которые нужно умножить. И только после этого можно говорить о производительности алгоритмов, решающих задачи мас- штаба n.
Время, нужное алгоритму, зависит от его вычислительной сложности.
Вычислительная сложность алгоритма — это количество ресурсов, которое требуется для его работы. Ресурсы бывают двух основных видов: время, не- обходимое для выполнения, и объем компьютерной памяти.
Пока сосредоточимся на времени. Компьютеры могут иметь разную производительность, поэтому время выполнения алгоритма на конкрет- ном оборудовании может служить лишь косвенным показателем того, что следует ожидать. Нам нужно что-то более универсальное. Скорость работы компьютера определяется тем, как долго он выполняет базовые операции.
Чтобы не углубляться в технические детали, мы будем говорить о количестве

32 ГЛАВА 1
операций, необходимых для работы алгоритма, а не о том, насколько быстро они выполняются на конкретном компьютере.
Однако следует отметить, что мы позволим себе небольшую вольность в использовании терминологии и будем считать слова «операции» и «время» синонимами. Строго говоря, эти понятия нужно разделять, отмечая, что ал- горитму требуется «x операций», но вместе с этим мы будем указывать, что алгоритму нужно «время x»; это время, которое требуется алгоритму для вы- полнения x операций на любом компьютере. И хотя на самом деле время бу- дет варьироваться в зависимости от программного обеспечения, это неважно, если мы хотим сравнить два алгоритма, которым нужно «время x» и «время y» на одном и том же компьютере, каким бы он ни был.
Теперь вернемся к масштабу задач, которые решает алгоритм. Поскольку тривиальные задачи нас не интересуют, мы не станем останавливаться на мелком масштабе. Мы не можем назвать конкретные цифры, но отметим, что масштаб должен быть значительным.
Существует определение сложности, полезность которого доказана на практике. У него есть название и условное обозначение. Мы записываем его как O(ڄ) и называем большое. Вместо точки в скобках указывается выра- жение. Эта запись означает, что алгоритму нужно время, не больше, чем мно- житель этого выражения. Давайте посмотрим, что это означает.
• Если вам нужно найти элемент в последовательности длиной n, которая никоим образом не упорядочена, сложность этой задачи будет
O(n). То есть, если у нас есть n элементов, время, необходимое, чтобы найти один из них, будет не больше, чем некое число, умноженное на n.
• Если вы хотите умножить в столбик два числа, состоящих из n разрядов, сложность этой операции будет O(n
2
). То есть время, необходимое на ее выполнение, будет не больше, чем некое число, умноженное на квадрат n.
Если сложность нашего алгоритма равна O(n), то при вводе размером
10 000 следует ожидать, что на работу ему потребуется количество шагов, кратное десяти тысячам. Если сложность алгоритма O(n
2
), то для ввода ана- логичного размера потребуется около ста миллионов шагов. Для многих за- дач этот масштаб не является большим. Компьютеры постоянно сортируют десятки тысяч элементов. Но вы можете видеть, что количество шагов, пред- ставленное сложностью алгоритма, может быть довольно крупным.

ЧТО ТАКОЕ АЛГОРИТМ? 33
Давайте рассмотрим несколько примеров, чтобы вы могли получить пред- ставление о масштабах некоторых показателей, с которыми вы будете стал- киваться. Возьмем число 100 миллиардов, или 10 11
; оно состоит из 11 нолей.
Если взять 100 миллиардов гамбургеров и разложить их один за другим, этой длины хватит, чтобы обогнуть земной шар 216 раз или, например, дойти до Луны и обратно.
Миллиард эквивалентен приставке гига-, по крайней мере в мире ком- пьютеров. За миллиардом (гига-) идет триллион (тера-); это 1000 милли- ардов, или 10 12
. Если вы начнете произносить по одному числу в секунду, то, чтобы досчитать до триллиона, вам понадобится 31 000 лет. Умножим это еще на 1000 и получим квадриллион, 10 15
или пета-; если верить биологу
Э. О. Уилсону, общее число муравьев на нашей планете находится в преде- лах от 1 до 10 квадриллионов. Иными словами, в природе существует от 1 до 10 «петамуравьев».
Вслед за квадриллионом идет квинтиллион, или экса-; это 10 18
— при- мерно столько, сколько песчинок на десяти больших пляжах. Например, на 10 Копакабанах умещается одна «эксапесчинка». Идем дальше. 10 21
— это один секстиллион, или зетта-. В наблюдаемой вселенной существует одна
«зеттазвезда». Последний общепринятый префикс, йотта-, обозначает 10 24
, или один септиллион. Но всегда можно взять большее число. Например, 10 100
называется гугол (англ. googol) — вы, наверное, слышали о компании с похо- жим названием, в котором специально допущена ошибка. Если возвести 10 в степень гугол,
10 10 100
, получится гуголплекс.
Эти аналогии помогут нам оценить относительные достоинства конкрет- ных алгоритмов, которые мы будем рассматривать на страницах этой книги.
Теоретически алгоритмы могут иметь любую сложность, но те из них, с кото- рыми мы обычно сталкиваемся, можно разделить на несколько разных групп.
Категории сложности алгоритмов
Самыми быстрыми являются алгоритмы, работающие не дольше фиксиро- ванного времени, независимо от ввода. Мы обозначаем эту сложность как
O(1); например, алгоритм, который проверяет, является ли последняя цифра числа четной, не зависит от того, насколько большое это число, и всегда бу- дет выполняться за одно и то же время. 1 в O(1) означает, что максимальное количество шагов, необходимое для выполнения алгоритма, кратно 1, то есть оно всегда одно и то же.

34 ГЛАВА 1
Прежде чем мы познакомимся со следующей категорией сложности, сле- дует обсудить, как именно вещи могут расти и уменьшаться. Многократное сложение эквивалентно умножению. Многократное умножение — это воз- ведение в степень (экспоненциальный рост). Мы только видели, насколько большими могут становиться числа, если они растут экспоненциально (как в случае с 10 12
). Возведение в степень может дать на удивление большую ве- личину — это явление называется экспоненциальным ростом.
Проиллюстрируем его с помощью (вероятно, недостоверной) легенды об изобретении шахмат. Правитель страны, где были придуманы шахматы, спро- сил их создателя о том, что он хотел бы получить в качестве подарка (в таких ис- ториях это всегда «он»). Тот ответил, что хочет одно зерно риса на первой клетке шахматной доски, два зерна на второй, четыре на третьей и т. д. Правитель поду- мал, что легко отделался, и приказал исполнить желание. Но все оказалось не так просто. Эта последовательность растет вместе со степенью двойки: 2 0
= 1 в пер- вой клетке, 2 1
= 2 во второй, 2 2
= 4 в третьей; таким образом, в последней клетке количество зерен равно 2 63
— это недостижимая величина, эквивалентная
9 223 372 036 854 775 808, или примерно 9 квинтиллионам.
Экспоненциальный рост может также объяснить, почему так сложно сло- жить кусочек бумаги много раз подряд. При каждом сгибании количество слоев бумаги удваивается. После десяти сгибаний получается 2 10
= 1024 слоя.
Если бумага имеет толщину 0,1 миллиметра, у вас получится комок толщи- ной 10 сантиметров. Сложить такой ком вдвое может быть физически невоз- можно, даже если приложить грубую силу, так как для этого его длина должна быть больше его толщины.
Именно благодаря экспоненциальному росту компьютеры становятся все более мощными год от года. Согласно закону Мура, количество транзисто- ров на интегральной схеме удваивается каждые два года. Этот закон назван в честь Гордона Мура, основателя Fairchild Semiconductor и Intel. Он сделал это наблюдение в 1965 году, и оно оказалось провидческим. В 1971 году в про- цессоре Intel 4004 насчитывалось около 2000 транзисторов, а в 2017-м этот показатель достиг 19 миллиардов (в 32-ядерном процессоре AMD Epyc).
С ростом мы разобрались, теперь давайте поговорим о его противополож- ности. Если у вас есть множитель какого-то числа, для получения исходного значения нужно выполнить деление. Но, если у вас есть степень чего-то, a
n
, как обернуть эту операцию вспять? Противоположностью возведения в сте- пень является логарифм.
Иногда говорят, что логарифмы находятся на границе между математи- кой для всех и математикой для посвященных; даже само название звучит

ЧТО ТАКОЕ АЛГОРИТМ? 35
непонятно. Если эта операция кажется вам запутанной, помните, что лога- рифм числа — это противоположность возведения числа в степень. Возведе- ние в степень предполагает многократное умножение, а логарифм заключа- ется в многократном делении.
Логарифм отвечает на вопрос: «в какую степень возвести число, чтобы получить нужное значение?» Число, которое мы возводим, называется осно-
ванием логарифма. Поэтому, если спросить: «в какую степень нужно возве- сти 10, чтобы получить 1000?», ответом будет 3, поскольку 10 3
= 1000. Ко- нечно, мы можем взять для возведения в степень другое число, то есть другое основание. Логарифм записывается как log
a
x и отвечает на вопрос: «в какую степень нужно возвести a, чтобы получить x?». Если a = 10, подстрочное зна- чение опускается ввиду распространенности логарифмов по основанию 10, поэтому вместо log
10
x мы пишем просто logx.
Существуют два других распространенных основания. Если основание равно математической константе e, мы пишем lnx. Эта константа называется
числом Эйлера и равна приблизительно 2,71828. В естественных науках lnx встречается повсеместно, поэтому его называют натуральным логарифмом.
Другое распространенное основание — 2, и вместо log
2
x мы пишем lgx. Это основание в основном применяется в информатике и алгоритмах, и в других областях его почти никогда не используют. Мы уже встречали его в примере со сгибанием кусочка бумаги: если результат состоит из 1024 слоев, он был сложен lg1024 = lg2 10
= 10 раз. В истории с шахматами количество зерен риса зависит от количества удваиваний: lg2 63
= 63.
lgx часто встречается в алгоритмах, потому что этот логарифм всегда ис- пользуют при разбиении одной большой задачи на две мелких; этот принцип называется разделяй и властвуй, и он работает точно так же, как сгибание ли- ста бумаги вдвое. Самый эффективный способ поиска по набору отсортиро- ванных элементов имеет сложность O(lgn). Поразительно, не так ли? Из этого следует, что для поиска по миллиарду упорядоченных элементов достаточно всего lg10 9
≈ 30 шагов.
Вторым лучшим выбором после алгоритмов, выполняемых за фиксиро- ванное время, являются алгоритмы с логарифмической сложностью. Дальше идут алгоритмы, которые выполняются за O(n); их называют алгоритмами
линейного времени, поскольку время их выполнения растет пропорцио- нально n, то есть они растут в качестве множителей n. Мы уже видели, что время, необходимое для поиска по списку неупорядоченных элементов, про- порционально количеству этих элементов, O(n). Обратите внимание на то, как повышается сложность по сравнению с упорядоченным списком; то, как