Базовые алгоритмы обработки данных.

 

Базовые алгоритмы обработки данных являются результатом исследований и разработок, проводившихся на протяжении десятков лет. Но они, как и прежде, продолжают играть важную роль во все расширяющемся применении вычислительных процессов.

К базовым алгоритмам императивного программирования можно отнести:

• Алгоритмы работы со структурами данных. Они определяют базовые принципы и методологию, используемые для реализации, анализа и сравнения алгоритмов. Позволяют получить представление о методах представления данных. К таким структурам относятся связные списки и строки, деревья, абстрактные типы данных, такие как стеки и очереди.
• Алгоритмы сортировки, предназначенные для упорядочения массивов и файлов, имеют особую важность. С алгоритмами сортировки связаны, в частности, очереди по приоритету, задачи выбора и слияния.
• Алгоритмы поиска, предназначенные для поиска конкретных элементов в больших коллекциях элементов. К ним относятся основные и расширенные методы поиска с использованием деревьев и преобразований цифровых ключей, в том числе деревья цифрового поиска, сбалансированные деревья, хеширование, а также методы, которые подходят для работы с очень крупными файлами.
• Алгоритмы на графах полезны при решении ряда сложных и важных задач. Общая стратегия поиска на графах разрабатывается и применяется к фундаментальным задачам связности, в том числе к задаче отыскания кратчайшего пути, построения минимального остовного дерева, к задаче о потоках в сетях и задаче о паросочетаниях. Унифицированный подход к этим алгоритмам показывает, что в их основе лежит одна и та же процедура, и что эта процедура базируется на основном абстрактном типе данных очереди по приоритету.
• Алгоритмы обработки строк включают ряд методов обработки (длинных) последователей символов. Поиск в строке приводит к сопоставлению с эталоном, что в свою очередь ведет к синтаксическому анализу. К этому же классу задач можно отнести и технологии сжатия файлов.
• Геометрические алгоритмы – это методы решения задач с использованием точек и линий (и других простых геометрических объектов), которые вошли в употребление достаточно недавно. К ним относятся алгоритмы построения выпуклых оболочек, заданных набором точек, определения пересечений геометрических объектов, решения задач отыскания ближайших точек и алгоритма многомерного поиска. Многие из этих методов дополняют простые методы сортировки и поиска.

 

Сортировка

 

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

Если сортируемый файл целиком помещается в памяти, то используемый метод сортировки называется внутренним (internal). Сортировка файлов на внешних носителях называется внешней (external). Основное различие между ними состоит в том, что при внутренней сортировке доступ к любому элементу файла не предоставляет трудностей, в то время как в условиях внешней сортировки возможен только последовательный доступ к элементу или, по крайней мере, доступ к большим блокам элементов.

На ряду с сортировкой массивов большой интерес представляет изучение методов сортировки связных списков (динамических структур). Однако большинство классических методов сортировки массивов обладают столь высокой степенью абстракции, что могут без труда быть применены к сортировке связных списков.

 

Можно выделить пять типов алгоритмов сортировки:

• Обменом – выполняются проходы по файлу с обменом местами элементов, до тех пор, пока файл не будет окончательно отсортирован.
• Вставками – отдельно анализируется каждый конкретный элемент, который затем помещается на надлежащее ему место среди других, уже отсортированных элементов
• Выбором – сначала отыскивается наименьший элемент массива, затем он меняется местами с элементом, стоящим первым в сортируемом массиве и т.д.
• Слиянием – сортируемый файл, расположенный во внешней памяти, разбивается на части, которые могут быть считаны в память, отсортированы каким-либо методом и записаны в отдельные временные файлы. Затем отсортированные временные файлы сливаются попарно с сохранением порядка сортировки. И так до тех пор, пока все временные файлы не будут объединены в один отсортированный файл.
• сортировка деревом – сортируемые элементы добавляются в бинарное дерево. Отсортированный массив формируется путем концевого обхода построенного дерева.

 

Основной характеристикой алгоритма сортировки является время, затраченное на его выполнение. Так для массива из N элементов:

• Сортировка выбором производит в среднем N^2 / 2 операций сравнения и N операций обмена
• Сортировка вставками – в среднем N^2 / 4 сравнений и N^2 / 4 операций полуобмена (перемещений) и в два раза больше в наихудшем случае
• Сортировка обменом (метод пузырька) – N^2 / 2 операций сравнения и N^2 / 2 обменов как в среднем так и наихудшем случае
• Сортировка деревом – N * log (N) операций сравнения и N операций вставки

 

Второй по важности фактор в алгоритмах сортировки – объем используемой дополнительной памяти. По существу, все методы можно разбить на три группы:

• Те, которые выполняют сортировку на месте и не нуждаются в дополнительной памяти, за исключением, возможно, стека или таблицы
• Те, которые используют представление в виде связного списка для размещения указателей или индексов
• Те, которые требуют дополнительной памяти для размещения еще одной копии сортируемого массива

 

Поиск

Поиск – получение конкретного фрагмента или фрагментов информации из больших объемов ранее сохраненных данных. Как и с случае алгоритмов сортировки, мы работаем с данными, разделенными на записи (элементы), каждая из которых имеет ключ, используемый при поиске. Цель поиска – отыскание элементов с ключами, значения которых соответствуют ключу поиска.

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

Иногда таблицы символов называют словарями по аналогии с хорошо известной системой упорядочивания слов в алфавитном порядке: слово – ключ, его толкование – данные.

Основные методы поиска:

• Поиск с использованием индексации по ключам. Пусть ключи – различные небольшие числа. В этом случае простейший алгоритм поиска предполагает хранение элементов в массиве St, проиндексированном значениями ключей. Изначально массив проинициализирован значениями Null. Затем можно вставить элемент со значением K записав его в St[K] или найти его, обратившись к St[K]. Удалить элемент K можно записав в St[K] значение Null.
• Последовательный поиск – в случае, когда диапазон ключей слишком велик, простейший способ реализации таблицы символов – упорядоченное хранение в последовательном массиве. Когда требуется вставить элемент в массив, мы вставляем его, сдвигая остальные, как в случае сортировки вставкам. Когда необходимо выполнить поиск – выполняется последовательный просмотр массива. Поскольку массив упорядочен, при встрече ключа больше искомого можно сделать вывод о неудаче поиска. При удачном поиске используется в среднем N / 2 сравнений, при неудачном – N.
• Бинарный поиск – основан на принципе «разделяй и властвуй». Мы делим упорядоченную таблицу символов на две части, определяем часть, в которой может лежать ключ и производим в ней такую же процедуру поиска. При бинарном поиске используется не более чем Log₂(N)+1 опeраций сравнения как при удачном поиске, так и при неудачном.

 

⇐ Предыдущая123456Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: