Базовые алгоритмы обработки данных являются результатом исследований и разработок, проводившихся на протяжении десятков лет. Но они, как и прежде, продолжают играть важную роль во все расширяющемся применении вычислительных процессов.
К базовым алгоритмам процедурного программирования можно отнести:
· Алгоритмы работы со структурами данных. Они определяют базовые принципы и методологию, используемые для реализации, анализа и сравнения алгоритмов. Позволяют получить представление о методах представления данных. К таким структурам относятся связные списки и строки, деревья, абстрактные типы данных, такие как стеки и очереди.
· Алгоритмы сортировки, предназначенные для упорядочения массивов и файлов, имеют особую важность. С алгоритмами сортировки связаны, в частности, очереди по приоритету, задачи выбора и слияния.
· Алгоритмы поиска, предназначенные для поиска конкретных элементов в больших коллекциях элементов. К ним относятся основные и расширенные методы поиска с использованием деревьев и преобразований цифровых ключей, в том числе деревья цифрового поиска, сбалансированные деревья, хеширование, а также методы, которые подходят для работы с очень крупными файлами.
· Алгоритмы на графах полезны при решении ряда сложных и важных задач. Общая стратегия поиска на графах разрабатывается и применяется к фундаментальным задачам связности, в том числе к задаче отыскания кратчайшего пути, построения минимального остовного дерева, к задаче о потоках в сетях и задаче о паросочетаниях. Унифицированный подход к этим алгоритмам показывает, что в их основе лежит одна и та же функция, и что эта функция базируется на основном абстрактном типе данных очереди по приоритету.
· Алгоритмы обработки строк включают ряд методов обработки последовательностей символов. Поиск в строке приводит к сопоставлению с эталоном, что, в свою очередь, ведет к синтаксическому анализу. К этому же классу задач можно отнести и технологии сжатия файлов.
· Геометрические алгоритмы – это методы решения задач с использованием точек и линий (и других простых геометрических объектов), которые вошли в употребление достаточно недавно. К ним относятся алгоритмы построения выпуклых оболочек, заданных набором точек, определения пересечений геометрических объектов, решения задач отыскания ближайших точек и алгоритма многомерного поиска. Многие из этих методов дополняют простые методы сортировки и поиска.
Ключевые термины
Алгоритм обработки данных – это описание метода решения задачи в компьютерных науках, который в дальнейшем возможно реализовать в выбранной среде программирования.
Анализ алгоритмов – это направление компьютерных наук, занимающееся изучением оценки эффективности алгоритмов.
Трудоемкость алгоритма – это количество элементарных операций, которые учитываются при анализе алгоритма.
Худший случай трудоемкости – это наибольшее количество операций, задаваемых алгоритмом А на всех входах D определенной размерности n.
Лучший случай трудоемкости – это наименьшее количество операций в алгоритме А на всех входах D определенной размерностиn.
Средний случай трудоемкости – это среднее количество операций в алгоритме А на всех входах D определенной размерности n.
Функция трудоемкости алгоритма – это зависимость трудоемкости алгоритма А от значения параметров на входе D.
Временная сложность алгоритма – это асимптотическая оценка функции трудоемкости алгоритма для худшего случая.
Объем памяти – это максимальное количество ячеек памяти, задействованных в ходе выполнения алгоритма А для входа D.
Емкостная сложность алгоритма – это асимптотическая оценка функции объема памяти алгоритма для худшего случая.
Ресурсная сложность алгоритма в худшем, среднем и лучшем случаях – это упорядоченная пара классов функций временной и емкостной сложности, заданных асимптотическими обозначениями и соответствующих рассматриваемому случаю.
Алгоритмы работы со структурами данных – это алгоритмы, которые определяют базовые принципы и методологию, используемые для получения представление о методах обработки данных.
Алгоритмы сортировки – это алгоритмы, предназначенные для упорядочения массивов и файлов.
Алгоритмы поиска – это алгоритмы, предназначенные для поиска конкретных элементов в больших коллекциях данных.
Алгоритмы на графах – это алгоритмы, предназначенные для реализации стратегий обходов и поиска на графах.
Алгоритмы обработки строк – это алгоритмы, которые включают ряд методов обработки последовательностей символов.
Геометрические алгоритмы – это алгоритмы решения задач с использованием геометрических объектов.
Примеры анализа трудоемкости алгоритмов.
Пример 1 Задача суммирования элементов квадратной матрицы
SumM (A, n; Sum)
Sum =0 // 1 операция
For i = 1 to n // 3 операции на один проход цикла
For j = 1 to n // 3 операции на один проход цикла
Sum =Sum + A[i,j] // 4 операции
End for j
End for i
Return (Sum)
End.
Алгоритм выполняет одинаковое количество операций при фиксированном значении n, и, следовательно, является количественно-зависимым. Его функция трудоемкости зависит только от размерности конкретного входа. Применение методики анализа конструкции «Цикл » дает:
fA(n)=1+1+ n *(3+1+ n *(3+4))=7*n2+4* n +2 = 
(n2),
где внутренний цикл: f1(n) = 1+3*n+4*n
внешний цикл: f2(n)= 1+3*n+n*f1(n)
замечание по задаче:
под n понимается линейная размерность матрицы, в то время как на вход алгоритма подается n2 значений.
Общее замечание:
Количественно-зависимые по трудоемкости алгоритмы - это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений:
Fa(n), n=f(N)
К ним можно отнести алгоритмы для стандартных операций с массивами и матрицами – умножение матриц, умножение матрицы на вектор и т.д.
Пример 2 Задача поиска максимума в массиве
MaxS (S,n; Max)
Max = S[1] // 2 операции
For i = 2 to n // 3 операции на один проход цикла
if Max < S[i] // 2 операции
then Max =S[i] // 2 операции
end for
return Max
End
Данный алгоритм является количественно-параметрическим.
Трудоемкость таких алгоритмов определяется количеством данных на входе и значениями этих данных:
Fa(n), n=f(N,р1…,рi)
В данном конкретном случае трудоемкость зависит от размера входа и от порядка расположения однородных элементов. Зависимость от значений не может быть полностью исключена, но она не является существенной, поэтому для фиксированной размерности исходных данных необходимо проводить анализ для худшего, лучшего и среднего случая. Примерами такого класса могут служить алгоритмы сортировки сравнениями, алгоритмы поиска минимума и максимума в массиве.
А). Худший случай
Максимальное количество переприсваиваний максимума (на каждом проходе цикла) будет в том случае, если элементы массива отсортированы по возрастанию. Трудоемкость алгоритма в этом случае равна:
fA(n)=1+1+1+ (n-1) (3+2+2)=7 n - 4 = (n).
Б) Лучший случай
Минимальное количество переприсваивания максимума (ни одного на каждом проходе цикла) будет в том случае, если максимальный элемент расположен на первом месте в массиве. Трудоемкость алгоритма в этом случае равна:
fA(n)=1+1+1+ (n-1) (3+2)=5 n - 2 = (n).
В) Средний случай
Алгоритм поиска максимума последовательно перебирает элементы массива, сравнивая текущий элемент массива с текущим значением максимума. На очередном шаге, когда просматривается к-ый элемент массива, переприсваивание максимума произойдет, если в подмассиве из первых “к” элементов максимальным элементом является последний. Очевидно, что в случае равномерного распределения исходных данных, вероятность того, что максимальный из к элементов расположен в определенной (последней) позиции равна 1/к. Тогда в массиве из n элементов общее количество операций переприсваивания максимума определяется как:
-постоянная Эйлера
Величина Hn называется n-ым гармоническим числом. Таким образом, точное значение (математическое ожидание) среднего количества операций присваивания в алгоритме поиска максимума в массиве из n элементов определяется величиной Hn (при очень большом количестве испытаний)), тогда:
fA(n)=1 + (n-1) (3+2) + 2 (ln (n) + )=5 n +2 ln(n) - 4 +2 = (n).
(В сущности это есть математическое ожидание среднего количества операций присваивания в алгоритме поиска максимума в массиве их n элементов. При этом мы предполагаем, что значения элементов распределены равномерно)
[Анализ сложности рекурсивных алгоритмов будет разобран на практике №3-4 для задачи вычисления факториала для некоторого значения n (n – параметр алгоритма, а не количество слов на входе)]
Теперь делим массив на две части и в каждой части производим такую же сортировку.
Сначала займемся первой половиной массива в которой находятся элементы меньше
6. 
Выбираем центральный элемент с которым будем сравнивать. Сразу видим, что нужно поменять местами элементы, на которых находятся указатели.
Все первая часть отсортирована, займемся второй частью массива.
Выберем элемент со значением, как элемент относительно которого будем сравнивать.
6 и 8 оставляем на своих местах, сдвигаем указатели. 7 и 9 тоже не трогаем. Теперь давайте поделим эту половинку еще на две. И отдельно сравним элементы в каждой из половинок: 9 и 8 меняем местами, 6 и 7 не изменяем.
Ну вот и все мы отсортировали массив методом быстрой сортировки.