Как найти свойства алгоритма

Алгоритм. Свойства алгоритмов.
Блок-схемы. Алгоритмические языки

Код ОГЭ: 1.3.1. Алгоритм, свойства алгоритмов, способы записи алгоритмов.
Блок-схемы. Представление о программировании

---

---

Понятие алгоритма является одним из основных понятий вычислительной математики и информатики.

■  Алгоритм
— строго определенная последовательность действий для некоторого исполнителя, приводящая к поставленной цели или заданному результату за конечное число шагов.

Любой алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей. Исполнитель — субъект, способный исполнять некоторый набор команд. Совокупность команд, которые исполнитель может понять и выполнить, называется системой команд исполнителя.

Для выполнения алгоритма исполнителю недостаточно только самого алгоритма. Выполнить алгоритм — значит применить его к решению конкретной задачи, т. е. выполнить запланированные действия по отношению к определенным входным данным. Поэтому исполнителю необходимо иметь исходные (входные) данные — те, что задаются до начала алгоритма.

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

Свойства алгоритмов

Алгоритм должен обладать определенными свойствами. Наиболее важные свойства алгоритмов:

• Дискретность. Процесс решения задачи должен быть разбит на последовательность отдельных шагов — простых действий, которые выполняются одно за другим в определенном порядке. Каждый шаг называется командой (инструкцией). Только после завершения одной команды можно перейти к выполнению следующей.
• Конечность. Исполнение алгоритма должно завершиться за конечное число шагов; при этом должен быть получен результат.
• Понятность. Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм должен содержать только те команды, которые входят в систему команд его исполнителя.
• Определенность (детерминированность). Каждая команда алгоритма должна быть точно и однозначно определена. Также однозначно должно быть определено, какая команда будет выполняться на следующем шаге. Результат выполнения команды не должен зависеть ни от какой дополнительной информации. У исполнителя не должно быть возможности принять самостоятельное решение (т. е. он исполняет алгоритм формально, не вникая в его смысл). Благодаря этому любой исполнитель, имеющий необходимую систему команд, получит один и тот же результат на основании одних и тех же исходных данных, выполняя одну и ту же цепочку команд.
• Массовость. Алгоритм предназначен для решения не одной конкретной задачи, а целого класса задач, который определяется диапазоном возможных входных данных.

Способы представления алгоритмов:

• словесная запись (на естественном языке). Алгоритм записывается в виде последовательности пронумерованных команд, каждая из которых представляет собой произвольное изложение действия;
• блок–схема (графическое изображение). Алгоритм представляется с помощью специальных значков (геометрических фигур) — блоков;
• формальные алгоритмические языки. Для записи алгоритма используется специальная система обозначений (искусственный язык, называемый алгоритмическим);
• псевдокод. Запись алгоритма на основе синтеза алгоритмического и обычного языков. Базовые структуры алгоритма записываются строго с помощью элементов некоторого базового алгоритмического языка.

Словесная запись алгоритма

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

■  Пример 1. Записать в словесной форме правило деления обыкновенных дробей.

Решение.
Шаг 1. Числитель первой дроби умножить на знаменатель второй дроби.
Шаг 2. Знаменатель первой дроби умножить на числитель второй дроби.
Шаг 3. Записать дробь, числителем которой являет результат выполнения шага 1, знаменателем — результат выполнения шага 2.

Описанный алгоритм применим к любым двум обыкновенным дробям. В результате его выполнения будут получены выходные данные — результат деления двух дробей (исходных данных).

Формальные исполнители алгоритма

Формальный исполнитель — это исполнитель, который выполняет все команды алгоритма строго в предписанной последовательности, не вникая в его смысл, не внося ничего в алгоритм и ничего не отбрасывая. Обычно под формальным исполнителем понимают технические устройства, автоматы, роботов и т. п. Компьютер можно считать формальным исполнителем.

Программы на языке произвольного формального исполнителя могут состоять только из элементарных команд, которые входят в его систему (которые исполнитель «понимает»).

Исполнитель может иметь свою среду (например, систему координат, клеточное поле и др.). Среда исполнителя — это совокупность объектов, над которыми он может выполнять определенные действия (команды), и связей между этими объектами. Алгоритмы в этой среде выполняются исполнителем по шагам.

■ Пример 2. Исполнитель Крот имеет следующую систему команд:

1. вперед k — продвижение на указанное число шагов вперед;
2. поворот s — поворот на s градусов по часовой стрелке;
3. повторить m [команда1 … командаN] — повторить m раз серию указанных команд.

Какой след оставит за собой исполнитель после выполнения следующей последовательности команд?

Повторить 5 [вперед 10 поворот 72]

Решение. Команда вынуждает исполнителя 5 раз повторить набор действий: пройти 10 шагов вперед и повернуть на 72° по часовой стрелке. Так как поворот происходит на один и тот же угол, то за весь путь исполнитель повернет на 5 х 72° = 360°. Поскольку все отрезки пути одинаковой длины и сумма внешних углов любого многоугольника составляет 360°, то в результате будет оставлен след в форме правильного пятиугольника со стороной в 10 шагов исполнителя.

Заметим, что если увеличить количество повторов серии команд, то исполнитель будет повторно передвигаться по тем же отрезкам (произойдет повторное движение по тому же пятиугольнику).

■ Пример 3.  В системе команд предыдущего исполнителя Крот сформировать алгоритм вычерчивания пятиступенчатой лестницы (длина ступеньки — 10 шагов исполнителя).

Решение. За каждый шаг цикла должно происходить 4 действия: движение вперед на 10 шагов исполнителя, поворот на 90° по часовой стрелке, еще 10 шагов вперед и поворот на 90° против часовой стрелки (= 270° по часовой). В результате за один шаг цикла формируется ломаная из двух отрезков длиной 10 под прямым углом. За пять таких шагов сформируется 5–ступенчатая лестница (ломаная будет содержать 10 звеньев).

Повторить 5 [вперед 10 поворот 90 вперед 10 поворот 270]

Блок–схема

Блок–схема — наглядный способ представления алгоритма. Блок–схема отображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Определенному типу действия соответствует определенная геометрическая фигура блока. Линии, соединяющие блоки, определяют очередность выполнения действий. По умолчанию блоки соединяются сверху вниз и слева направо. Если последовательность выполнения блоков должна быть иной, используются направленные линии (стрелки).

Основные элементы блок–схемы алгоритма:

Общий вид блок–схемы алгоритма:

