В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число , такое, что время работы алгоритма для всех входов длины не превосходит , то временную сложность данного алгоритма можно асимптотически оценить как .
Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как . В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации. Так как время работы алгоритма может отличаться на входах одного и того же размера, обычно используется время работы в худшем случае, которое обозначается как и определяется как наибольшее по всем входным данным длины время работы алгоритма. Реже, и это обычно оговаривается специально, вычисляется , то есть математическое ожидание времени работы по всем возможным входам. Время работы алгоритма может быть классифицировано в зависимости от того, какая функция находится под О-нотацией. Например, алгоритм с называют алгоритмом с линейным временем работы, а алгоритм с для некоторого называют полиномиальным.
Таблица сложностей по времени
Следующая таблица обобщает наиболее часто встречающиеся классы сложности. В таблице обозначает произвольный многочлен от , то есть .
Название Класс сложности Время работы, Примеры времени работы Примеры алгоритмов константное время Определение чётности целого числа (представленного в двоичном виде) обратная функция Аккермана Амортизационный анализ на одну операцию с использованием непересекающихся множеств итерированно логарифмическое время Распределённые раскраски циклов дважды логарифмическое Время амортизации на одну операцию при использовании ограниченной логарифмическое время , Двоичный поиск полилогарифмическое время сублинейное время при , Поиск в k-мерном дереве линейное время Поиск наименьшего или наибольшего элемента в неотсортированном массиве «n log-звёздочка n» Алгоритм триангуляции многоугольника . линейно-логарифмическое время , Самая быстрая квадратичное время Сортировка пузырьком, сортировка вставками, прямая свёртка кубическое время Обычное умножение двух матриц. Вычисление . полиномиальное время P , , Алгоритм Кармаркара для линейного программирования, АКС-тест простоты квазиполиномиальное время QP , Самый быстрый известный — аппроксимационный алгоритм для ориентированной задачи Штейнера. субэкспоненциальное время(первое определение) SUBEXP для всех Если принять теоретические гипотезы, BPP содержится в SUBEXP. субэкспоненциальное время (второе определение) Самые быстрые известные алгоритмы разложения на множители целых чисел и проверки экспоненциальное время(с линейной экспонентой) , Решение задачи коммивояжёра с помощью динамического программирования экспоненциальное время EXPTIME , Решение задачи о порядке перемножения матриц с помощью полного перебора факториальное время Решение задачи коммивояжёра полным перебором дважды экспоненциальное время Проверка верности заданного утверждения в арифметике ПресбургераАлгоритм ЕвклидаАлгоритм Полига - ХеллманаЕсли множители, на которые раскладывается , достаточно маленькие, то алгоритм очень эффективенρ-метод ПоллардаИмеет эвристическую оценку сложности
Константное время Говорят, что алгоритм является алгоритмом константного времени (записывается как время ), если значение ограничено значением, не зависящим от размера входа. Например, получение одного элемента в массиве занимает константное время, поскольку выполняется единственная команда для его обнаружения. Однако нахождение минимального значения в неотсортированном массиве не является операцией с константным временем, поскольку мы должны просмотреть каждый элемент массива. Таким образом, эта операция занимает линейное время, . Если число элементов известно заранее и не меняется, о таком алгоритме можно говорить как об алгоритме константного времени.
Несмотря на название «константное время», время работы не обязательно должно быть независимым от размеров задачи, но верхняя граница времени работы должна. Например, задача «обменять значения и , если необходимо, чтобы в результате получили », считается задачей константного времени, хотя время работы алгоритма может зависеть от того, выполняется ли уже неравенство или нет. Однако существует некая константа , для которой время выполнения задачи всегда не превосходит .
Ниже приведен пример кода, работающего за постоянное время: int index = 5; int item = list[index]; if (условие верно) then выполнить некоторые операции с постоянным временем работы else выполнить некоторые операции с постоянным временем работы for i = 1 to 100 for j = 1 to 200 выполнить некоторые операции с постоянным временем работы
Если равно , где — константа, то это эквивалентно тому, что равно .
Логарифмическое время
Говорят, что алгоритм выполняется за логарифмическое время, если . Поскольку в компьютерах принята двоичная система счисления, в качестве основания логарифма используется (то есть ). Однако при замене основания логарифма и отличаются лишь на постоянный множитель , который в записи O-большое отбрасывается. Таким образом, является стандартной записью для алгоритмов логарифмического времени независимо от основания логарифма.
Алгоритмы, работающие за логарифмическое время, обычно встречаются при операциях с двоичными деревьями или при использовании двоичного поиска.
алгоритмы для работы с массивами данных размера считаются высокоэффективными, поскольку отношение времени выполнения одной операции к размеру массива уменьшается с увеличением этого размера.
Очень простой пример такого алгоритма — поиск слов в словаре. Рассмотрим словарь , в котором записаны слов, отсортированных по алфавиту. При этом считаем, что все слова имеют длину и что мы можем за константное время получить доступ к любому элементу словаря по индексу. Пусть — это -й элемент словаря, тогда можно проверить, лежит ли слово в словаре за . Для этого нужно рассмотреть элемент словаря , где обозначает округление числа вниз. Если , то нам стоит перейти в правую половину массива, иначе — в левую. В конце мы получим индекс первого слова, который равен или лексикографически больше, чем . int find(vector<string> &D, string w) { int n = D.size(); int l = -1, r = n; while(r - l > 1) { int m = (l + r) / 2; if(D[m] < w) { l = m; } else { r = m;
return r; }
Полилогарифмическое время Говорят, что алгоритм работает за полилогарифмическое время, если для некоторого . Например, задача о порядке перемножения матриц может быть решена за такое время на .
Сублинейное время Говорят, что алгоритм выполняется за сублинейное время, если . В частности, сюда включаются алгоритмы, чья временная сложность соответствует указанным выше, а также, например, поиск Гровера со сложностью .
Обычно алгоритмы, которые, являясь точными, всё же работают за сублинейное время, используют распараллеливание процессов (как это делает алгоритм NC1 вычисления определителя матрицы), неклассические вычисления (как в поиске Гровера) или имеют гарантированное предположение о структуре входа (как алгоритмы двоичного поиска и многие алгоритмы обработки деревьев). Однако такие формальные языки как язык слов, имеющих единичный бит в позиции, определяемой первыми битами слова, могут быть разрешимыми за сублинейное время даже несмотря на то, что любой бит может быть важен для определения принадлежности слова языку.
Термин алгоритм с сублинейным временем работы обычно используется для алгоритмов, которые, в отличие от приведённых выше примеров, работают на обычных последовательных моделях машин и не предполагают априорных знаний о структуре входа. Однако для них допускается применение вероятностных методов и даже более того, зачастую они должны быть рандомизированными для любой нетривиальной задачи.
Так как такой алгоритм обязан давать ответ без полного чтения входных данных, он в очень сильной степени зависит от способов доступа, разрешённых во входном потоке. Обычно для потока, представляющего собой битовую строку , предполагается, что алгоритм может за время запросить значение для любого .
Алгоритмы сублинейного времени, как правило, вероятностны и дают лишь аппроксимированное решение. Алгоритмы сублинейного времени выполнения возникают естественным образом при исследовании .
Линейное время Говорят, что алгоритм работает за линейное время, или за время , если его сложность равна . Неформально, это означает, что для достаточно большого размера входных данных время работы увеличивается линейно от размера входа. Например, процедура, суммирующая все элементы списка, требует время, пропорциональное длине списка. Это описание не вполне точно, поскольку время работы может существенно отличаться от точной пропорциональности, особенно для малых значений .
Линейное время часто рассматривается как желательный атрибут алгоритма. Было проведено много исследований для создания алгоритмов с (почти) линейным или лучшим временем работы. Эти исследования включали как программные, так и аппаратные подходы. В случае аппаратного исполнения некоторые алгоритмы, которые, с математической точки зрения, никогда не могут достичь линейного времени исполнения в стандартных моделях вычислений, могут работать за линейное время. Существуют некоторые аппаратные технологии, которые используют параллельность для достижения такой цели. Примером служит ассоциативная память. Эта концепция линейного времени используется в задачах сопоставления с образцом, таких как алгоритм Бойера — Мура и алгоритм Укконена.
Квазилинейное время Говорят, что алгоритм работает за квазилинейное время, если для некоторой константы . При говорят о линейно-логарифмическом времени. В терминах soft-O такое время работы записывается как . Для алгоритмов с квазилинейным временем работы также верна оценка для любого . Таким образом, эти алгоритмы работают быстрее любого полинома от , степень которого больше .
Алгоритмы, работающие за квазилинейное время, вдобавок к линейно-логарифмическим алгоритмам, упомянутым выше, включают: Сортировка слиянием на месте: ; Быстрая сортировка: математическое ожидание времени работы вероятностной версии алгоритма лежит в на любом входе, для детерминированной же версии эта оценка верна только в среднем по всем входам; Сортировка кучей, сортировка слиянием, introsort, сортировка с помощью бинарного дерева, плавная сортировка, , и другие: в худшем случае; Быстрое преобразование Фурье: ; Алгоритмы на матрицах Монжа: .
Линейно-логарифмическое время Линейно-логарифмическое является частным случаем квазилинейного времени с показателем на логарифмическом множителе.
Линейно-логарифмическая функция — это функция вида (то есть произведение линейного и логарифмического членов). Говорят, что алгоритм работает за линейно-логарифмическое время, если Sedgewick, R. and Wayne K (2011). Algorithms, 4th Ed . p. 186. Pearson Education, Inc.. Таким образом, линейно-логарифмическая функция растёт быстрее, чем линейная, но медленнее, чем любой многочлен от со степенью, большей .
Во многих случаях время работы является просто результатом выполнения раз операции со временем работы . Например, сортировка с помощью двоичного дерева создаёт двоичное дерево путём вставки в него каждого элемента массива размера один за другим. Поскольку операция вставки в занимает время , общее время выполнения алгоритма будет линейно-логарифмическим.