Википедия

Вычислительная сложность: различия между версиями

Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[отпатрулированная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
→‎Замечания: -не отн. к теме
Строка 19:
Несмотря на то, что функция временной сложности алгоритма в некоторых случаях может быть определена точно, в большинстве случаев искать точное её значение бессмысленно. Дело в том, что во-первых, точное значение временной сложности зависит от определения ''элементарных операций'' (например, сложность можно измерять в количестве [[арифметика|арифметических]] операций, [[Сложность вычисления (битовая)|битовых]] операций или операций на [[машина Тьюринга|машине Тьюринга]]), а во-вторых, при увеличении размера входных данных вклад постоянных множителей и слагаемых низших порядков, фигурирующих в выражении для точного времени работы, становится крайне незначительным.
 
Рассмотрение входных данных большого размера и оценка [[порядок роста|порядка роста]] времени работы алгоритма приводят к понятию '''асимптотической сложности''' алгоритма. При этом алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных, за исключением лишь, возможно, данных малого размера. Для записи асимптотической сложности алгоритмов используются [[«O» большое и «o» малое|асимптотические обозначения]]:<!-- !асимптотические обозначения -->
 
{|class="wikitable"
!Обозначение
!Интуитивное объяснение
!Определение
<!-- !асимптотические обозначения -->
|-
|<math>f(n) \in O(g(n))</math>
|<math>f</math> ограничена сверху функцией <math>g</math> (с точностью до постоянного множителя) асимптотически
|<math>\exists (C>0), n_0 : \forall(n>n_0) \; |f(n)| \leq |Cg(n)| </math> или <math> \exists (C>0), n_0 : \forall(n>n_0) \; f(n) \leq Cg(n)</math>
|-
|<math>f(n) \in \Omega(g(n))</math>
|<math>f</math> ограничена снизу функцией <math>g</math> (с точностью до постоянного множителя) асимптотически
|<math>\exists (C>0), n_0 : \forall (n>n_0) \; |Cg(n)| \leq |f(n)|</math>
|-
|<math>f(n) \in \Theta(g(n))</math>
|<math>f</math> ограничена снизу и сверху функцией <math>g</math> асимптотически
|<math>\exists (C,C'>0), n_0 : \forall (n>n_0) \; |Cg(n)| \leq |f(n)| \leq |C'g(n)| </math>
|-
|<math>f(n) \in o(g(n))</math>
|<math>g</math> доминирует над <math>f</math> асимптотически
|<math>\forall (C>0),\exists n_0 : \forall(n>n_0) \; |f(n)| < |Cg(n)|</math>
|-
|<math>f(n) \in \omega(g(n))</math>
|<math>f</math> доминирует над <math>g</math> асимптотически
|<math>\forall (C>0),\exists n_0 : \forall(n>n_0) \; |Cg(n)| < |f(n)|</math>
|-
|<math>f(n) \sim g(n)</math>
|<math>f</math> эквивалентна <math>g</math> асимптотически
|<math>\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1</math>
|}
 
=== Примеры ===
* '''«почистить ковёр пылесосом»''' требует время, линейно зависящее от его площади (<math>\Theta(A)</math>), то есть на ковёр, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз объём работы увеличивается [[Пропорция (математика)|строго пропорционально]] в сто тысяч раз, и т. п.
Источник — https://ru.wikipedia.org/wiki/Вычислительная_сложность