■ Пример 4.  Алгоритм целочисленных преобразований представлен в виде фрагмента блок–схемы. Знаком := в нем обозначен оператор присваивания некоторого значения указанной переменной. Запись X := 1 означает, что переменная Х принимает значение 1.

Определить результат работы алгоритма для исходных данных Х = 7, Y = 12.

Решение.

1. Блок ввода данных определит исходные значения переменных Х и Y (7 и 12 соответственно).
2. В первом условном блоке осуществляется сравнение значений Х и Y. Поскольку условие, записанное в блоке, неверно (7 < 12), происходит переход по линии «нет».
3. Во втором условном блоке выполняется второе сравнение, которое для исходных данных оказывается верным. Происходит переход по линии «да».
4. Вычисляется результат выполнения алгоритма: X := 0, Y := 1.

Ответ: X := 0, Y := 1.

Алгоритмические языки

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

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

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

Псевдокод

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

Служебные слова учебного алгоритмического языка:

Стандартная структура алгоритма

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

Общий вид записи алгоритма на учебном алгоритмическом языке:

В начале заголовка записывается служебное слово алг, после чего указывается имя алгоритма. Описание переменных, являющихся аргументами алгоритма и его результатами, приводится после названия в круглых скобках.

В следующих строках конкретизируют, какие именно переменные являются аргументами алгоритма (входными данными), а какие — его результатами (выходными данными). Для этого после служебного слова арг приводится список имен переменных–аргументов; в следующей строке после служебного слова рез приводится список имен переменных–результатов.

Между служебными словами нач и кон размещается тело алгоритма — конечная последовательность команд, выполнение которых предписывает алгоритм. Команды алгоритма записывают одну за одной в отдельных строках. В случае необходимости можно записать две или более команд в одной строке, тогда соседние команды разделяют точкой с запятой. Если в алгоритме применяются промежуточные переменные, их описание приводят в начальной строке тела алгоритма рядом со словом нач.

Примеры заголовков алгоритмов:

В первом примере алгоритм имеет название Объем_шара, один вещественный аргумент Радиус и один вещественный результат Объем. Во втором примере алгоритм под названием Choice имеет три аргумента — целые M и N и логический b, а также два результата — вещественные Var1 и Var2.

Пример алгоритма вычисления гипотенузы прямоугольного треугольника:

На вход алгоритму даются два вещественных аргумента a и b (величины катетов), результатом является вещественная переменная с (гипотенуза). Для ее расчета используется функция вычисления квадратного корня sqrt.

Описание величин и действия над ними

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

При представлении алгоритма решения в виде блок–схемы выбранные обозначения величин приводятся отдельно от блок–схемы (как объяснение к ней). Если алгоритм представлен на языке программирования, то характеристика обрабатываемых величин включается в программу. Учебный алгоритмический язык также предусматривает описание величин, используемых в алгоритме.

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

В алгоритмическом языке не существует специальных правил именования переменных. Однако их названия не должны совпадать со служебными словами алгоритмического языка. Во многих языках программирования для имен можно использовать только латинские буквы, цифры, знак подчеркивания. Имена обязательно должны начинаться с буквы, при этом строчные и прописные буквы в именах не различаются. В одном алгоритме не могут существовать разные объекты с одинаковыми именами. Все имена являются уникальными. Имена переменных и констант стараются выбирать так, чтобы они напоминали их смысл. Например, имена переменных и констант: S, p12, result, итог.

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

Величина — переменная, с которой связывается определенное множество значений. Этой величине присваивается имя (в языках программирования его называют идентификатор).

Значение — то, чему равна переменная в конкретный момент. Значение переменной можно задать двумя способами: присваиванием и с помощью процедуры ввода.

Тип переменной определяет диапазон всех значений, которые может принимать данная переменная, и допустимые для нее операции. Существует несколько предопределенных типов переменных. К стандартным типам относятся числовые, литерные и логические типы.

Числовой тип предназначен для обработки числовых данных. Различают целый и вещественный числовые типы. Целый тип в учебном алгоритмическом языке обозначается служебным словом цел, к нему относятся целые числа некоторого определенного диапазона. Они не могут иметь дробной части, даже нулевой. Число 123,0 является не целым, а вещественным числом. Вещественные величины относятся к вещественному типу данных и обозначаются в учебном алгоритмическом языке служебным словом вещ. Такие величины могут отображаться двумя способами: в форме с фиксированной запятой (например, 0,0511 или –712,3456) и с плавающей запятой (те же примеры: 5,11*10^-2 и –7,123456*10²).

Над числовыми данными можно выполнять арифметические операции и операции сравнения.

Над целыми числами можно также выполнять две операции целочисленного деления div и mod. Операция div обозначает деление с точностью до целых чисел (остаток от деления игнорируется). Операция mod позволяет узнать остаток при делении с точностью до целых чисел. Например, результатом операции 100 div 9 будет число 11, а результатом 100 mod 9 — число 1.

Литерный тип представляет собой символы и строки, он дает возможность работать с текстом. Литерные величины — это произвольные последовательности символов. Эти последовательности заключаются в двойные кавычки: «результат», «sum_price». В качестве символов могут быть использованы буквы, цифры, знаки препинания, пробел и некоторые другие специальные знаки (возможными символами могут быть символы таблицы ASCII). В учебном алгоритмическом языке литерные величины обозначаются лит.

Над литерными величинами возможны операции сравнения и слияния. Сравнение литерных величин производится в соответствии с их упорядочением: «a» < «b», «b» < «с» и т. д. Слияние (конкатенация) литерных величин приводит к образованию новой величины: «пол» + «е» образует «поле».

Логический тип определяет логические переменные, которые могут принимать только два значения — истина (True) или ложь (False). Над логическими величинами можно выполнять все стандартные логические операции.

Команды учебного алгоритмического языка

Учебный алгоритмический язык использует следующие команды для реализации алгоритма:

ОПЕРАЦИЯ ПРИСВАИВАНИЯ

Ко всем типам величин может быть применена операция присваивания, которая обозначается знаком «:=» и служит для вычисления выражения, стоящего справа, и присваивания его значения переменной, указанной слева. Например, если переменная H имела значение 12, а переменная М — значение 3, то после выполнения оператора присваивания H := М + 10 значение переменной H изменится и станет равным 13.

