Русская Википедия:Худший случай сложности
В информатике (особенно в теории сложности вычислений), худший случай сложности (он обозначается Big-oh(n)) измеряет ресурсы (например, время выполнения, память), которые требуются алгоритму для обработки входных данных случайного размера (обычно обозначаемого Шаблон:Mvar в асимптотическом обозначении). Он обозначает верхнюю границу ресурсов, требуемых алгоритму.
В случае со временем выполнения, худший случай временной сложности алгоритма обозначает самое долгое время выполнения требуемое алгоритму для обработки любого размера входных данных Шаблон:Mvar, тем самым гарантируя, что алгоритм выполнится в обозначенный период времени. Порядок роста (например, линейный, логарифмический) худшего случая сложности обычно используется для сравнения эффективности двух алгоритмов.
Худший случай сложности алгоритма следует противопоставлять с его средним случаем сложности, который обозначает усредненное количество ресурсов, требуемых алгоритму для обработки данных случайного размера.
Определение
Дана модель вычислений и алгоритм <math>\mathsf{A}</math>, который останавливается на каждом входе <math>s</math>, соответствие <math>t_{\mathsf{A}} \colon \{0, 1\}^\star \to \N</math> называется временной сложностью алгоритма <math>\mathsf{A}</math> если, для каждой входной строки <math>s</math>, <math>\mathsf{A}</math> останавливается точно после <math>t_{\mathsf{A}}(s)</math> шагов.
Так как нас обычно интересует зависимость временной сложности алгоритма на входных данных различной длины, злоупотребляя терминологий, временной сложностью алгоритма иногда называют соответствие <math>t_{\mathsf{A}} \colon \N \to \N</math>, определяемое максимальной сложностью
- <math>t_{\mathsf{A}}(n) := \max_{s\in \{0, 1\}^n} t_{\mathsf{A}}(s)</math>
входных данных <math>s</math> длиной или размером <math>\le n</math>.
Подобные определения могут быть даны пространственной сложности.
Способы формулировки
Очень часто, сложность <math>t_{\mathsf{A}}</math> алгоритма <math>\mathsf{A}</math> дана в асимптотическом Big-O обозначении, которое обозначает его рост в форме <math>t_{\mathsf{A}} = O(g(n))</math> с функцией сравнения использующей конкретные вещественные значения <math>g(n)</math> и обозначением:
- Существует позитивное вещественное число <math>M</math> и натуральное число <math>n_0</math> такие, что
- <math>|t_{\mathsf{A}}(n)| \le M g(n) \quad \text{ для всех } n\ge n_0.</math>
Довольно часто, формулировка звучит следующим образом:
- „Алгоритм <math>\mathsf{A}</math> имеет худший случай сложности <math>O(g(n))</math>.“
или еще короче:
- „Алгоритм <math>\mathsf{A}</math> имеет сложность <math>O(g(n))</math>.“
Примеры
Рассмотрим выполнение алгоритма сортировки вставками на <math>n</math> числах с использованием машины с произвольным доступом к памяти. В лучшем случае для алгоритма, когда числа уже отсортированы, требуется <math>O(n)</math> шагов для выполнения задачи. Однако, в худшем случае для алгоритма, когда числа отсортированы в обратном порядке, требуется <math>O(n^2)</math> шагов для их сортировки; таким образом худший случай временной сложности алгоритма сортировки вставками <math>O(n^2)</math>.
См. также
Ссылки
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. Шаблон:ISBN. Chapter 2.2: Analyzing algorithms, pp.25-27.
- Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. Шаблон:ISBN, p.32.
