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

Сложностьисходныхданных понимается как длина (размер) их записи. Что такое размер входа? Все зависит от того, что является входом. Размером входа, в общем случае, считают число символов, с помощью которых записан вход. Пусть входом является целое число. Считаем, что число пред­ ставлено в системе счисления с некоторым фиксированным основани­ ем. В этих системах число символов, необходимых для представления целого числа п, равно ]logx! «[, где А > 2 - основание системы, а ]л:[ обозначает наименьшее целое q, такое, что q > x . Известно, что logB?^=(bg2n)/(Iog2/^), здесь log2^ является константой при фиксиро­ ванном А . Таким образом, число символов, необходимых для пред­ ставления целого числа п есть 0(log2 «). Рассмотрим второй пример. Пусть требуется перемножить квад­ ратные ПУ.П матрицы А я В. Ясно, что подходящей мерой сложности исходных данных будет число, пропорциональное I = п^, имеется в виду, что для запоминания отдельного числа (элемента матрицы) выделен определенный объем памяти. Во многих задачах входом является граф. Граф G-{V,X) можно, например, задать его матрицей смежностей Ас;=(а,у) размера | к1 х 1т1, где a ,j =l> если ребро (vi,vj)e X и в противном случае. Ясно, что максимальное число возможных ребер равно М - С|^|=0(1кР), Однако многие графы являются разреженными, т. е. число их ребер много меньше М В этом случае лучше задать граф перечислением его ребер, с помощью списковсмежностей. При задании списков смежностей для каждой вершины v e V выписывается множество A(v) ( A ( v ) a V ) вершин, смежных с V (рис. 7.1). ^ ( V l ) = { V 2 , V 4 } ; ^ ( V 2 ) = { V b V3, V4}; -4(V3)={V2, V 4 } ; ^ ( V 4 ) = { V b V2, V3}. Рис, 7,1 277