Вычисления в операторе присваивания выполняются справа налево: сначала необходимо вычислить значение выражения справа от знака присваивания. Поэтому допустимы конструкции вида H := Н + 10. В этом случае сначала будет вычислено выражение в правой части (12 + 10), а его результат будет присвоен в качестве нового значения переменной Н (значение 22).

Для оператора присваивания обязательно должны быть определены значения всех переменных в его правой части. Кроме того, типы данных в левой и правой части должны соответствовать друг другу.

ВВОД И ВЫВОД ДАННЫХ

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

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

Описание алгоритма средствами псевдокода может вовсе не предусматривать команды ввода или вывода данных. В заголовке алгоритма указывается, какие данные являются аргументами, какие — результатами работы алгоритма. Считается, что аргументы будут предоставлены до выполнения алгоритма, результаты будут выведены после его выполнения, и описывается лишь процесс превращения аргументов в результаты.

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

Список ввода может содержать только имена переменных. После выполнения команды ввод алгоритм получит значения перечисленных в списке переменных.

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

Если при выполнении алгоритма ввести значения 20 и 10, то переменная v примет значение 20, а переменная t — значение 10. По окончании работы алгоритма будет выведен результат:

Путь 200 м

Тот же результат был бы получен, если бы изменить строку вывода на

вывод «Путь «, v * t, » м»

---

Конспект по информатике «Алгоритм. Свойства алгоритмов. Блок-схемы. Алгоритмические языки».

Вернуться к Списку конспектов по информатике.

Кто же ты такой, алгоритм?

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

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

В университетах дела обстоят получше, однако автору этих строк на курсе по математической логике и теории алгоритмов пришлось столкнуться все с тем же винегретом из определения алгоритма и его свойств. Разберемся, что тут не так.

Бесконечность не предел

Но перед этим немного вспомним математику. Из школьного курса математики мы знаем, что чисел существует бесконечно много — какое бы большое число мы не взяли, всегда можно прибавить единицу и получить число еще большее. Обычно в школе этим и ограничиваются. В университете на курсе высшей математики нам расскажут, что бесконечности на самом деле бывают разные: множества, элементы которого можно пронумеровать натуральными числами считаются счётно-бесконечными. К таким множествам относят сами натуральные числа (числу 1 мы дадим номер один, числу 2 номер два и т.д.), целые числа — натуральные плюс ноль и отрицательные целые числа (первый номер отдаем нулю, второй — числу 1, третий — числу -1, то есть каждой положительное число k получает номер 2k, а каждое отрицательное число -m получает номер 2m + 1). К счетно-бесконечным множествам относят четные, нечетные и даже рациональные числа (числа представимые в виде несократимой дроби m/n, где m — целое, n — натуральное). Получается, что натуральных чисел ровно столько же, сколько четных, и, в то же время, ровно столько же, сколько целых. «Количество» (мощность) множества натуральных чисел обозначается символом ℵ₀ (алеф-ноль).

Такой же трюк с нумерацией не пройдет для бесконечных непериодических дробей (иррациональных чисел). Допустим такое множество счетное, то есть элементы этого множества можно пронумеровать натуральными числами. Тогда рассмотрим бесконечную десятичную дробь с нулевой целой частью, у которой первая цифра после запятой не равняется цифре на той же позиции у дроби с номером 1, вторая цифра не равняется цифре на второй позиции у дроби с номером 2 и т.д. Тогда полученная дробь будет заведомо отличаться от всех дробей хотя бы одной цифрой. Получается для нее не нашлось номера в нашей бесконечной нумерации! Примененная схема доказательства называется канторовским диагональным методом в честь придумавшего ее математика Георга Кантора.

Про бесконечные дроби

Не стоит делать ошибку, записывая в иррациональные числа все бесконечные дроби. Иррациональными являются только те числа, которые нельзя представить в виде несократимой дроби вида m/n. В десятичной системе счисления дроби 1/3 и 2/7 тоже окажутся бесконечными, однако их «бесконечность« обусловлена выбранной системой счисления. В системе счисления по основанию 21 эти дроби будут иметь конечное представление, а вот, например, дробь 1/2 окажется бесконечной (периодической).

Говорят, что множество бесконечных десятичных дробей имеет мощность континуум, которая обозначается символом ℵ₁ (алеф-один).  В дальнейшем нам понадобится следующее множество. Рассмотрим некоторый алфавит (конечное множество символов). Теперь представим множество всех конечных цепочек символов алфавита A*. Коль скоро алфавит конечен, и каждая цепочка конечна, то множество таких цепочек счетно (их можно пронумеровать натуральными числами). 

На сколько велика бесконечность?

Допустим в наш алфавит вошли все придуманные на земле символы: русский алфавит, японские иероглифы, шумерская клинопись и т.д. Тогда в наше множество войдут все написанные когда-либо книги, все книги, которые будут написаны и все книги, которые никто не стал бы писать (например, хаотичные последовательности символов). Кроме того, представим книгу, толщиной в Солнечную систему и диагональю листа равной диаметру Млечного Пути, набранную 12-м шрифтом. В наше придуманное множество войдут все такие книги, отличающиеся хотя бы одним символов, и не только они, ведь вселенная бесконечна! Кто мешает представить себе книгу, размером в миллиарды световых лет? А все такие книги? Уже на этом этапе воображение может давать сбои, а ведь наше множество всего лишь счетное. Чтобы дополнить множество до континуума, нужно рассмотреть бесконечную книгу, по сравнению с которой, предыдущие книги — детские игрушки. Но и одной бесконечной книги нам не хватит, нужно рассмотреть все бесконечные книги.

Конструктивно оперировать континуальными бесконечностями невозможно. Даже работая со счетными множествами, мы не рассматриваем сами множества, а только говорим, что какой бы не был элемент N, всегда найдется элемент N+1. Если мы ставим себе прикладную задачу, появление в наших рассуждениях континуальной бесконечности должно служить нам «тревожной лампочкой»: осторожно, выход за пределы конструктивного. 

Алгоритмы и вычислимость 

Суть работы компьютера заключается в проведении некоторого вычисления — преобразования одной порции информации в другую порцию. Причем результатом работы не обязательно должно быть число, главное, чтобы информация была представлена в некоторой объективной форме. Обычно под такой формой имеют в виду конечные цепочки символов некоторого алфавита. Получается, компьютерное вычисление есть некоторая функция в сугубо математическом смысле, с областью определения и значений в рассмотренном выше множестве A*. Именно тут возникают определенные проблемы. Если мы можем вычислить функцию, то можем записать промежуточные вычисления в виде текста. Более того, в виде тексте можно описать вообще правила вычисления. Мы знаем, что множество всех текстов счетное. Однако выясняется, что множество всех функций над натуральными числами имеет мощность континуум. Если мы пронумеруем все тексты, то получается функций вида A* -> A* тоже континуум. Получается, что некоторые функции вычислимы, а некоторые нет. 

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

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

