Описание тега time-complexity

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

При таком выражении считается, что временная сложность описывается асимптотически, т. Е. Когда размер ввода стремится к бесконечности. Например, если время, необходимое алгоритму для всех входов размера n, не превышает5n^3 + 3n, асимптотическая временная сложность равна O(n^3).

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

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

Например, алгоритм с T(n) = O(n)называется алгоритмом линейного времени, а алгоритм сT(n) = O(2^n)называется алгоритмом экспоненциального времени.

Полезные ссылки:

• Сложность времени (Википедия)
• Как найти временную сложность алгоритма
• Временные сложности классических алгоритмов

Связанные теги: теория сложности