В математике и информатике алгоритм AL-gə-ridh-əm) является однозначной спецификацией того, как решить класс проблем. Алгоритмы могут выполнять вычисления, обработку данных и автоматические задачи рассуждения.

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

Концепция алгоритма существует на протяжении веков, и использование этой концепции можно приписать греческим математикам, например, сито Эратосфена и алгоритма Евклида; Сам термин «алгоритм» происходит от математика 9-го века Мухаммада ибн Муса аль-Хвардими, латинизированного «Алгоритми». Частичная формализация того, что станет современным понятием алгоритма, началось с попыток решить проблему Entscheidungs ​​(«проблема решения»), поставленную Дэвидом Гильбертом в 1928 году. Последующие формализации были сформулированы как попытки определить «эффективную вычислимость» или «эффективный метод», ; эти формализации включали рекурсивные функции Гёделя-Хербранда-Клейна 1930, 1934 и 1935 гг., исчисление лямбды Алонсо Церкви 1936 года, формула 1 Эмиля Поста 1, 1936 года и машины Тьюринга Алана Тьюринга 1936-7 и 1939 годов.

Этимология
Слово «алгоритм» имеет свои корни в латинском названии Мухаммада ибн Муса аль-Хорезми в первом шаге к алгоризму. Аль-Хварзими (персидский: خوارزمی, c. 780-850) был персидским математиком, астрономом, географом и ученым в Доме Мудрости в Багдаде, чье имя означает «уроженец Хорезма», регион, который был частью Большого Ирана и сейчас находится в Узбекистане.

Около 825 года аль-Хорезми написал трактат на арабском языке о системе индусско-арабских цифр, который был переведен на латынь в 12 веке под названием Algoritmi de numero Indorum. Это название означает «Алгоритми по числу индейцев», где «Алгоритми» была латинизацией переводчика имени Аль-Хорезми. Аль-Хорезми был самым читаемым математиком в Европе в позднем средневековье, прежде всего через одну из своих книг — Алгебру. В поздней средневековой латыни, алгоризм, английский «алгоризм», коррупция его имени, просто означали «систему счисления в десятичной системе». В XV веке, под влиянием греческого слова ἀριθμός ‘number’ (см. «Арифметика»), латинское слово было изменено на алгоритм, а соответствующий английский термин «алгоритм» впервые засвидетельствован в 17 веке; современный смысл был введен в XIX веке.

На английском языке он был впервые использован примерно в 1230 году, а затем Чосером в 1391. Английский принял французский термин, но только в конце 19-го века «алгоритм» принял значение, которое он имеет на современном английском языке.

Еще одно раннее использование этого слова — с 1240 года, в пособии под названием «Carmen de Algorismo», составленном Александром де Виллее. Он начинается так:

Haec algorismus ars praesens dicitur, в qua / Talibus Indorum fruimur bis quinque figuris.

который переводится как:

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

Стихотворение состоит из нескольких сотен строк и суммирует искусство расчета с новым стилем индийских кубиков, или Talibus Indorum, или индусскими цифрами.

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

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

Boolos, Jeffrey & 1974, 1999 предлагают неофициальное значение слова в следующей цитате:

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

«Перечислимо бесконечное множество» — это элемент, элементы которого можно поместить во взаимно однозначное соответствие с целыми числами. Таким образом, Boolos и Jeffrey говорят, что алгоритм подразумевает инструкции для процесса, который «создает» выходные целые числа из произвольного «входного» целого или целых чисел, которые теоретически могут быть сколь угодно большими. Таким образом, алгоритмом может быть алгебраическое уравнение, такое как y = m + n — две произвольные «входные переменные» m и n, которые производят выход y. Но попытки различных авторов определить понятие указывают на то, что слово подразумевает гораздо больше, чем это, что-то порядка (для примера добавления):

