Временная сложность: различия между версиями
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| (не показаны 4 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
'''Временная сложность'''([[Time complexity | '''Временная сложность''' (''[[Time complexity]]'') — основной параметр, характеризующий [[алгоритм]]; определяется как число шагов, выполняемых алгоритмом в худшем случае, обычно рассматривается | ||
как функция размера задачи, представленной входными данными. Обычно под ''размером'' теоретико-графовой задачи понимается число вершин графа <math>n</math>, число дуг <math>m</math> или пара <math>(n,m)</math>. Под шагом алгоритма понимается выполнение одной из команд некоторой гипотетической машины. Поскольку при таком определении шага сложность алгоритма зависит от конкретного вида машинных команд, во внимание принимается асимптотическая сложность, т.е. асимптотическая скорость увеличения числа шагов алгоритма, когда размерность задачи неограниченно растет. Ясно, что при двух произвольных "разумных" способах перевода алгоритма в последовательность машинных команд соответствующие сложности различаются не более чем на мультипликативную константу, а их скорость роста одинакова. | как функция размера задачи, представленной входными данными. Обычно под ''размером'' теоретико-графовой задачи понимается число [[вершина|вершин]] [[граф|графа]] <math>n</math>, число [[дуга|дуг]] <math>m</math> или пара <math>(n,m)</math>. Под шагом алгоритма понимается выполнение одной из команд некоторой гипотетической машины. Поскольку при таком определении шага [[сложность алгоритма]] зависит от конкретного вида машинных команд, во внимание принимается асимптотическая сложность, т.е. асимптотическая скорость увеличения числа шагов алгоритма, когда размерность задачи неограниченно растет. Ясно, что при двух произвольных "разумных" способах перевода алгоритма в последовательность машинных команд соответствующие сложности различаются не более чем на мультипликативную константу, а их скорость роста одинакова. | ||
При сравнении скорости роста двух функций <math>f(n)</math> и <math>g(n)</math> используются | При сравнении скорости роста двух функций <math>f(n)</math> и <math>g(n)</math> используются | ||
| Строка 8: | Строка 8: | ||
f(n) = O(g(n)) \Longleftrightarrow </math> | f(n) = O(g(n)) \Longleftrightarrow </math> | ||
существуют константы | существуют константы | ||
<math> C, N > 0 </math> такие, что | <math> C, </math> <math> N > 0 </math> такие, что | ||
<math> f(n) \leq C \cdot g(n) </math> для всех <math> n \geq N </math>; | <math> f(n) \leq C \cdot g(n) </math> для всех <math> n \geq N </math>; | ||
<math>f(n) = \Omega(g(n)) \Longleftrightarrow </math> | <math>f(n) = \Omega(g(n)) \Longleftrightarrow </math> | ||
существуют константы <math> C, N > 0 </math> такие, что | существуют константы <math> C,</math> <math> N > 0 </math> такие, что | ||
<math> f(n) \geq C \cdot g(n)</math> для всех <math> n \geq N.</math> | <math> f(n) \geq C \cdot g(n)</math> для всех <math> n \geq N.</math> | ||
Другое название | Другое название — ''[[Вычислительная сложность]]''. | ||
==См. также== | ==См. также== | ||
[[Сложность РАМ | * ''[[Сложность РАМ]]''. | ||
==Литература== | ==Литература== | ||
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. | |||
* Липский В. Комбинаторика для программистов. — М.: Мир, 1988. | |||
* Касьянов В.Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003 | |||
* Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: НГУ, 2018. | |||
[ | [[Категория:Теория вычислений]] | ||
Текущая версия от 21:26, 28 октября 2024
Временная сложность (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.