Алгоритм 4.2 нахождения наибольшего и наименьшего элементов множества

Таблица 3. Сравнение по временной сложности трех алгоритмов

Если за размер задачи взять степень полинома, то можно заметить, что алгоритм с возведением в степень имеет сложность O(n^a), алгоритмы Горнера 1.2 и 1.3 - O(n^b), причём a > 1 > b. Поэтому выигрыш по скорости счёта будет тем выше, чем сложнее задача (выше порядок полинома). Если же сравнивать второй и третий алгоритмы, то можно заключить, что они имеют одинаковый порядок временной сложности, но константа c₂ будет больше константы c₃, и третий алгоритм работает быстрее.

1.2. Структуры данных: списки, очереди, стеки

Теперь рассмотрим некоторые структуры данных, которые полезны при разработке эффективных алгоритмов для обширных классов задач.

С математической точки зрения список (List) - это конечная последовательность элементов, взятых из некоторого подходящего множества. Описание алгоритма часто включает в себя некоторый список, к которому добавляются и из которого удаляются элементы. В частности может потребоваться добавить или удалить элемент где-то в середине списка. По этой причине необходимо разработать структуры данных, позволяющие реализовать списки, в которых разрешается удалять и добавлять новые элементы так, как это требуется.

Рассмотрим список:

Unit1; Unit2; Unit3; Unit4. (1.3)

Простейшей его реализацией будет структура последовательно связанных компонент (Linked List), показанная на рисунке 1.

			Рис.1. Список со связями
	First

Каждая компонента в этой структуре состоит из 2-х ячеек памяти. Первая ячейка содержит сам элемент (если этот элемент сам является сложной структурой, то первая ячейка может содержать указатель ее местоположения), вторая - указатель следующего элемента. Такую структуру можно рассматривать в виде двух массивов, которые на рисунке 2 названы Name (Имя) и Next (Следующая). Если Index - индекс в рассматриваемом массиве, то Name[Index] - сам элемент, хранящийся там, а Next[Index] - индекс следующего элемента в списке (если таковой существует). Если же Index - индекс последнего элемента в этом списке, то Next[Index]=0.

Next[0] - указатель на первый элемент в списке. Порядок элементов в массиве Name не совпадает с их порядком в списке. Тем не менее, рисунок 2 дает верное представление списка, изображенного на рисунке 1, так как массив Next располагает элементы в том же порядке, в каком они расположены в списке (1.3).

Создадим программу, вставляющую новую компоненту в список. Будем предполагать, что Free - номер незанятой ячейки в массивах Name и Next, а Position - индекс той компоненты в списке, после которой надлежит вставить новый элемент New_Unit. Тогда:

// Программа 2

void Insert_Element(char New_Unit, unsigned Free, unsigned Position, char *Name, unsigned Next)

{

/* Функция вставляет новый элемент в список типа char на позицию вслед за

элементом с номером Position */

Name[Free]=New_Unit;

Next[Free]=Next[Position];

Next[Position]=Free;

} // Конец Insert_Element

Легко видеть, что время исполнения программы 2 не будет зависеть от размера списка.

Пример 1.2. Допустим, что нужно вставить в список (1.3) New_Unit после Unit2 и получить список

Unit1; Unit2; New_Unit, Unit3; Unit4

Если пятая ячейка в каждом массиве на рисунке 2 пуста, можно вставить New_Unit после Unit2, вызвав Insert_Element(New_Unit, 5, 3, Name, Next). В результате выполнения трёх операторов функции: Name[5]=New_Unit, Next[5]=4 и Next[3]=5. Получатся массивы, показанные на рисунке 3.ð

Для того чтобы удалить компоненту, следующую за компонентой в ячейке с номером Position можно выполнить следующий оператор Next[Position]= Next[Next[Position]]. При желании индекс удаленной компоненты можно поместить в список незанятых ячеек памяти.

Часто в один и тот же массив вкладываются несколько списков. Обычно один из этих списков состоит из незанятых ячеек; его называют свободным списком (Free List). Для добавления элемента к списку A можно так изменить функцию Insert_Element, что незанятая ячейка получалась путем удаления первой ячейки в свободном списке. При удалении элемента из списка A соответствующая ячейка возвращается в свободный список для будущего употребления.