Точные инструкции (на языке, понятном «компьютеру») для быстрого, эффективного, «хорошего» процесса, который определяет «ходы» «компьютера» (машины или человека, оснащенные необходимой внутренней информацией и возможностями), чтобы найти , декодировать, а затем обрабатывать произвольные входные целые числа / символы m и n, символы + и = … и «эффективно» производить в «разумное время» выходное целое y в определенном месте и в определенном формате.
Концепция алгоритма также используется для определения понятия разрешимости. Это понятие имеет центральное значение для объяснения того, как возникают формальные системы, начиная с небольшого набора аксиом и правил. В логике время, которое требует алгоритм для завершения, невозможно измерить, поскольку оно, по-видимому, не связано с нашим обычным физическим измерением. Из таких неопределенностей, которые характеризуют текущую работу, вытекает отсутствие недоступности определения алгоритма, который подходит как конкретному (в некотором смысле), так и абстрактному использованию термина.

формализация
Алгоритмы важны для того, как компьютеры обрабатывают данные. Многие компьютерные программы содержат алгоритмы, в которых подробно описываются конкретные инструкции, которые компьютер должен выполнять (в определенном порядке) для выполнения заданной задачи, например, вычисление зарплат сотрудников или печать отчетов учащихся. Таким образом, алгоритм можно рассматривать как любую последовательность операций, которую можно моделировать с помощью системы Тьюринга. Авторы, утверждающие этот тезис, включают Минский (1967), Дикарь (1987) и Гуревич (2000):

Мински: «Но мы также будем поддерживать с Тьюрингом … что любая процедура, которую можно« естественным образом »назвать эффективной, на самом деле может быть реализована (простой) машиной. Хотя это может показаться крайним, аргументы … в его милость трудно опровергнуть ».

Гуревич: «… Неофициальный аргумент Тьюринга в пользу его диссертации обосновывает более сильный тезис: каждый алгоритм может быть смоделирован машиной Тьюринга … согласно Savage [1987], алгоритм — это вычислительный процесс, определяемый машиной Тьюринга», ,

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

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

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

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

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

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

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

Представления алгоритмов можно классифицировать на три приемлемых уровня описания машины Тьюринга:

1 Описание высокого уровня
«… проза для описания алгоритма, игнорируя детали реализации. На этом уровне нам не нужно упоминать, как машина управляет своей лентой или головой».
2 Описание реализации
«… проза, используемая для определения того, как машина Тьюринга использует свою голову и как она хранит данные на своей ленте. На этом уровне мы не даем подробностей о состоянии или функции перехода».
3 Официальное описание
Наиболее подробный «самый низкий уровень» дает «таблицу состояний» машины Тьюринга.
Для примера простого алгоритма «Добавить m + n», описанного на всех трех уровнях, см. Примеры алгоритмов #.

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

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

«Элегантные» (компактные) программы, «хорошие» (быстрые) программы: понятие «простота и элегантность» появляется неофициально в Кнуте и именно в Чаитине:

Кнут: «Мы хотим хороших алгоритмов в каком-то слабо определенном эстетическом смысле … Один критерий … это время, затраченное на выполнение алгоритма … Другие критерии — это адаптивность алгоритма к компьютерам, его простота и элегантность , и т.д»
Chaitin: «… программа« элегантная », под которой я подразумеваю, что это наименьшая возможная программа для производства вывода, которую она делает»
Chaitin предисловие к его определению: «Я покажу, что вы не можете доказать, что программа« элегантна »- такое доказательство решит проблему Halting (ibid).

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

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

Компьютеры (и компиляторы), модели вычислений: компьютер (или человеческий «computor») — это ограниченный тип машины, «дискретное детерминированное механическое устройство», слепо следуя его инструкциям. Первоначальные модели Мельцака и Ламбека сводили это понятие к четырем элементам: (i) дискретные, различимые местоположения, (ii) дискретные, неразличимые счетчики (iii) агента и (iv) список инструкций, которые эффективны относительно возможностей агент.

