12. Основные вопросы анализа алгоритмов. Понятие алгоритмической сложности.

• описание анализа алгоритма;

• объяснение принципов выбора подсчитываемых операций;

• объяснение, как проводить анализ в наилучшем, наихудшем и среднем случае;

• работа с логарифмами, вероятностями и суммированием;

• описание функции θ(f), Ω(f), Ο ( f ) , скорости роста и порядка

алгоритма;

• использование дерева решений для определения нижней границы

сложности;

• приведение простого рекуррентного соотношения к замкнутому виду.

Трудоемкость алгоритма.

Под трудоемкостью алгоритма для данной конкретной проблемы, заданной множеством D, будем понимать количество «элементарных» операций, задаваемых алгоритмом в принятой модели вычислений. Соответствующую функцию будем обозначать как f_a (D). Значением функции трудоемкости является целое положительное число.

При более детальном анализе ряда алгоритмов оказывается, что не всегда количество элементарных операций задаваемых алгоритмом, т.е. значение f_a (D) на входе длины n, где n = |D|, совпадает с количеством операций на другом входе такой же длины.

Введем специальные обозначения, связанные с граничными значениями функции трудоемкости данного алгоритма при фиксированной длине входа. Пусть DA — множество допустимых конкретных проблем данной задачи, решаемой алгоритмом A, D Є DA — конкретная проблема (вход алгоритма А), представляющая собой упорядоченное множество элементов (слов) d:

В общем случае существует подмножество (для большинства алгоритмов собственное) множества DA, включающее все конкретные проблемы, имеющие размерность n, — обозначим его через D_n:

В предположении о том, что элементы d, представляют собой слова фиксированной длины в алфавите {0,1}, множество D_n„ является конечным — обозначим его мощность через M_Dn , т.е. M_Dn = |D_n|. Тогда алгоритм А, имея на входе различные множества D Є D_n, будет, возможно, задавать в каком-то случае наибольшее, а в каком-то случае наименьшее количество операций.

Введем следующие обозначения, отметив, что соответствующая терминология является устоявшейся в литературе по анализу алгоритмов.

1. f_A(n) — худший случай — наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерности n:

2. f_A(n) — лучший случай — наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерности n:

3. f_A(n) — средний случай — среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерности n: