Математическая логика и теория алгоритмов

§ 2. Временная сложность вычислений (алгоритма) Временная сложность вычислений (алгоритма) характеризует число операций для решения задачи заданного размера, При решении однотипных задач с одинаковым размером входа может потребоваться различное число итераций для решения отдель­ ных задач (этого типа), следовательно, и различное число операций. Определим временнуюсложностьалгоритма как число опера­ ций в худшем случае по всем входам размера (длины) п. Кроме меры сложности, в наихудшем с;гучае вводят в р е м е н н у ю сложностьалгоритма А в среднем на входе размера п: МА(П)= S р(д,)ц(Л(й,)), здесь р(а,) - вероятность появления задачи [д,(/4(а()) - число операций, затрачиваемых алгоритмом на решение индивидуальной задачи а,; Р„ ~ множество рассматриваемых задач размера п, Р„={ а,}. При изучении сложности алгоритма в основном интересуются его поведением при применении его к очень большим входам. Разли­ чие меисду сложностями и 9п^ считаются несущественными, бо­ лее важен показатель степени, а не коэффициент. Сложность алгорит­ ма оценивается асимптотической сложностью, т.е. порядком роста числа операций при неограниченном росте размера входа. Например, если вход размера п обрабатывается за время сг?, где с - некоторая постоянная, то сложность этого алгоритма есть 0(?г^), т.е. постоянная с не содержится в оценке. Для практических задач величина этого ко­ эффициента может быть важна, если они различаются существенно. Если время работы алгоритмов А1 и А2 пропорционально, например, и 9/7^ соответственно, то практическое использование алгоритма А1 проблематично. Для решение выбранной задачи иногда можно использовать различные алгоритмы. 279