Асимптотический анализ алгоритмов

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

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

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

В асимптотическом анализе приняты следующие обозначения:

1.Оценка Θ(тетта)

Пусть f(n) и g(n) — положительные функции положительного аргумента, n >= 1 (количество объектов на входе и количество операций -положительные числа), тогда:

f(n) =Θ(g(n)), если существуют положительные c₁, с₂, n₀, такие, что: c_l ·g(n) =< f(n) =< c₂ * g(n), при n > n₀

Обычно говорят, что при этом функция g(n) является асимптотически точной оценкой функции f(n), т.к. по определению функция f(n) не отличается от функции g(n) с точностью до постоянного множителя.

Отметим, что из f(n) = Θ(g(n)) следует, что g(n) = Θ(f(n)). Примеры:

1) f(n)=4n²+nlnN+174 - f(n)= Θ (n²)_;

2) f(n)=Θ(l) - запись означает, что f(n) или равна константе, не равной нулю, или f(n) ограничена константой на : f(n) = 7+1/n = Θ(1).

2. Оценка О ( О большое)

В отличие от оценки Θ, оценка О требует только, что бы функция f(n) не превышала g(n) начиная с n > n₀, с точностью до постоянного множителя:

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

Например, для всех функций:

f(n)=l/n, f(n)= 12, f(n)=3·n+17, f(n)=n·Ln(n), f(n)=6·n ²+24·п+77 будет справедлива оценка О(n²)

Указывая оценку О, есть смысл указывать наиболее «близкую» мажорирующую функцию, поскольку например для f(n)= n² справедлива оценка О(n²), однако она не имеет практического смысла.

3. Оценка Ω (Омега)

В отличие от оценки О, оценка Ω является оценкой снизу, т.е. определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя:

Например, запись Ω (n·Ln(n)) обозначает класс функций, которые растут не медленнее, чем g(n) = n·Ln(n), в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы.

Асимптотическое обозначение О восходит к учебнику Бахмана по теории простых чисел (Bachman, 1892), обозначения Θ,Ωвведены Д. Кнутом (Donald Knuth).

Отметим, что не всегда для пары функций справедливо одно из асимптотических соотношений, например для f(n)=n^1+sin(n) и g(n)=n не выполняется ни одно из асимптотических соотношений.

В асимптотическом анализе алгоритмов разработаны специальные методы получения асимптотических оценок, особенно для класса рекурсивных алгоритмов. Очевидно, что Θ оценка является более предпочтительной, чем оценка О. Знание асимптотики поведения функции трудоемкости алгоритма - его сложности, дает возможность делать прогнозы по выбору более рационального с точки зрения трудоемкости алгоритма для больших размерностей исходных данных.

В частности, проблема останова также является частично разрешимой проблемой, а проблемы эквивалентности и тотальности не являются таковыми.

Контрольные вопросы

1. Что представляет собой решение задачи на ПЭВМ?

2. Охарактеризуйте этапы решения задачи на ПЭВМ.

3. Что такое алгоритм?

4. Назовите основные свойства алгоритмов и дайте им характеристику.

5. Опишите способы записи алгоритмов.

6. Что такое псевдокод?

7. Дайте перечень блоков в методе блок-схем.

8. Дать понятие «структура данных».

9. Привести классификацию структур данных.

10. Что называется структурой хранения?

11. Чем отличаются физические и логические структуры данных?

12. Какой признак структуры данных является наиболее важным?

13. Дать определение типу данных.

14. Какие бывают типы данных? Охарактеризуйте их.

15. На какие вычислительные процессы делятся алгоритмы? Привести примеры основных вычислительных процессов (алгоритмов).

16. Какие процессы имеют место при вычислении арифметических выражений?

17. Что является целью анализа трудоемкости алгоритмов?

18. Дайте определения «трудоемкость» алгоритма и «функция трудоемкости».

19. Как проводится анализ алгоритмов?

20. Что является целью асимптотического анализа алгоритмов?