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

Размер этого представления зависит от суммы длин списков, Каждое ребро вносит вершину в два списка, поэтому сумма длин спи­ сков содержит l\x\ элементов, Но для различения вершин, как пра­ вило, вводятся числовые индексы. Так как имеется 1 v\ вершин, то для индексов потребуется 0(log21 v\) двоичных или десятичных раз­ рядов. Следовательно, при таком представлении графа G={V,X) потре­ буется 0( 1ZI log21 К1) символов. Более экономной записью информации в ячейках памяти ЭВМ (выделенного для одного числа) можно добиться, что для задания графа G=(V,X) требуется 0( |z|) ячеек памяти. Сложность вычислений с помощью алгоритма понимается как функция от размера входа алгоритма. Для оценки сложности вычислений существует много критериев. Важными критериями яв­ ляются: временная сложность, характеризующая время, затраченное на вычисление, и емкостная (ленточная) сложность, ха­ рактеризующая необходимую для вычисления память, используемую для хранения промежуточных результатов. Кроме того, сложность вычислений зависит от способа форму­ лировки задачи. В качестве примера рассмотрим следующую задачу. Требуется узнать, является ли натуральное число п простым или составным. Чтобы анализировать сложность задачи, надо выяснить, как задано чис;ю п. Если п задано как произведение своих простых делителей; n = {p\f^{p2)''^-{pr)\ О, то задачи нет вообще. Следует обратить внимание на то обстоятельство, что одной и той же задаче могут соответствовать разные языки, представляющие условия или входные данные задачи. Это связано со способами коди­ ровки данных. Из всех языков, представляющих исходную задачу, выбирается «разумный язык» или разумный способ кодировки ее ус­ ловий. Таким образом, каждой задаче соответствует "разумный язык", ее представляющий. 278