Ещё две основные операции над списками - конкатенация (сцепление, concatenation) двух списков, в результате которой образуется единственный список, и обратная к ней операция расцепления (расщепления, split) списка, стоящего после некоторого элемента, результатом которой будут два списка. Конкатенацию можно выполнить за ограниченное (постоянной величиной) число шагов, включив в представление списка ещё один указатель. Этот указатель даёт индекс последней компоненты списка и тем самым позволяет обойтись без просмотра всего списка для определения его последнего элемента. Расцепление можно сделать за ограниченное (постоянной величиной) время, если известен индекс компоненты, непосредственно предшествующей месту расцепления.

Списки можно сделать проходимыми в обоих направлениях, если добавить ещё один массив, называемый Previous (Предыдущая). Значение Previous[Index] равно ячейке, в которой помещается тот элемент списка, который стоит непосредственно перед элементом из ячейки Index. Список такого рода называется дважды связанным (Doubly Linked List). Из дважды связанного списка можно удалить элемент или вставить в него элемент, не зная ячейку, где находится предыдущий элемент.

Со списком часто работают очень ограниченными приёмами. Например, элементы добавляются или удаляются только на конце списка. Иными словами, элементы вставляются и удаляются по принципу: «последний вошёл - первый вышел» (last-in first-out, LIFO). В этом случае список называют стеком (Stack) или магазином.

Часто стек реализуется в виде одного массива. Например, список

Unit1; Unit2; Unit3

можно хранить в массиве Name, как показано на рисунке 4

	Номер индекса эл-та	Name
Рис. 4. Реализация стека.		Unit1
		Unit2
Top ®		Unit3

Переменная Top (Вершина) является указателем последнего элемента (Top of stack pointer), добавленного к стеку. Чтобы добавить (Затолкнуть – Push) новый элемент в стек значение Top увеличивают на 1, а затем помещают новый элемент в Name[Top]. (Поскольку массив Name имеет конечную длину l, перед попыткой вставить новый элемент следует проверить, что Top<l–1). Чтобы удалить (Вытолкнуть - Pop) элемент из вершины стека, надо просто уменьшить значение Top на 1. Здесь совсем необязательно физически стирать элемент, удаляемый из стека. Чтобы узнать, пуст ли стек, достаточно проверить, не имеет ли Top значение, меньшее нуля. Понятно, что время выполнения операций Push и Pop и проверка пустоты не зависят от числа элементов в стеке.

Другой специальный вид списка - очередь (Queue), т.е. список, в который элементы всегда добавляются с одного (переднего) конца, а удаляются с другого. Как и стек, очередь можно реализовать одним массивом. На рисунке 5 приведена очередь, содержащая список из элементов P, Q, R, S, T. Два указателя обозначают ячейки текущего переднего (Front) и заднего (Back) концов очереди. Чтобы добавить (Append) новый элемент к очереди, как и в случае стека, полагают Front++ и помещают новый элемент в Name[Front]. Чтобы удалить (Strip off) новый элемент из очереди, заменяют Back--. С точки зрения доступа к элементам эта техника основана на принципе «первый вошёл - первый вышел» (first in –first out; FIFO).

	Name
Back ®	P
Рис. 5. Реализация очереди в виде одного массива.	Q
	R
	S
Front ®	T

Поскольку массив Name имеет конечную длину, скажем l, указатели Front и Back рано или поздно доберутся до его концов. Если длина списка, представленного этой очередью, никогда не превосходит, то можно трактовать Name[0] как элемент, следующий за элементом Name[l–1].

Элементы, расположенные в виде списка, сами могут быть сложными структурами. Работая, например, со списком массивов, мы на самом деле не добавляем и не удаляем массивы, ибо каждое добавление или удаление потребовало бы времени, пропорционального размеру массива. Вместо этого мы добавляем или удаляем указатели массивов. Таким образом, сложную структуру можно добавить или удалить за фиксированное время, не зависящее от ее размера.

1.6. Рекурсия

Процедуру, которая прямо или косвенно обращается к себе, называют рекурсивной. Применение рекурсии (recursion) часто позволяет дать более прозрачные и сжатые описания алгоритмов, чем это было бы возможно без рекурсии.

