Анализ сложности в среднем. Вероятностные алгоритмы

Среди подходов к решению NP-трудных задач можно выделить два. Первый заключается в построении приближенных алгоритмов с гарантированными оценками точности получаемого решения, а второй — в отказе от анализа сложности алгоритмов по наихудшему случаю и переходе к анализу сложности в среднем.
Настоящая лекция посвящена изучению второго подхода (анализу сложности в среднем) применительно к задаче упаковки.

При анализе сложности в среднем вводится некоторая вероятностная мера на
исходных данных. Средним временем работы алгоритма называется математическое ожидание времени его работы (по всем исходным данным с заданным распределением).