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

входа, в общем случае, считают число символов, с помощью которых записан вход. Пусть входом является целое число. Считаем, что число представлено в системе счисления с некоторым фиксированным основанием. В этих системах число символов, необходимых для представления целого числа п равно ]logAn[, где А>2 - основание системы, а ]х[ обозначает наименьшее целое q, такое, что q>x. Известно, что logAn=(log2n)/(log2A), здесь log2A является константой при фиксированном А. Таким образом, число символов, необходимых для представления целого числа п есть 0(log2n). Так, например, для записи числа 100 в системе счисления с основанием^ понадобится: е с ли^ = 2, то нужно 7 символов (log 2100 = 6,65): 100io= IIOOIOO2; е с ли^ = 4, то нужно 4 символа (log 4100 = 3,32): 100io= I2IO4; е с ли^ = 8, то нужно 3 символа (log 8 ЮО = 2,22): 100io= 1448; е с ли^ = 16, то нужно 2 символа (log 16100 = 1,67): 100io= 64i6. Рассмотрим случай, когда требуется перемножить квадратные пхп матрицы ^ и 5 . Ясно, что подходящей мерой сложности исходных данных будет число, пропорциональное / = п^, имеется в виду, что для запоминания отдельного числа (элемента матрицы) выделен определенный объем памяти. Во многих задачах входом является граф. Граф G=(V,X) можно, например, задать его матрицей смежностей Ао=(ау) размера \v \x 1И , где aij=l, если ребро (Vi,Vj)E X и aij=0 в противном случае. Ясно, что максимальное число возможных ребер равно М= =0( \ Однако многие графы являются разреженными, т. е. число их ребер много меньше М. В этом случае граф лучше задать перечислением его ребер с помощью списков смежностей. При задании списков смежностей для каждой вершины VE V выписывается множество (A(v)cV) вершин, смежных с v, см. Рис. 7.2. A(VI)={V2, V4}; A(V2)={VI, V3, V4}; A(V3)={V2, V4}; A( V4)={VJ, V2, V3}. Рис. 7.2 Размер этого представления зависит от суммы длин списков. Каждое ребро вносит вершину в два списка, поэтому сумма длин списков содержит2 к | элементов. По для различения вершин, как правило, вводятся числовые индексы. Так как имеется | v\ вершин, то для индексов потребуется 0(log2 \v\) ДВОИЧНЫХ или десятичных разрядов. Следовательно, при таком представлении графа G=(V,X) потребуется log2 \v\) символов. 219