Частично-рекурсивные функции и тезис Черча

Все началось с того, что математик Давид Гильберт в 1900 году предложил список нерешенных на тот момент математических проблем. Позже выяснилось, что десятая проблема (проблема решения произвольного диофантового уравнения) оказалось неразрешимой, но для доказательства этого факта пришлось составить целую новую математическую теорию. Вопросами того, какие задачи можно конструктивно решить, и что такое конструктивное решение, занялись математики Курт Гедель, Стивен Клини, Алонсо Черч и Алан Тьюринг. 

Как выяснилось выше, континуальные бесконечности не всегда подходят под конструктивные рассуждения, поэтому Гедель и Клини предложили рассматривать только функции натурального аргумента (при необходимости любые функции над счетными множествами можно привести к «натуральным функция» путем замены элементов множеств их номерами). Изучая вычислимость таких функций, Гедель, Клини, Аккерман и другие математики пришли к так называемому классу частично-рекурсивных функций. В качестве определения этого класса рассматривается набор базовых, очень простых функций (константа, увеличение на единицу и проекция, которая сопоставляет функции многих аргументов один из ее аргументов) и операторов, позволяющих из функций строить новые функции (операторы композиции, примитивной рекурсии и минимизации). Слово «частичные» показывает, что эти функции определены лишь на некоторых числах. На остальных они не могут быть вычислены. Попытки расширить класс частично-рекурсивных функций ни к чему не привели, так как введение новых операций приводило к тому, что получалось множество функций, совпадающее с классом частично-рекурсивных. В дальнейшем Алонсо Черч отказался от попыток расширения этого класса, заявив, что, видимо:

Частично-рекурсивные функции соответствуют вычислимым функциям в любом разумном понимании вычислимости.

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

Формальная теория алгоритмов во многом построена аналогично теории вычислимости. Считается, что алгоритм есть некое конструктивное преобразование входного слова (цепочки символов некоторого алфавита) в некоторое выходное слово. Опять же, здесь мы имеем с функциями вида A*->A*. Конечно, предложенное описание не подходит под определение алгоритма, так как неясно, что же такое «конструктивное преобразование». Хоть понятия алгоритма и вычислимой функции близки, не стоит их смешивать. Для одного и того же алгоритма может быть предъявлено сколько угодно его записей на каком-нибудь формальном языке, но соответствующая вычислимая функция всегда одна. Один из основателей формальной теории алгоритмов, Алан Тьюринг, предложил формальную модель автомата, известного как машина Тьюринга. Тезис Тьюринга гласит:

Каково бы не было разумное понимание алгоритма, любой алгоритм, соответствующий такому пониманию, может быть реализован на машине Тьюринга.

Любые попытки построить более мощные автомат заканчивались неудачей: для каждого такого автомата (машина Поста, нормальные алгоритмы Маркова, автоматы с регистрами и несколькими лентами) удавалось построить аналогичную машину Тьюринга. Некоторые ученые объединяют тезис Черча и тезис Тьюринга в тезис Черча-Тьюринга, так как они весьма близки по духу. 

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

Свойства алгоритмов

Мы выяснили, почему у алгоритма не может быть конкретного определения. Однако можно определить свойства, которыми должен обладать каждый алгоритм. К сожалению, в литературе часто смешивают обязательные и необязательный свойств. Разберемся подробнее.

Обязательные свойства

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

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

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

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

Необязательные свойства

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

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

Про зависающие программы

Программы, которые не могут зациклиться, на самом деле входят в класс примитивно-рекурсивных — подмножество частично-рекурсивного класса. Отличает их отсутствия оператора минимизации. Он то и вносит пикантности. Если вы используете «неарифметический цикл» while или рекурсию, для которых нельзя заранее определить, сколько раз они выполняться, то ваша программа сразу переходит из класса примитивно-рекурсивных в класс частично-рекурсивных.

Теперь перейдем к пресловутой последовательности шагов. Дело в том, что алгоритм может быть представлен в любой из имеющихся формальных систем (частично-рекурсивные функции, машина Тьюринга, лямбда-исчисление и т.д.). Воплощение алгоритма в виде компьютерной программы далеко не всегда будет описанием последовательности шагов. Здесь все зависит от парадигмы программирования. В императивной парадигме программисты действительно оперируют последовательностью действий. Однако существуют и другие парадигмы, такие как функциональная (привет Haskell программистам), где нету никаких действий, а лишь функции в сугубо математическом смысле, или чистая объектно-ориентированная, которая основана не на «последовательности действий», а на обмене сообщениями между абстрактными объектами. 

Заключение 

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

Материал данной статьи во многом опирается на 1-ый том «Программирование: введение в профессию» А. В. Столярова. Тем, кто хочет подробнее изучить вопросы, связанные с алгоритмами и теорией вычислимости, кроме этой книги, советую Босс В «От Диофанта до Тьюринга» и трехтомник А. Шеня по математической логике и теории алгоритмов.

---

Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.

 Содержание

Алгоритм. Понятие алгоритма.        2

Свойства алгоритма.        2

Система команд исполнителя        3

Формальное исполнение алгоритма        3

Способы записи алгоритмов.        3

1. Естественный язык (словесная запись алгоритма)        3

2. Язык блок-схем (графическая запись алгоритмов).        4

3. Алгоритмический язык (псевдокоды).        5

4. Формальный язык (язык программирования).        5

Структуры алгоритмов.        5

Структура следование        6

Структура ветвление (развилка).        6

Структура повторение (цикл)        7

Контрольные вопросы.        10

 

Алгоритм. Понятие алгоритма.

Алгоритм — понятное и точное предписание (указание) исполнителю совершить определенную последовательность действий для достижения указанной цели или решения поставленной задачи.

Алгоритм — список команд, набор инструкций, выполнив которые можно получить определенный результат.

Сборником алгоритмов можно назвать книгу кулинарных рецептов. Рассмотрим простейший алгоритм.

Пр. 1. Алгоритм заварки чая.

1. Подготовить исходные величины — заварку, воду, чайник, заварник

2. Налить в чайник воду.

