временная сложность алгоритма

В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число , такое, что время работы алгоритма для всех входов длины не превосходит , то временную сложность данного алгоритма можно асимптотически оценить как . Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как . В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации. Так как время работы алгоритма может отличаться на входах одного и того же размера, обычно используется , которое обозначается как и определяется как наибольшее по всем входным данным длины время работы алгоритма. Реже, и это обычно оговаривается специально, вычисляется , то есть математическое ожидание времени работы по всем возможным входам. Время работы алгоритма может быть классифицировано в зависимости от того, какая функция находится под О-нотацией. Например, алгоритм с называют алгоритмом с линейным временем работы, а алгоритм с для некоторого называют полиномиальным.