Средний случай

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

1. В основе анализа лежит определение различных групп, на которые следует разбить возможные входные наборы данных.
2. На втором шаге определяется вероятность, с которой входной набор данных принадлежит каждой группе.
3. На третьем шаге подсчитывается время работы алгоритма на данных из каждой группы. Время работы алгоритма на всех входных данных одной группы должно быть одинаковым, в противном случае группу следует разбить ещё раз.

Среднее время работы вычисляется по формуле:

, где

• n - размер входных данных;
• m - число групп;
• p_i - вероятность того, что входные данные принадлежат группе с номером i;
• t_i - время необходимое алгоритму для обработки данных из группы с номером i.

И разбиение на группы, и значения параметров p_i и t_i зависят от n.

Если вероятность попадания входных данных в каждую из групп одинакова, то среднее время работы определить по упрощённой формуле, справедливой при равной вероятности групп:

Например, если групп пять, то вероятность попасть в первую группу такая же, как вероятность попасть во вторую, и т.д., то есть вероятность попасть в каждую группу равна 0,2.