Временная сложность алгоритма
время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Временная сложность алгоритма?
Кратко изложите эту статью для 10-летнего ребёнка
В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе[1]. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число , такое, что время работы алгоритма для всех входов длины
не превосходит
, то временную сложность данного алгоритма можно асимптотически оценить как
.
Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как . В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации. Так как время работы алгоритма может отличаться на входах одного и того же размера, обычно используется время работы в худшем случае, которое обозначается как
и определяется как наибольшее по всем входным данным длины
время работы алгоритма. Реже, и это обычно оговаривается специально, вычисляется средняя сложность[англ.], то есть математическое ожидание времени работы по всем возможным входам. Время работы алгоритма может быть классифицировано в зависимости от того, какая функция находится под О-нотацией. Например, алгоритм с
называют алгоритмом с линейным временем работы, а алгоритм с
для некоторого
называют полиномиальным.