Алгоритмическую сложность можно определить как зависимость времени исполнения алгоритма от длины входных данных:
В Гамильтоновом цикле нужно выйти из какой-то вершины и вернуться в нее таким образом, чтобы ни в какой промежуточной вершине не побывать дважды:
В параметрически-зависимых по трудоемкости алгоритмах трудоемкость определяется размерностью входа:
Для всех функций f(n) = 1/n, f(n) = 7, f(n) = 2 · n + 12, f(n) = n · ln (n) будет справедлива оценка О(n):
Задача о коммивояжере относится к задачам класса Р:
Задача поиска нужной фамилии в телефонном справочнике имеет логарифмическую сложность:
Запись O(g(n)) обозначает класс функций таких, что все они растут не быстрее, чем функция g(n) с точностью до постоянного множителя:
Класс NPC-задач содержится в классе NP-задач:
Классом алгоритмов NP называется класс алгоритмов, выполняемых за полиномиальное время на недетерминированных машинах Тьюринга:
Количество элементарных операций, выполняемых алгоритмом на одном входе длины N, всегда совпадает с количеством операций на другом входе такой же длины:
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа соответствует ровно два варианта действий:
Недетерминированная машина Тьюринга решает только задачи класса Р:
Примером алгоритма с количественно-зависимой функцией трудоемкости может служить алгоритм умножения матрицы на вектор:
Финитные алгоритмы - алгоритмы, дающие решение общей проблемы за конечное время: