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