Временная сложность: различия между версиями
KVN (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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> используются | ||
| Строка 15: | Строка 15: | ||
<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. | |||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Липский В. Комбинаторика для программистов. — М.: Мир, 1988. | |||
Версия от 12:30, 30 ноября 2010
Временная сложность(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.
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
- Липский В. Комбинаторика для программистов. — М.: Мир, 1988.