Система обозначений в анализе алгоритмов

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

Пусть D_А — множество конкретных проблем данной задачи, заданное в формальной системе. Пусть D_Ғ, D_А — задание конкретной проблемы и |D|=N.

В общем случае существует собственное подмножество множества D_А, включающее все конкретные проблемы, имеющие мощность N:

- обозначим это подмножество через D_N:D_N= {D_Ғ, D_N : |D| = N};

- обозначим мощность множества D_N через M_DN→ M_DN=|D_N |.

Тогда содержательно данный алгоритм, решая различные задачи размерности N, будет выполнять в каком-то случае наибольшее количество операций, а в каком-то случае наименьшее количество операций. Введем следующие обозначения:

1. F_α ^(N) - худший случай - наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

F_α ^(N) = max {F_α (D)}

DD_N -худший случай на D_N.

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

F_a (N) = min {F_a (D)}

DD_N - лучший случай на D_N

3. _α(N) - средний случай - среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

_a(N)=(1/M_DN}·Σ{F_a(D)}

DÎD_N - средний случай на D_N