Понятие о сложности

В предыдущей главе рассматривались проблемы принципиальной

возможности вычислений и были исследованы различные подходы к понятию

вычислимости. При этом не обращалось внимания на ресурсы времени и

памяти. Однако существуют задачи, которые теоретически разрешимы, но

при практической реализации требуют столь больших вычислений, что их

решение практически неосуществимо. Следовательно, принципиальная

алгоритмическая разрешимость ещё не означает практическую

реализуемость. Рассмотрим некоторые характеристики вычислений.

Считаем, что при вычислении мы используем алгоритм.

Различают сложность описания алгоритма и исходных данных, и сложность

применения алгоритма к исходным данным.

Сложность описания алгоритма зависит от выбора того или иного способа

задания алгоритма. Если такой способ выбран (машина Тьюринга,

нормальный алгоритм или рекурсивное задание и т.д.), то под сложностью

алгоритма может быть введена как длина записи алгоритма, так и длина

встречающихся выражений и т.д. Например, для машины Тьюринга её

сложность может быть введена как число букв внешнего и внутреннего

алфавитов.

Введем следующее определение. Говорят, что неотрицательная функция g(n)

есть 0(f(n)) если существует такая постоянная c, что g(n)≤ cf(n) для всех, кроме

конечного (возможно пустого) множества значений n, n∈ {1, 2, 3, …}. В этом

случае записываем: g(n)=0(f(n)).

Сложность исходных данных понимается как длина (размер) их записи. Что

такое размер входа? Всё зависит от того, что является входом. Размером

входа, в общем случае, считают число символов, с помощью которых записан

вход.

Пусть входом является целое число. Считаем, что число представлено в

системе счисления с некоторым фиксированным основанием. В этих

системах число символов, необходимых для представления целого числа n

равно ]logAn[, где А2 – основание системы, а ]х[ обозначает наименьшее

целое q, такое, что qx. Известно, что log≥ ≥ Bn=(log2n)/(log2B), здесь log2B

является константой при фиксированном В. Таким образом, число символов,

необходимых для представления целого числа n есть 0(log2n).

Рассмотрим второй пример. Пусть требуется перемножить квадратные nЧn

матрицы А и В. Ясно, что подходящей мерой сложности исходных данных

будет число пропорциональное l= n2, имея в виду, что для запоминания

отдельного числа (элемента матрицы) выделен определенный объем памяти.

Во многих задачах входом является граф. Граф G=(V, X) можно, например,

задать его матрицей смежностей АG=(aij) размера   VЧ V, где aij=1, если ребро

(vi, vj)∈ X и aij=0 в противном случае. Ясно, что максимальное число

возможных ребер равно М= 2VС=0( V 2). Однако многие графы являются

разреженными, т. е. число их ребер много меньше М. В этом случае лучше

задать граф перечислением его ребер, с помощью списков смежностей.

При задании списков смежностей для каждой вершины v∈ V выписывается

множество А(v) (А(v)⊆ V) вершин, смежных с v, см. Рис. 7.1.

Размер этого представления зависит от суммы длин списков. Каждое ребро

вносит вершину в два списка, поэтому сумма длин списков содержит 2 X

элементов. Но для различения вершин, как правило, вводятся числовые

индексы. Так как имеется  V вершин, то для индексов потребуется 0(log2 V)

двоичных или десятичных разрядов. Следовательно, при таком

представлении графа G=(V, X) потребуется 0( X log2 V) символов.

Более экономной записью информации в ячейках памяти ЭВМ (выделенного

для одного числа) можно добиться, что для задания графа G=(V, X) требуется

0( X) ячеек памяти.

Сложность вычислений с помощью алгоритма понимается как функция от

размера входа алгоритма. Для оценки сложности вычислений существует

много критериев. Важными критериями являются: временная сложность,

характеризующая время, затраченное на вычисление, и ёмкостная

Рис. 7.1.

А(v1)={v2, v4};

А(v2)={v1, v3, v4};

А(v3)={v2, v4};

А(v4)={v1, v2, v3}.

v2 (Рисунок: четыре кружочка. Каждый связан с соседним)v1v3 v4

(ленточная) сложность, характеризующая необходимую для вычисления

память, используемую для хранения промежуточных результатов.

Кроме того, сложность вычислений зависит от способа формулировки задачи.

В качестве примера рассмотрим следующую задачу. Требуется узнать,

является ли натуральное число n простым или составным. Чтобы

анализировать сложность задачи надо выяснить, как задано число n. Если n

задано как произведение своих простых делителей: n=(, …,

(k)p1k1n)p(22kn)prrki≥ 0, то задачи нет вообще; если n задано в унарной

форме, т.е. n=11…1, то сложность записи равна l=n (числу единиц), а

сложность задачи, как можно показать, равна l=n(если использовать

известный способ решения этой задачи – решето Эратосфена, состоящий в

том, что число N последовательно делят на простые числа p1, p2, …, p. Если ни

на одно из этих чисел N не делится, то оно простое, иначе составное). Если

число n записано в десятичной форме, то сложность записи числа (длина

записи) равна l=log10n, а сложность решения в этом случае равна =2l/2, т.е.

сложность решения представляет собой экспоненту от длины записи числа n.

Следует обратить внимание на то обстоятельство, что одной и той же задаче

могут соответствовать разные языки, представляющие условия или входные

данные задачи. Это связано со способами кодировки данных. Из всех языков

представляющих исходную задачу, выбирается «разумный язык» или

разумный способ кодировки её условий. Таким образом, каждой задаче

соответствует “разумный язык” её представляющий.

Tcp.

N

Tmax