В теории вычислительной сложности средняя сложность алгоритма — это количество некоторого вычислительного ресурса (обычно времени), используемого алгоритмом, усредненное по всем возможным входным данным. Его часто противопоставляют сложности в наихудшем случае , когда учитывается максимальная сложность алгоритма для всех возможных входных данных.
Есть три основных мотива для изучения средней сложности. [1] Во-первых, хотя в худшем случае некоторые проблемы могут оказаться неразрешимыми, входные данные, вызывающие такое поведение, могут редко встречаться на практике, поэтому сложность в среднем случае может быть более точной мерой производительности алгоритма. Во-вторых, анализ сложности среднего случая предоставляет инструменты и методы для создания сложных экземпляров проблем, которые можно использовать в таких областях, как криптография и дерандомизация . В-третьих, средняя сложность позволяет выделить наиболее эффективный на практике алгоритм среди алгоритмов эквивалентной наилучшей сложности (например, Quicksort ).
Анализ среднего случая требует понятия «средних» входных данных для алгоритма, что приводит к проблеме разработки распределения вероятностей по входным данным. В качестве альтернативы можно использовать рандомизированный алгоритм . Анализ таких алгоритмов приводит к родственному понятию ожидаемой сложности . [2] : 28
Производительность алгоритмов в среднем случае изучалась с тех пор, как в 1950-х годах были разработаны современные представления об эффективности вычислений. Большая часть этой первоначальной работы была сосредоточена на проблемах, для которых уже были известны алгоритмы полиномиального времени для наихудшего случая. [3] В 1973 году Дональд Кнут [4] опубликовал том 3 книги « Искусство компьютерного программирования» , в котором подробно рассматривается производительность алгоритмов в среднем случае для задач, решаемых за полиномиальное время в наихудшем случае, таких как сортировка и нахождение медианы.
Эффективный алгоритм для NP-полных задач обычно характеризуется как работающий за полиномиальное время для всех входных данных; это эквивалентно требованию эффективной сложности в наихудшем случае. Однако алгоритм, который неэффективен для «небольшого» количества входных данных, может быть эффективным для «большинства» входных данных, встречающихся на практике. Таким образом, желательно изучить свойства этих алгоритмов, где сложность в среднем случае может отличаться от сложности в наихудшем случае, и найти методы, чтобы связать их.
Фундаментальные понятия сложности в среднем были разработаны Леонидом Левиным в 1986 году, когда он опубликовал одностраничную статью [5] , определяющую сложность и полноту в среднем и приведя пример полной задачи для distNP, аналога задачи в среднем случае НП .