3. Насыпать в заварник заварку.

4. Довести воду до кипения.

5. Налить в заварник кипяток и подождать 3 минуты.

6. Заварка готова.

Свойства алгоритма.

Не каждый набор команд можно назвать алгоритмом. Алгоритм обладает определенными свойствами:

1. Конечность. Суть свойства: алгоритм не может быть бесконечным, он должен закончиться за конечное число шагов.

2. Результативность. Суть свойства: выполнив алгоритм, должны получить результат. Установление факта, что задача решения не имеет, является тоже результатом исполнения алгоритма.

3. Дискретность (прерывистость). Суть свойства: алгоритм разбивается на отдельные шаги (команды), которые выполняются одна за другой.

4. Понятность. Суть свойства: команды алгоритма должны быть понятны исполнителю. В алгоритме используются только команды из системы команд исполнителя.

5. Определенность. Суть свойства: каждая команда однозначно определяет действия исполнителя.

6. Массовость. Суть свойства: алгоритм должен обеспечивать решение не одной конкретной задачи, а класса задач данного типа.

7. Эффективность. Суть свойства: каждый шаг алгоритма должен быть выполнен точно и за конечное время, а, значит, весь алгоритм должен быть выполнен за разумно конечное (эффективное) время.

Система команд исполнителя

Исполнитель – это тот, кто будет исполнять алгоритм.

Совокупность команд, которые могут быть выполнены конкретным исполнителем, называется системой команд исполнителя.

Формальное исполнение алгоритма

Исполнитель может не иметь представления о цели выполнения алгоритма. Он должен строго и точно выполнять действия, предписанные алгоритмом, не понимая, зачем и почему это надо делать. Такое исполнение называется формальным исполнением алгоритма, что позволяет передать исполнение алгоритма автомату.

Способы записи алгоритмов.

1. Естественный язык (словесная запись алгоритма)

Обычно используется для алгоритмов, ориентированных на исполнителя – человека. Команды алгоритма нумеруют, чтобы иметь возможность на них ссылаться. Словесная запись алгоритма была использована выше для составления алгоритма заварки чая (см. Пр. 1, стр. 2)

2. Язык блок-схем (графическая запись алгоритмов). 

Конец

Начало

Команды алгоритмов помещаются внутрь блоков, соединенных стрелками, показывающими очередность выполнения команд алгоритма.

• Овал обозначает начало и конец алгоритма (блок начало и блок конец).
• Команды обработки информации помещают в блоках имеющих вид прямоугольников (блок арифметических выражений, блок присваиваний).
• Проверка условий — ромб. В результате проверки условия возникают два возможных пути для продолжения алгоритма. Эти пути изображаются стрелками со знаками «+» и «–» (иногда пишут «да» и «нет»). Переход по стрелке со знаком «+» происходит если условие соблюдено а переход по стрелке «–», если условие не выполняется.
• Операции ввода и вывода помещают в блоки, имеющие вид параллелограммов (блок ввода/вывода).

Для записи команд внутри блоков используется естественный язык с элементами математической символики.

Начало

Конец

Ввод

a, b

P:=2(a+b)

Вывод

P

Пр. 2.

Задача. Даны длина и ширина прямо-угольника. Определить периметр этого прямоугольника.

Решение. Выделяем исходные данные и результаты.

Исходные данные: а – длина, b – ширина прямоугольника.

Результат: P – периметр прямоугольника.

Составим алгоритм решения задачи и запишем его на языке блок-схем (см. рис.)

3. Алгоритмический язык (псевдокоды).

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

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

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

Запишем алгоритм нахождения периметра прямоу-гольника (см. Пр. 2), на алгоритмическом языке:

алг периметр прямоугольника

нач ввод a, b

P := 2∙(a + b)

вывод P

кон

4. Формальный язык (язык программирования).

Обычно используется для алгоритмов, ориентированных на исполнителя – ЭВМ. Алгоритм, записанный на языке программирования – программа.

Структуры алгоритмов.

Из простых команд и проверок условий образуются составные команды (структуры).

Действие

Действие

Действие

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

Структура следование

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

Под действием понимается либо простая, либо составная команда. 

Линейным называется алгоритм, в котором все этапы решения задачи выполняются строго последовательно.

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

Структура ветвление (развилка).

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

Ветвление может использоваться в двух видах: полное и неполное.

Условие

Действие

Блок-схема неполной развилки

Условие

Блок-схема полной развилки

Действие 1

Действие 2

Рассмотрим ветвление на конкретных примерах.

 Пр. 3. Фрагмент алгоритма        Пр. 4. Фрагмент алгоритма

«Поедание яблока»        «Покупка билетов»

Билеты есть?

Купить

Подойти к кассе

Отойти от кассы

Съесть

Выбросить

Яблоко гнилое?

Взять яблоко

Структура повторение (цикл)

Цикл – алгоритмическая структура, организующая многократное повторение действий.

Действия, которые повторяются в цикле, называют телом цикла.

Циклы бывают двух видов: цикл «До»  и цикл «Пока».

Условие

Действие

Блок-схема цикла «До»

Условие

Действие

Блок-схема цикла «Пока»

Цикл «Пока» — цикл с предусловием (сначала проверяется условие, потом выполняется тело цикла). В цикле «Пока» тело цикла выполняется, пока выполняется условие.

Цикл «До» — цикл с постусловием (сначала выполняется тело цикла, потом проверяется условие). В цикле «До» тело цикла выполняется до тех пор, пока не выполнится условие.

Рассмотрим циклы на конкретных примерах.

Пр. 5. Фрагмент алгоритма        Пр. 6. Фрагмент алгоритма

«Перейти дорогу»        «Помыть тарелки»

 Горит красный?

Посмотреть на светофор

Стоять

Перейти дорогу

Взять тарелку

Помыть

Убрать

Тарелки кончились?

Рассмотрим пример алгоритма, в котором внутри цикла находится ветвление.

 Пр. 7. Алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух натуральных чисел:

1. Если числа равны, то взять первое число в качестве ответа и закончить исполнение алгоритма, иначе перейти к п.2

2. Определить большее из двух чисел.

3. Заменить большее число на разность большего и меньшего чисел.

4. Перейти к п.1

Блок-схема алгоритма Евклида:

Начало

Ввод

a, b

a ≠ b

a > b

Заменить

a на a-b

Заменить

b на b-a

Вывод

a

Конец

Например, a = 32, b = 24

Трассировочная таблица:

