Loading AI tools
Из Википедии, свободной энциклопедии
В информатике (особенно в теории сложности вычислений), худший случай сложности (он обозначается Big-oh(n)) измеряет ресурсы (например, время выполнения, память), которые требуются алгоритму для обработки входных данных случайного размера (обычно обозначаемого n в асимптотическом обозначении). Он обозначает верхнюю границу ресурсов, требуемых алгоритму.
В случае со временем выполнения, худший случай временной сложности алгоритма обозначает самое долгое время выполнения требуемое алгоритму для обработки любого размера входных данных n, тем самым гарантируя, что алгоритм выполнится в обозначенный период времени. Порядок роста (например, линейный, логарифмический) худшего случая сложности обычно используется для сравнения эффективности двух алгоритмов.
Худший случай сложности алгоритма следует противопоставлять с его средним случаем сложности, который обозначает усредненное количество ресурсов, требуемых алгоритму для обработки данных случайного размера.
Дана модель вычислений и алгоритм , который останавливается на каждом входе , соответствие называется временной сложностью алгоритма если, для каждой входной строки , останавливается точно после шагов.
Так как нас обычно интересует зависимость временной сложности алгоритма на входных данных различной длины, злоупотребляя терминологий, временной сложностью алгоритма иногда называют соответствие , определяемое максимальной сложностью
входных данных длиной или размером .
Подобные определения могут быть даны пространственной сложности.
Очень часто, сложность алгоритма дана в асимптотическом Big-O обозначении, которое обозначает его рост в форме с функцией сравнения использующей конкретные вещественные значения и обозначением:
Довольно часто, формулировка звучит следующим образом:
или еще короче:
Рассмотрим выполнение алгоритма сортировки вставками на числах с использованием машины с произвольным доступом к памяти. В лучшем случае для алгоритма, когда числа уже отсортированы, требуется шагов для выполнения задачи. Однако, в худшем случае для алгоритма, когда числа отсортированы в обратном порядке, требуется шагов для их сортировки; таким образом худший случай временной сложности алгоритма сортировки вставками .
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.