Алгоритмы и структуры данных
Вопросы по теории
Алгоритмы и структуры данных
Алгоритм (algorithm) — это любая корректно определенная вычислительная процедура, на вход (input) которой подается некоторая величина или набор величин, и результатом выполнения которой является выход-
выходная (output) величина или набор значений. Таким образом, алгоритм представляет
собой последовательность вычислительных шагов, преобразующих входные ве-
величины в выходные.
Структура данных — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс. Структура данных часто является реализацией какого-либо абстрактного типа данных.
Макс
Асимптотическая оценка алгоритма
является наглядной характеристикой эффективности алгоритма, а также позволяет сравнивать производительность различных алгоритмов.
{Асимптотически положительной называется такая функция, которая является положительной при любых достаточно больших n).
Для всех n≥n0 функция f (n) равна функции g (n) с точностью до
постоянного множителя. Говорят, что функция g(n) является асимптотически
точной оценкой функции f (n).
Обозначения:
В 0-обозначениях функция асимптотически ограничивается сверху и снизу.
Если же достаточно определить только асимптотическую верхнюю границу,
используются О-обозначения. в Ω-обозначениях дается ее асимптотическая нижняя граница.
Методика оценки не рекурсивных алгоритмов
Время работы алгоритма — это сумма промежутков времени, необходимых для
выполнения
каждой входящей в его состав исполняемой
инструкции. Если выполнение инструкции
длится в течение времени
и она повторяется в алгоритме n
раз, то ее вклад в полное время работы
алгоритма равно
n.
Даже если размер входных данных является фиксированной величиной, время
работы алгоритма может зависеть от степени упорядоченности сортируемых ве-
величин, которой они обладали до ввода.
Рекурсивные алгоритмы, построение асимптотической оценки
Многие полезные алгоритмы имеют рекурсивную структуру: для решения дан-
данной задачи они рекурсивно вызывают сами себя один или несколько раз, чтобы
решить вспомогательную задачу, имеющую непосредственное отношение к по-
поставленной задаче. Такие алгоритмы зачастую разрабатываются с помощью
метода декомпозиции, или разбиения: сложная задача разбивается на несколько более простых, которые подобны исходной задаче, но имеют меньший объем; далее эти вспомогательные задачи решаются рекурсивным методом, после чего полученные решения комбинируются с целью получить решение исходной задачи.
Парадигма, лежащая в основе метода декомпозиции "разделяй и властвуй", на
каждом уровне рекурсии включает в себя три этапа.
Разделение задачи на несколько подзадач.
Покорение — рекурсивное решение этих подзадач. Когда объем подзадачи доста-
достаточно мал, выделенные подзадачи решаются непосредственно.
Комбинирование решения исходной задачи из решений вспомогательных задач.
Если алгоритм рекурсивно обращается к самому себе, время его работы часто
описывается с помощью рекуррентного уравнения, или рекуррентного соотношения, в котором полное время, требуемое для решения всей задачи с объемом ввода n, выражается через время решения вспомогательных подзадач. Затем данное рекуррентное уравнение решается с помощью определенных математических методов, и устанавливаются границы производительности алгоритма.
Метод получения асмптот оценки по рекур отношению:
Интерация – рассматриваем формулу в сумму элементов которые вычисляются на основе формулы n элементов
Основная теорема для рекурсивных алгоритмов
Теорема является своего рода "сборником рецептов", по которым строятся решения рекуррентных соотношений вида
где а≥1иb>1 — константы, а / (n) — асимптотически положительная функция.
Чтобы научиться пользоваться этим методом, необходимо запомнить три случая,
что значительно облегчает решение многих рекуррентных соотношений, а часто
это можно сделать даже в уме.