шаг	Операция	a	b	Условие
	Ввод а	32
	Ввод b		24
	а ≠ b			32 ≠ 24, да
	а > b			32 > 24, да
	а на а-b	8
	а ≠ b			8 ≠ 24, да
	а > b			8 > 24, нет
	b на b-a		16
	а ≠ b			8 ≠ 16, да
	а > b			8 > 16, нет
	b на b-a		8
	а ≠ b			8 ≠ 8, нет
	Вывод а
	Конец

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

 Контрольные вопросы.

1. Что такое алгоритм?
2. Какие вы знаете свойства алгоритма? В чем суть каждого свойства?
3. Как вы понимаете термин «исполнитель»?
4. Что такое система команд исполнителя?
5. Что означает формальное исполнение алгоритма?
6. Какие способы записи алгоритмов вы знаете?
7. Расскажите подробно о языке блок-схем.
8. Какой формальный язык вы знаете?
9. Как называется алгоритм, записанный на языке программирования
10. Какие алгоритмические структуры вы знаете?
11. Какой алгоритм называется линейным? Привести пример.
12. Что такое ветвление? Виды ветвлений? Привести примеры.
13. Что такое цикл? Виды циклов? Привести примеры.
14. Что такое тело цикла?
15. Чем цикл «До» отличается от цикла «Пока»?

Алгоритм — это четкая последовательность действий, выполнение которой дает какой-то заранее известный результат. Проще говоря, это набор инструкций для конкретной задачи. Известнее всего этот термин в информатике и компьютерных науках, где под ним понимают инструкции для решения задачи эффективным способом.

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

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

Кто пользуется алгоритмами

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

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

Для чего нужны алгоритмы

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

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

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

Алгоритмы применяются во всех направлениях IT и во многих других отраслях. Инструкции для автоматизированного станка или линии производства — алгоритмы, рецепт блюда — тоже.

Свойства алгоритмов

Дискретность. Алгоритм — не единая неделимая структура, он состоит из отдельных маленьких шагов, или действий. Эти действия идут в определенном порядке, одно начинается после завершения другого.

Результативность. Выполнение алгоритма должно привести к какому-либо результату и не оставлять неопределенности. Результат может в том числе оказаться неудачным — например, алгоритм может сообщить, что решения нет, — но он должен быть.

Детерминированность. На каждом шаге не должно возникать разночтений и разногласий, инструкции должны быть четко определены.

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

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

Конечность. Алгоритмы конечны, они должны завершаться и выдавать результат, в некоторых определениях — за заранее известное число шагов.

Какими бывают алгоритмы

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

Линейные. Это самый простой тип алгоритма: действия идут друг за другом, каждое начинается после того, как закончится предыдущее. Они не переставляются местами, не повторяются, выполняются при любых условиях.

Ветвящиеся. В этом типе алгоритма появляется ветвление: какие-то действия выполняются, только если верны некоторые условия. Например, если число меньше нуля, то его нужно удалить из структуры данных. Можно добавлять и вторую ветку: что делать, если условие неверно — например, число больше нуля или равно ему. Условий может быть несколько, они могут комбинироваться друг с другом.

Циклические. Такие алгоритмы выполняются в цикле. Когда какой-то блок действий заканчивается, эти действия начинаются снова и повторяются некоторое количество раз. Цикл может включать в себя одно действие или последовательность, а количество повторений может быть фиксированным или зависеть от условия: например, повторять этот блок кода, пока в структуре данных не останется пустых ячеек. В некоторых случаях цикл может быть бесконечным.

Рекурсивные. Рекурсия — это явление, когда какой-то алгоритм вызывает сам себя, но с другими входными данными. Это не цикл: данные другие, но «экземпляров» работающих программ несколько, а не одна. Известный пример рекурсивного алгоритма — расчет чисел Фибоначчи.

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

Вероятностные. Такие алгоритмы упоминаются реже, но это довольно интересный тип: работа алгоритма зависит не только от входных данных, но и от случайных величин. К ним, например, относятся известные алгоритмы Лас-Вегас и Монте-Карло.

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

Графическое изображение алгоритмов

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

В схемах подписаны конкретные действия, условия, количество повторений циклов и другие детали. Это позволяет нагляднее воспринимать алгоритмы.

Сложность алгоритма

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

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

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

•  O(1) означает, что алгоритм выполняется за фиксированное константное время. Это самые эффективные алгоритмы.
•  O(n) — это сложность линейных алгоритмов. n здесь и дальше обозначает размер входных данных: чем больше n, тем дольше выполняется алгоритм.
•  O(n²) тоже означает, что чем больше n, тем выше сложность. Но зависимость тут не линейная, а квадратичная, то есть скорость возрастает намного быстрее. Это неэффективные алгоритмы, например с вложенными циклами.
•  O(log n) — более эффективный алгоритм. Скорость его выполнения рассчитывается логарифмически, то есть зависит от логарифма n.
•  O(√n) — алгоритм, скорость которого зависит от квадратного корня из n. Он менее эффективен, чем логарифмический, но эффективнее линейного.

Существуют также O(n³), O(nn) и другие малоэффективные алгоритмы с высокими степенями. Их сложность растет очень быстро, и их лучше не использовать.

Графическое описание сложности. Лучше разобраться в сложности в O-нотации поможет график. Он показывает, как изменяется время выполнения алгоритма в зависимости от размера входных данных. Чем более пологую линию дает график, тем эффективнее алгоритм.

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

Использование алгоритмов в IT

Мы приведем несколько примеров использования разных алгоритмов в отраслях программирования. На самом деле их намного больше — мы взяли только часть, чтобы помочь вам понять практическую значимость алгоритмов.

Разработка ПО и сайтов. Алгоритмы используются для парсинга, то есть «разбора» структур с данными, таких как JSON. Парсинг — одна из базовых задач, например в вебе. Также алгоритмы нужны при отрисовке динамических структур, выводе оповещений, настройке поведения приложения и многом другом.

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

Отдельное значение алгоритмы имеют в Big Data и анализе данных: там они позволяют обработать огромное количество информации, в том числе сырой, и не потратить на это слишком много ресурсов.

Поисковые задачи. Алгоритмы поиска — отдельная сложная отрасль. Их выделяют в отдельную группу, в которой сейчас десятки разных алгоритмов. Поиск важен в науке о данных, в методах искусственного интеллекта, в аналитике и многом другом. Самый очевидный пример — поисковые системы вроде Google или Яндекса. Кстати, подробности об используемых алгоритмах поисковики обычно держат в секрете.

