§ 3. Асимптотические оценки (два примера)

29

Начав вояж из вершины с номером v, мы смотрим, не пуст ли спи­сок a_v: если он пуст, то вояж закончен. Если же список a_v не пуст, пе­реносим первый его элемент (пусть это будет, например, i) в список вершин, через которые шаг за шагом проходит вояж; затем рассмат­риваем список a_i, если он пуст, то вояж закончен, иначе повторяем все то же самое, что проделывали в предыдущей вершине, и т.д.:

l := cons(v, nil); i := v;

while not null(a_i) do i := car(a_i); l := cons(i, l); a_i := cdr(a_i) od

Мы здесь использовали операции над списками, применяемые в язы­ке Лисп: car — первый элемент списка, cdr — список после удале­ния первого его элемента, cons —вставка элемента в начало списка, null —предикат проверки пустоты списка, nil —обозначение пустого списка.

Затраты, связанные с удлинением пути на один шаг и с проверкой, не завершен ли вояж, ограничены сверху константой (эти затраты суть четыре операции над списками), длина всего пути не превос­ходит | E |, и затраты во всех случаях не превосходят произведения некоторой константы на | E |.

Список l содержит в обратном порядке все вершины, через кото­рые последовательно проходит вояж. Если желателен прямой поря­док, то надо перевернуть l:

l^′ := nil;

while not null(l) do l^′ := cons(car(l), l^′); l := cdr(l) od

Построение списка l^′ потребует некоторых дополнительных опера­ций над списками, число этих операций не превзойдет произведения некоторой константы c на длину списка l, но эта длина не превосхо­дит | E |, следовательно, число операций на этом этапе не превзойдет

с\Е\.

V

Естественно считать пространственные затраты на хранение спис­ка с числовыми элементами пропорциональными длине списка. В случае, например, графа в виде кольца каждый из списков l и l^′ имеет длину |E|+1.

Обозначим буквами VL описанный алгоритм построения вояжа, предполагая, что исходный ориентированный граф задается масси­вом списков смежных вершин. Из сказанного следует, что для вре­менных затрат алгоритма VL мы имеем

C^(G,v)^c\E\,

(3.2)

30 Глава 1. Сложности алгоритмов как функции числовых аргументов

где c—некоторая константа. Это неравенство выполнено для любого имеющего |E| ребер графа. Поэтому если значение |E| принято за размер входа (напомним, что сам вход—это граф и выделенная в нем вершина), то из (3.2) будет следовать T^(.\E\) ^c\E\, откуда

T_VL(|E|) = O(|E|). (3.3)

Вместе с указанной ранее оценкой П(\E\) оценка (3.3) дает

T_VL(|E|)=e(|E|).

Нетрудно вывести аналогичную оценку и для пространственной сложности.

Если массивы списков смежных вершин используются в качестве представления ориентированных графов, то построение начинающе­гося с заданной вершины v вояжа в графе G = (V, E) возможно с по­мощью алгоритма, который при выборе числа \E\ ребер в качестве размера входа имеет сложность 6(|E |) по числу операций над списка­ми. Эта же оценка имеет место для пространственной сложности, если считать, что пространственные затраты на хранение списка с числовыми элементами пропорциональны длине этого списка.

Если бы граф представлялся матрицей смежности, то мы для ис­пользуемого алгоритма не смогли бы получить оценку сложности 6(|E|), так как при блуждании по графу вход в каждую вершину сопровождается проверкой, есть ли непройденное до сих пор реб­ро, выходящее из этой вершины. Например, для графа в виде кольца при \E| = |V| = n мы имеем матрицу смежности порядка n:

[О 1 0 ... (Л 0 0 1 ... 0

0 0 0 ... 1

1 0 0 ... О

Начиная вояж из первой вершины, мы потратим 2 + 3 + ... + n + 1 = = П(n²) сравнений элементов матрицы с единицей при поиске первых подходящих вершин.

Разумеется, базовые операции над списками и операции сравне­ния элементов матрицы смежности с единицей различаются по за­тратности (сравнение с единицей—это очень дешевая операция). Но какими бы ни были положительные c' и c", отражающие затраты на операцию сравнения с 1 и, соответственно, на операцию над спис­ком, неравенство c'\E \² > c"\E | будет иметь место для всех достаточно