Построение и анализ алгоритмов
Алгоритм – набор предписаний, ведущий от некоторых входных данных к результату
Свойства алгоритма:
1. Массовость – алгоритм должен описывать круг однотипных задач, исходные данные которых могут изменяться в определенных пределах.
2. Детерминированность – это обусловленность всех шагов алгоритма потребностью решения данных задач. Свойство детерминированности выражается в том, что при заданных значениях параметров алгоритм выполняется формально, т.е. строго выполняется последовательность действий до появления результата.
3. Понятность – предписания алгоритма должны быть сформулированы так, чтобы они понимались одинаково разработчиком и исполнителем, т.е. они должны быть однозначно понятны.
4. Дискретность – четкое разделение всего пути решения задачи на отдельные этапы (шаги) так, чтобы ход выполнения алгоритма проходил поэтапно, вовремя корректируя действия исполнителя.
5. Результативность – точное выполнение предписаний алгоритма должно привести к результату за n шагов, если правильно разработана исходная модель и сам алгоритм.
При анализе алгоритма определяется количество «времени» для его выполнения. Это не реальное число секунд или других промежутков времени, а число операций, выполняемых алгоритмом. Число операций измеряет относительное время выполнения алгоритма или его вычислительную сложность. Фактическое количество секунд работы алгоритма непригодно для его анализа, т.к.
а) нас интересует относительная эффективность алгоритма;
б) алгоритм не становится лучше (хуже), если его перенести на более быстрый (медленный) компьютер.
АСИМПТОТИЧЕСКАЯ НОТАЦИЯ ДЛЯ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ
Несмотря на то, что функция временной сложности алгоритма в некоторых случаях может быть определена точно, в большинстве случаев искать точное её значение бессмысленно. Дело в том, что, во-первых, точное значение временной сложности зависит от определения элементарных операций (например, сложность можно измерять в количестве арифметических операций, битовых операций или операций на машине Тьюринга), а во-вторых, при увеличении размера входных данных вклад постоянных множителей и слагаемых низших порядков, фигурирующих в выражении для точного времени работы, становится крайне незначительным.
Рассмотрение входных данных большого размера и оценка порядка роста времени работы алгоритма приводят к понятию асимптотической сложности алгоритма. При этом алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных, за исключением лишь, возможно, данных малого размера. Для записи асимптотической сложности алгоритмов используются асимптотические обозначения.
СВОЙСТВА АССИМТОТИЧЕСКИХ ОБОЗНАЧЕНИЙ
Если в
правой части уравнения находится только
асимптотическое обозначение (например
),
то знак равенства обозначает принадлежность
множеству (
).
Если в
уравнении асимптотические обозначения
встречается в другой ситуации, они
рассматриваются как подставляемые
взамен их некоторые функции. Например,
при x → 0 формула
обозначает,
что
,
где
—
функция, о которой известно только то,
что она принадлежит множеству
.
Предполагается, что таких функций в
выражении столько, сколько раз встречаются
в нём асимптотические обозначения.
Например,
—
содержит только одну функцию из класса
.
Если
асимптотические обозначения встречаются
в левой части уравнения, используют
следующее правило:
какие бы мы функции
ни выбрали (в соответствии с предыдущим
правилом) взамен асимптотических
обозначений в левой части уравнения,
можно выбрать функции вместо асимптотических
обозначений (в соответствии с предыдущим
правилом) в правой части так, что уравнение
будет правильным.
Например, запись
обозначает,
что для любой функции
,
существует некоторая функция
такая,
что выражение
—
верно для всех
.
Несколько
таких уравнений могут быть объединены
в цепочки. Каждое из уравнений в таком
случае следует интерпретировать в
соответствии с предыдущим правилом.
Например:
.
Отметим, что такая интерпретация
подразумевает выполнение соотношения
.
Приведенная интерпретация подразумевает выполнение соотношения:
,
где A, B, C — выражения, которые могут
содержать асимптотические обозначения.
Вычислительная сложность – зависимость количества операций в алгоритме от входных данных.
Сложность в худшем случае, в лучшем, в среднем - существуют алгоритмы, которые изменяют время своей работы в зависимости от наборов данных, которое были введены.
АСИМПТОТИЧЕСКАЯ ОЦЕНКА ПОТРЕБЛЯЕМОЙ ПАМЯТИ
О (1):
Большинство инструкций программы запускается один или несколько раз, независимо от n. Т.е. время выполнения программы постоянно.
О (n):
Время выполнения программы линейно зависит от n. Каждый входной элемент подвергается небольшой обработке.
(поиск min/max в массиве, значения в связанном списке) (for…; i<n ;...).
О (n2):
Время выполнения программы является квадратичным. Такие алгоритмы можно использовать для относительно небольших n. Такое время характерно, когда обрабатываются все пары элементов (в цикле двойного уровня вложенности).
(сортировки выбором, вставками).
О (n3):
Алгоритм обрабатывает тройки элементов (возможно, в цикле тройного уровня вложенности) и имеет кубическое время выполнения. Такой алгоритм практически применим только для малых задач. (умножение матриц).
О (log n):
Программа работает медленнее с ростом n. Такое время характерно для программ, которые сводят большую задачу к набору меньших подзадач, уменьшая на каждом шаге размер подзадачи на некоторый постоянный коэффициент. Общее решение находится в одной из подзадач. Логарифмическая зависимость. (бинарный поиск).
О (n*log n):
Время выполнения программы пропорционально n*log n возникает тогда, когда алгоритм решает задачу, разбивая ее на меньшие подзадачи, решая их независимо и затем объединяя решения подзадач (комбинация).
(сортировки быстрая, слиянием).
О (2n):
Лишь несколько алгоритмов с экспоненциальным временем имеет практическое применение, хотя такие алгоритмы возникают естественным образом при попытке прямого решения задач. (перебор и сравнение различных решений) Для комбинаторных задач нереализуемы. Сведение к приближенному алгоритму с приближенным значением.
Обычно время выполнения в результате анализа выглядит как многочлен, где главным членом является один из вышеприведенных. Коэффициент при главном члене зависит от количества инструкций во внутреннем цикле. Поэтому так важно максимально упрощать количество инструкций во внутреннем цикле. При росте N начинает доминировать главный член, поэтому остальными слагаемыми в многочлене можно пренебречь.