Машинное обучение. В машинном обучении и искусственном интеллекте подход к алгоритмам немного другой. Если обычная программа действует по заданному порядку действий, то «умная машина» — нейросеть или обученная модель — формирует алгоритм для себя сама в ходе обучения. Разработчик же описывает модель и обучает ее: задает ей начальные данные и показывает примеры того, как должен выглядеть конечный результат. В ходе обучения модель сама продумывает для себя алгоритм достижения этого результата.

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

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

Основные понятия алгоритмизации

Работа по решению любой задачи с использованием компьютера делится на следующие этапы:

1. Постановка задачи.
2. Формализация задачи.
3. Построение алгоритма.
4. Составление программы на языке программирования.
5. Отладка и тестирование программы.
6. Использование программы.

Часто эту последовательность называют технологической цепочкой решения задачи. Непосредственно к программированию в этом списке относятся пункты 3, 4, 5.

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

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

Третий этап — построение алгоритма. Опытные программисты часто сразу пишут программы на языках, не прибегая к каким-либо специальным способам описания алгоритмов (блок-схемам, псевдокодам). Однако в учебных целях полезно использовать эти средства, а затем переводить полученный алгоритм на язык программирования.

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

Таким образом, программист должен обладать следующими знаниями и навыками:

• уметь строить алгоритмы;
• знать языки программирования;
• уметь работать в соответствующей системе программирования.

Понятие алгоритма

Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi — латинского написания имени Мухаммеда альХорезми (787 — 850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел — вот первые алгоритмы в математике.

В наше время понятие алгоритма трактуется шире. Алгоритм — это последовательность команд управления каким-либо исполнителем.

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

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

В разделе информатики под названием Программирование изучаются методы программного управления работой ЭВМ. Следовательно, в качестве исполнителя выступает компьютер.

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

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

Например, при решении квадратного уравнения ах² + Ьх + с = 0
исходными данными являются коэффициенты а, Ь, с; результатами — корни уравнения х1, х2; промежуточным данным — дискриминант уравнения D = b² — 4ас.

Для успешного освоения программирования необходимо усвоить следующее правило: всякая величина занимает свое определенное место в памяти ЭВМ (иногда говорят — ячейку памяти). Хотя термин «ячейка» с точки зрения архитектуры современных ЭВМ несколько устарел, однако в учебных целях его удобно использовать.

У всякой величины имеются три основных свойства: имя, значение и тип (на самом деле многие современные языки, такие как PHP или JS, обходятся без явного указания типа, интерпретируя тип переменной в зависимости от контекста операции). На уровне команд процессора величина идентифицируется при помощи адреса ячейки памяти, в которой она хранится. В алгоритмах и языках программирования величины делятся на константы и переменные. Константа — неизменная величина, и в алгоритме она представляется собственным значением, например: 15, 34.7, k, true и т.д. Переменные величины могут изменять свои значения в ходе выполнения программы и представляются символическими именами — идентификаторами, например: X, S2, cod15. Любая константа, как и переменная, занимает ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.

Теперь о типах величин — типах данных. С понятием типа данных вы уже, возможно, встречались, изучая в курсе информатики базы данных и электронные таблицы. Это понятие является фундаментальным для программирования.

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

Тип	Значения	Операции	Внутреннее представление
Целый	Целые положительные и отрицательные числа в некотором диапазоне. Примеры: 23, —12, 387	Арифметические операции с целыми числами: +, —, *, целое деление и остаток от деления. Операции отношений (<, >, = и др.)	Формат с фиксированной точкой
Вещественный	Любые (целые и дробные) числа в некотором диапазоне. Примеры: 2.5, -0.01, 45.0, 3.6-109	Арифметические операции: +, —, *, /. Операции отношений	Формат с плавающей точкой
Логический	True (истина), False (ложь)	Логические операции: И (&), ИЛИ (|), HE (~). Операции отношений	1 бит: 1 — true; 0 — false
Символьный	Любые символы компьютерного алфавита. Примеры: ‘а’, ‘5’, ‘+’, ‘$’	Операции отношений	Коды таблицы символьной кодировки. 1 символ — 1 байт (Сейчас используются многобайтные кодировки: UTF-8, UTF-16…)

Типы констант определяются по контексту (т.е. по форме записи в тексте), а типы переменных устанавливаются в описаниях переменных (не во всех языках; Python, например, не имеет явного определения типа, тип переменной определяетя при первом присваивании).

Есть еще один вариант классификации данных — классификация по структуре. Данные делятся на простые и структурированные. Для простых величин (их еще называют скалярными) справедливо утверждение: одна величина — одно значение, для структурированных: одна величина — множество значений. К структурированным величинам относятся массивы, строки, множества и т.д.

Свойства алгоритма

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

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

Дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

Определенность (детерминнированность) — предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер.

Результативность (конечность) — алгоритм должен приводить к решению задачи за конечное число шагов.

Формы записи алгоритмов

На практике наиболее распространены следующие формы представления алгоритмов:

• словесная (запись на естественном языке)
• графическая (изображения из графических символов)
• псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.
• программная (тексты на языках программирования)

Пример: написать алгоритм «Одеться по погоде». Если на улице температура ниже 0, то необходимо надеть шубу, иначе – куртку.

Словесный способ записи алгоритма

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

Алгоритм ПОГОДА  
Начало  
определить температуру воздуха  
если температура ниже 0, то надеть шубу, иначе надеть куртку  
Конец.

Словесный способ не имеет широкого распространения, так как такие описания:

• строго не формализуемы;
• страдают многословностью записей;
• допускают неоднозначность толкования отдельных предписаний.

Графический способ записи алгоритмов

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

Такое графическое представление называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. В таблице приведены наиболее часто употребляемые символы.

Название символа	Обозначение и пример заполнения	Пояснение
Процесс		Вычислительное действие или последовательность действий
Решение		Проверка условий
Модификация		Начало цикла
Предопределенный процесс		Вычисления по подпрограмме, стандартной подпрограмме
Ввод-вывод		Ввод-вывод в общем виде
Пуск-останов		Начало, конец алгоритма, вход и выход в подпрограмму
Документ		Вывод результатов на печать

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

Блок решение используется для обозначения переходов управления по условию. В каждом блоке решение должны быть указаны вопрос, условие или сравнение, которые он определяет.

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

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

Блок Ввод-вывод используется для преобразования данных в фор­му, пригодную для обработки (ввод) или отображения результатов обработки (вывод). Отдельным логическим устройствам компьютера или отдельным функциям об­мена соответствуют определенные блочные символы. В каждом из них указыва­ются тип устройства или файла данных, тип информации, участвующий в обме­не, а также вид операции обмена.

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

Блок Документ предназначен для ввода-вывода данных, носителем которых служит бумага.

Псевдокод

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

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

В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя.

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

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

Программный способ записи алгоритмов

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

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

Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера.

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

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

//Пример программы на языке C#
namespace oap
{
  class Program
  {
    static void Main(string[] args)
    {
      Console.WriteLine("введите температуру воздуха t: ");
      var t = int.Parse( Console.ReadLine() );
      if (t < 0)
        Console.WriteLine("одеть шубу");
      else
        Console.WriteLine("одеть куртку");
    }
  }
}

Структурное программирование

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

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

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

Каждый вспомогательный алгоритм описывает способ решения некоторой вспомогательной задачи или даже общий способ решения некоторого класса вспомогательных подзадач.

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

Общие принципы построения алгоритмов

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

Принцип поэтапной детализации алгоритма (другое название — «проектирование сверху-вниз»). Этот принцип предполагает первоначальную разработку алгоритма в виде укрупненных блоков (разбиение задачи на подзадачи) и их постепенную детализацию.

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

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

Определение сложности работы алгоритмов

Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

Память или время

Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.

Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.

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

Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти.

Оценка порядка

При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.

В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим код, который для матрицы A[NxN] находит максимальный элемент в каждой строке.

for i:=1 to N do
begin
  max:=A[i,1];
  for j:=1 to N do
  begin
    if A[i,j]>max then
      max:=A[i,j]
  end;
  writeln(max);
end;

В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N²).

Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N³+N. В таком случае его сложность будет равна O(N³). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N³+N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%.

