Глава 1. Основные понятия

В этой главе содержатся общие понятия, которые нужно усвоить перед началом серьезного изучения алгоритмов. Начинается она с вопроса «Что такое алгоритмы?». Прежде чем углубиться в детали программирования алгоритмов, стоит потратить немного времени, чтобы разобраться в том, что это такое.

Затем в этой главе дается введение в формальную теорию сложности алгоритмов (complexity theory). При помощи этой теории можно оценить теоретическую вычислительную сложность алгоритмов. Этот подход позволяет сравнивать различные алгоритмы и предсказывать их производительность в разных условиях. В главе приводится несколько примеров применения теории сложности к небольшим задачам.

Некоторые алгоритмы с высокой теоретической производительностью не слишком хорошо работают на практике, поэтому в данной главе также обсуждаются некоторые реальные предпосылки для создания программ. Слишком частое обращение к файлу подкачки или плохое использование ссылок на объекты и коллекции может значительно снизить производительность прекрасного в остальных отношениях приложения.

После знакомства с основными понятиями, вы сможете применять их к алгоритмам, изложенным в последующих главах, а также для анализа собственных программ для оценки их производительности и сможете предугадывать возможные проблемы до того, как они обернутся катастрофой.

Что такое алгоритмы?

Алгоритм – это последовательность инструкций для выполнения какого‑либо задания. Когда вы даете кому‑то инструкции о том, как отремонтировать газонокосилку, испечь торт, вы тем самым задаете алгоритм действий. Конечно, подобные бытовые алгоритмы описываются неформально, например, так:

Проверьте, находится ли машина на стоянке.

Убедитесь, что машина поставлена на ручной тормоз.

Поверните ключ.

И т.д.

==========1

При этом по умолчанию предполагается, что человек, который будет следовать этим инструкциям, сможет самостоятельно выполнить множество мелких операций, например, отпереть и открыть дверь, сесть за руль, пристегнуть ремень, найти ручной тормоз и так далее.

Если же составляется алгоритм для исполнения компьютером, вы не можете полагаться на то, что компьютер поймет что‑либо, если это не описано заранее. Словарь компьютера (язык программирования) очень ограничен и все инструкции для компьютера должны быть сформулированы на этом языке. Поэтому для написания компьютерных алгоритмов используется формализованный стиль.

Интересно попробовать написать формализованный алгоритм для обычных ежедневных задач. Например, алгоритм вождения машины мог бы выглядеть примерно так:

Если дверь закрыта:

Вставить ключ в замок

Повернуть ключ

Если дверь остается закрытой, то:

Повернуть ключ в другую сторону

Повернуть ручку двери

И т.д.

Этот фрагмент «кода» отвечает только за открывание двери; при этом даже не проверяется, какая дверь открывается. Если дверь заело или в машине установлена противоугонная система, то алгоритм открывания двери может быть достаточно сложным.

Формализацией алгоритмов занимаются уже тысячи лет. За 300 лет до н.э. Евклид написал алгоритмы деления углов пополам, проверки равенства треугольников и решения других геометрических задач. Он начал с небольшого словаря аксиом, таких как «параллельные линии не пересекаются» и построил на их основе алгоритмы для решения сложных задач.

Формализованные алгоритмы такого типа хорошо подходят для задач математики, где должна быть доказана истинность какого‑либо положения или возможность выполнения каких‑то действий, скорость же исполнения алгоритма не важна. Для выполнения реальных задач, связанных с выполнением инструкций, например задачи сортировки на компьютере записей о миллионе покупателей, эффективность выполнения становится важной частью постановки задачи.