Алгоритм "быстрая сортировка" в общем случае более быстрый, чем сортировка вставками:
В терминах машин Тьюринга детерминированность отражается в том, что программа МТ является отображением:
Детерминированность алгоритма заключается в том, что на каждом шаге имеется лишь одно допустимое действие, зависящее от входных данных и от текущего внутреннего состояния:
Для недетерминированных алгоритмов обычно рассматривают только одну форму задач - задачи распознавания языков:
Для списка общего вида вычислительная сложность "быстрой" сортировки равна O(n):
Емкостная сложность алгоритма - объем памяти, требуемый для решения задачи:
Множество всех слов над алфавитом A обозначается как A*:
Наихудшим сценарием для "быстрой" сортировки будет тот, при котором центральный элемент все время попадает в одноэлементный подсписок, а все прочие элементы остаются во втором подсписке:
Недетерминированная машина Тьюринга является чисто теоретическим понятием:
НМТ допускает входное слово x, если только одна последовательность конфигураций приводит к допускающему состоянию:
Операция умножения требует большего времени, чем операция сложения:
При оценке сложности алгоритма обычно рассматривают его сложность в лучшем случае:
Существуют задачи, для которых не существует самого быстрого алгоритма:
Теорема Блюма утверждает, что ускорение возможно для любой задачи:
Формальная система записи алгоритма адекватна реальной системе команд процессора: