Худший случай сложности

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В информатике (особенно в теории сложности вычислений), худший случай сложности (он обозначается Big-oh(n)) измеряет ресурсы (например, время выполнения, память), которые требуются алгоритму для обработки входных данных случайного размера (обычно обозначаемого n в асимптотическом обозначении). Он обозначает верхнюю границу ресурсов, требуемых алгоритму.

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

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

Определение

[править | править код]

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

Так как нас обычно интересует зависимость временной сложности алгоритма на входных данных различной длины, злоупотребляя терминологий, временной сложностью алгоритма иногда называют соответствие , определяемое максимальной сложностью

входных данных длиной или размером .

Подобные определения могут быть даны пространственной сложности.

Способы формулировки

[править | править код]

Очень часто, сложность алгоритма дана в асимптотическом Big-O обозначении, которое обозначает его рост в форме с функцией сравнения использующей конкретные вещественные значения и обозначением:

Довольно часто, формулировка звучит следующим образом:

  • „Алгоритм имеет худший случай сложности .“

или еще короче:

  • „Алгоритм имеет сложность .“

Рассмотрим выполнение алгоритма сортировки вставками на числах с использованием машины с произвольным доступом к памяти. В лучшем случае для алгоритма, когда числа уже отсортированы, требуется шагов для выполнения задачи. Однако, в худшем случае для алгоритма, когда числа отсортированы в обратном порядке, требуется шагов для их сортировки; таким образом худший случай временной сложности алгоритма сортировки вставками .