ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->Листинг 5.15. Программа нахождения НОП

Алгоритмы структуры данных

Листинг 5.15. Программа нахождения НОП

procedure НОП;

begin

(1)    инициализация So= {О, 1, ..., n} и Sk= 0 для k от 1 до n;

(2)    for j:= 1 to n do { вычисление всех Sk для позиции j }

(3)        for наибольшее число r є PLACES (bj) do begin

(4)            k:= FIND(r);

(5)            if k:= FIND(r-l) then begin

(6)                 SPLIT (Sk, Sk, S'k, r);

(7)                 MERGE (S'k, S'k+1, S'k+1)

end

end

end; { НОП }

Анализ времени выполнения алгоритма нахождения НОП

Как упоминалось ранее, описываемый алгоритм целесообразно применять тогда, когда между элементами рассматриваемых последовательностей не очень много совпадений. Число совпадений можно подсчитать по формуле |PLACES(bj) |, где |PLACES(bj)| обозначает число элементов в множестве PLACES(bj). Другими словами, р — это сумма по всем bt количества позиций в первой последовательности, совпадающих c--bj. Напомним, что при сравнении файлов мы ожидали, что р имеет такой порядок, как длины сравниваемых последовательностей (файлов) тип.

Оказывается, что 2-3 деревья*— подходящая структура для множеств Sk. Мы можем инициализировать эти множества (строка (1) в листинге 5.15) за О(п) шагов. Для реализации функции FIND необходим массив, осуществляющий отображение из множества позиций в множество листьев дерева, а также указатели на родителей узлов в 2-3 дереве. Имя множества, т.е. k для множества Sk, можно хранить в корне дерева. В этом случае оператор FIND можно выполнить за время O(logn), следуя за указателями от листа дерева к его корню. Поэтому все выполнения строк (4) и (5) в листинге 5.15 в совокупности требуют времени порядка О(р logn.).

Выполняемый в строке (5) оператор MERGE обладает тем свойством, что каждый элемент в множестве S'k меньше, чем любой элемент в множестве Sk+1, и мы можем воспользоваться этим, применяя 2-3 деревьев для реализации данного оператора1. Вначале оператор MERGE помещает 2-3 дерево множества S'k слева от дерева множества k+1. Если оба дерева имеют одинаковую высоту, то создается новый корень, сыновьями которого являются корни этих MERGE деревьев. Если дерево множества S'k короче дерева множества Sk+1, то корень дерева множества S'k становится самым левым сыном самого левого узла.на соответствующем уровне дерева множества Sk+1. Если после этого узел будет иметь четырех сыновей, то дерево модифицируется точно так же, как и при выполнении процедуры INSERT из листинга 5.11. Пример подобного объединения деревьев показан на рис. 5.15. Аналогично, если дерево множества Sk+1короче дерева множества S'k, то корень дерева множества Sk+1 становится самым правым сыном самого правого узла на соответствующем уровне дерева множества S'k.

Оператор SPLIT, разбивающий множество по элементу r, осуществляет проход по дереву от листа, содержащего г, к корню дерева, дублируя по пути все внутренние узлы, расположенные на пути, и отдавая эти копии узлов двум результирующим деревьям. Узлы, не имеющие сыновей, исключаются из дерева, а узлы, имеющие по одному сыну, удаляются, вставляя своего сына на соответствующий уровень дерева.

Пример 5.9. Предположим, необходимо разбить дерево, изображенное на рис. 5.15,6, по узлу 9. Два дерева с дубликатами узлов, расположенных на пути от листа 9 к корню, показаны на рис. 5.16,а. На дереве слева родитель листа 8 имеет только одного сына, поэтому лист 8 становится сыном родителя узлов 6 и 7. Этот родитель теперь имеет трех сыновей, поэтому все в порядке. Если бы он имел четырех сыновей, то потребовалось бы создать новый узел и вставить его в дерево. Теперь надо удалить узлы без сыновей (старый родитель листа 8) и цепочку из узлов с одним сыном, ведущую к корню дерева. После этих удалений родитель листьев 6, 7 и 8 становится корнем дерева, как показано на рис. 5.16,6. Аналогично, на правом дереве рис. 5.16,а лист 9 становится левым братом листьев 10 и 11, лишние узлы удаляются, в результате получаем дерево, показанное на рис. 5.16,6.

Если операция разбиения деревьев и последующая их реорганизация происходят так, как описано выше, то можно показать, что в большинстве случаев для выполнения оператора SPLIT потребуется не более O(logn) шагов. Таким образом, общее время выполнения строк (6) и (7) в листинге 5.15 требует О(р logra) шагов. Еще необходимо учесть время, затрачиваемое перед выполнением процедуры НОП на вычисление и сортировку множеств PLACES(a) для всех элементов а. Как уже упоминалось, если элементы а — "большие" объекты (например, текстовые строки), то это время может быть больше времени, необходимого на реализацию любой части описываемого алгоритма.

Как будет показано в главе 8, если манипулирование и сравнение элементов можно "уложить" в единичные "шаги", то на сортировку первой последовательности a1a2...ап потребуется порядка О(п logn) таких шагов, после чего PLACES(a) может быть считан из списка за время О(n). В итоге получаем, что длину НОП можно подсчитать за время порядка О(тах(n, р) logn), которое (поскольку обычно р ≥ п) можно принять как О(р logn).

 

 

83