Моделирование алгоритма: компьютерный (computor) язык: Кнут советует читателю, что «лучший способ изучить алгоритм — попробовать … сразу взять ручку и бумагу и работать на примере». Но как насчет симуляции или исполнения реальной вещи? Программист должен перевести алгоритм в язык, который может эффективно выполнять симулятор / компьютер / компилятор. Камень дает пример: при вычислении корней квадратного уравнения компаньон должен знать, как взять квадратный корень. Если они этого не делают, то алгоритм, чтобы быть эффективным, должен предоставить набор правил для извлечения квадратного корня.

Это означает, что программист должен знать «язык», который эффективен относительно целевого вычислительного агента (компьютер / компаратор).

Алгоритмический анализ
Часто важно знать, сколько определенного ресурса (например, времени или хранения) теоретически требуется для данного алгоритма. Разработаны методы анализа алгоритмов для получения таких количественных ответов (оценок); например, алгоритм сортировки выше имеет требование времени O (n), используя большую запись O с n как длину списка. Во все времена алгоритму нужно запомнить только два значения: наибольшее число, найденное до сих пор, и его текущую позицию во входном списке. Следовательно, говорят, что для O (1) требуется пространство для пространства, если пространство, необходимое для хранения входных чисел, не учитывается, или O (n), если оно подсчитано.

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

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

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

Реализация
Один из способов классификации алгоритмов — средствами реализации.

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

логический
Алгоритм можно рассматривать как управляемый логический вывод. Это понятие может быть выражено как: Алгоритм = логика + управление. Логическая составляющая выражает аксиомы, которые могут быть использованы в вычислении, а контрольная составляющая определяет способ применения вычитания к аксиомам. Это является основой для парадигмы логического программирования. В чистых логических языках программирования компонент управления фиксирован, а алгоритмы задаются путем подачи только логической составляющей. Привлекательность этого подхода — элегантная семантика: изменение аксиом имеет четко определенное изменение в алгоритме.

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

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

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

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

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

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

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

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

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

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

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

Когда проблема показывает оптимальные подструктуры — это означает, что оптимальное решение проблемы может быть построено из оптимальных решений подзадач — и перекрывающихся подзадач, что означает, что одни и те же подзадачи используются для решения многих разных проблемных ситуаций, более быстрый подход, называемый динамическим программированием, позволяет избежать рекомпиляции решений, которые уже были вычислены. Например, алгоритм Флойда-Варшалла, кратчайший путь к цели из вершины в взвешенном графе можно найти, используя кратчайший путь к цели из всех смежных вершин. Динамическое программирование и memoization идут вместе. Основное различие между динамическим программированием и делением и завоеванием заключается в том, что подзадачи более или менее независимы в делении и покорении, тогда как подпрограммы перекрываются в динамическом программировании. Разница между динамическим программированием и прямой рекурсией заключается в кешировании или мемонации рекурсивных вызовов. Когда подзадачи независимы и нет повторений, мемонирование не помогает; поэтому динамическое программирование не является решением для всех сложных задач. Используя memoization или поддерживая таблицу подзадач, которые уже решены, динамическое программирование уменьшает экспоненциальный характер многих проблем до полиномиальной сложности.

Жадный метод
Жадный алгоритм аналогичен алгоритму динамического программирования, поскольку он работает, исследуя подструктуры, в данном случае не проблемы, а заданного решения. Такие алгоритмы начинаются с некоторого решения, которое может быть дано или каким-то образом построено, и улучшить его, сделав небольшие изменения. Для некоторых проблем они могут найти оптимальное решение, в то время как для других они останавливаются на локальных оптимумах, то есть в решениях, которые не могут быть улучшены алгоритмом, но не являются оптимальными. Наиболее популярным использованием жадных алгоритмов является поиск минимального остовного дерева, где поиск оптимального решения возможен с помощью этого метода. Huffman Tree, Kruskal, Prim, Sollin — жадные алгоритмы, которые могут решить эту проблему оптимизации.

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

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

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

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

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

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

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