Рассмотрим определение прохождения двоичного дерева во внутреннем порядке, данное в разделе 1.5.

Идея прохождения дерева во внутреннем порядке заключается в следующем. Находясь в каком-то узле v, необходимо сначала проверить, есть ли у данного узла левый сын. Если таковой нашёлся, то нужно запомнить данный узел v и двинутся к левому сыну. С левым сыном описанная выше процедура повторяется, и т.д. Если же левого сына у узла v нет, то нужно присвоить этому узлу текущий номер и двинуться к правому сыну узла v, с которым опять требуется повторить сначала всю описанную процедуру. Если же сыновей у узла v нет, то необходимо вернуться к его предку на один уровень вверх. Далее процедура повторяется. Двигаться вниз по дереву нетрудно, но чтобы обеспечить возможность вернуться к предку, надо запомнить всех предков в стеке.

1.7. Разделяй и властвуй

Для решения той или иной задачи её часто разбивают на части, находят их решения и затем их них получают решение всей задачи. Этот приём, особенно если применять его рекурсивно, часто приводит к эффективному решению задачи, подзадачи которой представляют собой ее меньшие версии. Проиллюстрируем данную технику на примерах, сопровождаемых анализом получающихся рекуррентных уравнений.

Рассмотрим задачу нахождения наибольшего и наименьшего элементов множества S, содержащего n элементов. Для простоты будем считать, что n есть степень числа 2. Очевидный путь поиска наибольшего и наименьшего элементов состоит в том, чтобы искать их по отдельности. Например, следующая функция находит наибольший и наименьший элементы множества S, заданного массивом array, произведя 2×n-2 сравнений его элементов. Не ограничивая общности, массив выбрали типа int. Однако если требуется другой тип массива, то необходимо будет изменить тип у самой функции Max_Min_Element, у массива array и у указателя *ptr на соответствующий.

// Программа 4.1 поиска наибольшего и наименьшего элементов массива

void Max_Min_Element(int array[], unsigned Size, unsigned max, unsigned min)

// Функция находит максимальный и минимальный элементы массива array размера Size

{

unsigned index;

int *ptr;

ptr=&array[0];

min=max=*ptr++;

index=1;

while (index++<Size)

{

if (max<*ptr) max=*ptr;

if (min>*ptr) min =*ptr;

*ptr++

}

} // Конец Max_Min_Eletment

Итак, понятно, что для нахождения минимального и максимального элементов множества S требуется 2×n-2 сравнений при n³ 2. (Вообще-то достаточно на одно сравнение меньше, если реализовать поиск данных элементов последовательно и после нахождения максимального не учитывать его при поиске минимального, т.е. 2×n-3 сравнений).

Применяя приём «разделяй и властвуй» (divide and conquer), пришлось разбить бы множество S на два подмножества S₁ и S₂ по n/2 элементов в каждом. Тогда описанный выше алгоритм нашёл бы наибольший и наименьший элементы в каждом из двух половин с помощью рекурсии. Наибольший и наименьший элементы всего множества S можно было бы определить, произведя ещё два сравнения - наибольших элементов в S₁ и S₂ и наименьших элементов в них. Сформулируем данный алгоритм более точно.

Вход. Множество S из n элементов, n³2, n - степень числа 2.

Выход. Наибольший и наименьший элементы множества S.

Метод. К множеству S применяется рекурсивная процедура MaxMin. Она имеет два аргумента, представляющие собой само множество S и его размер║S║=2^k, и выдаёт на выходе пару (max, min), соответственно наибольший и наименьший элементы в S. Если множество S представлено массивом, то можно эффективно организовать вызовMaxMin, используя указатели на первый и последний элементы массива.

// Программа 4.2

// Программа находит максимальный и минимальный элемент в массиве

// методом «разделяй и властвуй» с использованием рекурсивной процедуры

#include <stdlib.h>

#include <stdio.h>

#define SIZE 1024 .// Размер массива array

typedef struct{ // Структура, состоящая из минимального и

int max; // максимального элементов, найденных в

int min; // массиве array

} pair;