Разработка технологии создания дистанционных курсов на примере курса "Администрирование DB2", страница 27

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

3.2 O-сложность алгоритмов^[4]

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

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

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

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

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

В математике существует специальный механизм оценки скорости роста интересующей исследователя величины: ее сравнивают с какой-нибудь функцией, чье поведение хорошо исследовано. При этом используется обозначение g(n)=O(f(n)) (читается: O-большое), которое относиться к интересующим нас дискретным функциям f(n) натурального n и ко всем функциям g(n), растущим не быстрее f(n). Формулировка "растущим не быстрее" означает, что существует такая пара положительных значений M и n₀, что |g(n)|≤M|f(n0)| для n≥n₀.

Такая O-нотация дает верхнюю оценку временной трудоемкости алгоритма, его асимптотическую сложность. Использование констант M и n₀, фигурирующих в определении, фактически связано с "большими" значениями аргумента n и мало что дает при его малых значениях.

Свойства O-операций:

1. f(n)=O(f(n))

2. O(c·f(n)) = c·O(f(n)) = O(f(n)), где c - некоторая константа

3. O(f(n))+O(g(n))=max{O(f(n)),O(g(n))}

4. O(O(f(n)))=O(f(n))

5. O(f(n))·O(g(n))=O(f(n)·g(n)) или O(f(n)) / O(g(n))=O(f(n)/g(n))

O-функция отражает относительную скорость алгоритма в зависимости от некоторой переменной (или переменных).

Виды сложностей алгоритмов и программ

O(1) - данная сложность свидетельствует, что большинство операций в программе выполняется только раз или только несколько раз. Такие алгоритмы называется алгоритмами константной сложности (поскольку их сложность не зависит от объема входных данных).

O(N) - свидетельствует о том, что время работы программы линейно зависит от объема входных данных

O(N²), O(N³), O(N^k) - полиномиальная сложность.

O(log(N)) - такое время работы встречается в программах, которые делят большую задачу на более маленькие и решают их по отдельности.

O(N*log(N)) - такое время работы имеют программы, которые делят большую задачу на ряд более мелких, а затем решив их, объединяют решения.

O(2^N) - экспоненциальная (показательная) сложность. Алгоритмы и программы такой сложности чаще всего возникают в результате решения задачи с "наскока".

Временная сложность алгоритма может быть подсчитана исходя из анализа его управляющих структур (таблица 3.1)

Таблица 3.1

Сложность управляющих структур