При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N³ рассматривается, как O(N³). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.

Определение сложности

Наиболее сложными частями программы обычно является выполнение циклов и вызов процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов.

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

В качестве примера рассмотрим две процедуры: Slow со сложностью O(N³) и Fast со сложностью O(N²).

procedure Slow;
var
  i,j,k: integer;
begin
  for i:=1 to N do
    for j:=1 to N do
      for k:=1 to N do
        //какое-то действие
end;

procedure Fast;
var
  i,j: integer;
begin
  for i:=1 to N do
    for j:=1 to N do
      Slow;
end;

procedure Both;
begin
  Fast;
end;

Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N²)*O(N³)=O(N⁵).

Если же основная программа вызывает процедуры по очереди, то их сложности складываются:

O(N²)+O(N³)=O(N³).

Следующий фрагмент имеет именно такую сложность:

procedure Slow;
var
  i,j,k: integer;
begin
  for i:=1 to N do
    for j:=1 to N do
      for k:=1 to N do
        {какое-то действие}
end;

procedure Fast;
var
  i,j: integer;
begin
  for i:=1 to N do
    for j:=1 to N do
      {какое-то действие}
end;

procedure Both;
begin
  Fast;
  Slow;
end;

Сложность рекурсивных алгоритмов

Простая рекурсия

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

Рассмотрим рекурсивную реализацию вычисления факториала:

function Factorial(n: Word): integer;
begin
  if n > 1 then
    Factorial:=n*Factorial(n-1)
  else
    Factorial:=1;
end;

Эта процедура выполняется N раз, таким образом, вычислительная сложность этого алгоритма равна O(N).

Многократная рекурсия

Рекурсивный алгоритм, который вызывает себя несколько раз, называется многократной рекурсией. Такие процедуры гораздо сложнее анализировать, кроме того, они могут сделать алгоритм гораздо сложнее.

Рассмотрим такую процедуру:

procedure DoubleRecursive(N: integer);
begin
  if N>0 then
  begin
    DoubleRecursive(N-1);
    DoubleRecursive(N-1);
  end;
end;

Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2^(N+1)-1)=O(2^N).

Всегда надо помнить, что анализ сложности рекурсивных алгоритмов весьма нетривиальная задача.

Объёмная сложность рекурсивных алгоритмов

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

Средний и наихудший случай

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

function Locate(data: integer): integer;
var
  i: integer;
  fl: boolean;
begin
  fl:=false; i:=1;
  while (not fl) and (i<=N) do
  begin
    if A[i]=data then
      fl:=true
    else
      i:=i+1;
  end;
  if not fl then
    i:=0;
  Locate:=i;
end;

Если искомый элемент находится в конце списка, то программе придётся выполнить N шагов. В таком случае сложность алгоритма составит O(N). В этом наихудшем случае время работы алгоритма будем максимальным.

С другой стороны, искомый элемент может находится в списке на первой позиции. Алгоритму придётся сделать всего один шаг. Такой случай называется наилучшим и его сложность можно оценить, как O(1).

Оба эти случая маловероятны. Нас больше всего интересует ожидаемый вариант. Если элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N).

В данном случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N²), в то время как ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее.

Общие функции оценки сложности

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

1. C – константа (время выполнения алгоритма не зависит от входных параметров, линейные алгоритмы)
2. log(log(N))
3. log(N) — (поиск в сортированном массиве)
4. N^C, 0<C<1
5. N — линейная сложность (поиск в не сортированном массиве)
6. N*log(N)
7. N^C, C>1
8. C^N, C>1
9. N!

Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!).

Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N²), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).

Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.

В заключение приведём таблицу, которая показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы.

Сложность	N=10	N=20	N=30	N=40	N=50
N3	0.001 c	0.008 c	0.027 c	0.064 c	0.125 c
2N	0.001 c	1.05 c	17.9 мин	1.29 дней	35.7 лет
3N	0.059 c	58.1 мин	6.53 лет	3.86*105 лет	2.28*1010 лет
N!	3.63 c	7.71*104 лет	8.41*1018 лет	2.59*1034 лет	9.64*1050 лет

Википедия: Временная сложность алгоритма

---

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Этапы решения задачи на компьютере? Охарактеризуйте их. Проиллюстрируйте этапы постановки и формализации на примере задачи: вычислить время движения моторной лодки между двумя пунктами.

2. Понятие алгоритма.

3. Основные типы данных.

4. Свойства алгоритма.

5. Формы записи алгоритмов.

6. Что такое структурное программирование? Каковы основные прнципы структурной методики построения алгоритмов?