Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Более экономной записью информации в ячейках памяти ЭВМ (выделен­ ного для одного числа) можно добиться, что для задания графа G=(V,X) требу­ ется о(\х\) ячеек памяти. Следует обратить внимание на то обстоятельство, что одной и той же зада­ че могут соответствовать разные языки, представляющие условия или входные данные задачи. Это связано со способами кодировки данных. Из всех языков, представляющих исходную задачу, выбирается «разумный язык» или разумный способ кодировки её условий. Таким образом, каждой задаче соответствует "разумный язык", её представляющий. § 2. Временная сложность вычислений (алгоритма) Временная сложность вычислений (алгоритма) характеризует число опе­ раций для решения задачи заданного размера. При решении однотипных задач с одинаковым размером входа может по­ требоваться различное число итераций для решения отдельных задач (этого ти­ па), следовательно, и различное число операций. Определим временную сложность алгоритма как число операций в худ­ шем случае по всем входам размера (длины) п. Кроме меры сложности, в наихудшем случае вводят временную сложность алгоритма А в среднем на входе размера п\ МА(П)= S P(AI)/J.(A(AI)), здесь р(а) - вероятность появления задачи а^; ju(A(ai)) - число операций, затрачиваемых алгоритмом на решение индивидуальной задачи af, Рп - множе­ ство рассматриваемых задач размера п, Рп={ аJ. При изучении сложности алгоритма в основном интересуются его поведе­ нием при применении его к очень большим входам. Различие между сложно- 3 3 стями 10п и 9п считаются несущественными, более важен показатель степени, а не коэффициент. Сложность алгоритма оценивается асимптотической слож­ ностью, т.е. порядком роста числа операций при неограниченном росте размера входа. Например, если вход размера п обрабатывается за время сп , где с - не- которая постоянная, то сложность этого алгоритма есть 0(п ), т.е. постоянная с не содержится в оценке. Для практических задач величина этого коэффициента может быть важна, если они различаются существенно. Если время работы ал- 10 2 2 горитмов и А 2 пропорционально, например, 10 п и 9п соответственно, то практическое использование алгоритма^ 7 проблематично. Для решения выбранной задачи иногда можно использовать различные ал­ горитмы. Под временной сложностью задачи понимается временная сложность наи­ лучшего алгоритма, известного для ее решения. Выясним, как изменяется эффективность различных алгоритмов с ростом быстродействия ЭВМ, на которых реализуются эти алгоритмы. 220