Временная сложность

Временная сложность (Time complexity) — основной параметр, характеризующий алгоритм; определяется как число шагов, выполняемых алгоритмом в худшем случае, обычно рассматривается как функция размера задачи, представленной входными данными. Обычно под размером теоретико-графовой задачи понимается число вершин графа [math]\displaystyle{ n }[/math], число дуг [math]\displaystyle{ m }[/math] или пара [math]\displaystyle{ (n,m) }[/math]. Под шагом алгоритма понимается выполнение одной из команд некоторой гипотетической машины. Поскольку при таком определении шага сложность алгоритма зависит от конкретного вида машинных команд, во внимание принимается асимптотическая сложность, т.е. асимптотическая скорость увеличения числа шагов алгоритма, когда размерность задачи неограниченно растет. Ясно, что при двух произвольных "разумных" способах перевода алгоритма в последовательность машинных команд соответствующие сложности различаются не более чем на мультипликативную константу, а их скорость роста одинакова.

При сравнении скорости роста двух функций [math]\displaystyle{ f(n) }[/math] и [math]\displaystyle{ g(n) }[/math] используются следующие обозначения:

[math]\displaystyle{ f(n) = O(g(n)) \Longleftrightarrow }[/math] существуют константы [math]\displaystyle{ C, }[/math] [math]\displaystyle{ N \gt 0 }[/math] такие, что [math]\displaystyle{ f(n) \leq C \cdot g(n) }[/math] для всех [math]\displaystyle{ n \geq N }[/math];

[math]\displaystyle{ f(n) = \Omega(g(n)) \Longleftrightarrow }[/math] существуют константы [math]\displaystyle{ C, }[/math] [math]\displaystyle{ N \gt 0 }[/math] такие, что [math]\displaystyle{ f(n) \geq C \cdot g(n) }[/math] для всех [math]\displaystyle{ n \geq N. }[/math]

Другое название — Вычислительная сложность.

См. также

• Сложность РАМ.

Литература

• Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
• Липский В. Комбинаторика для программистов. — М.: Мир, 1988.
• Касьянов В.Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003
• Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: НГУ, 2018.