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