Доверительная трудоемкость – новая оценка качества алгоритмов

Рассматриваются вопросы, связанные с оценкой качества компьютерных алгоритмов по критерию трудоемкости. Классически применяемая оценка трудоемкости в среднем позволяет получить значимые результаты только в статистическом смысле, т. е. оценить алгоритм на большом числе входов с фиксированной длиной. В статье вводится интервальная оценка – доверительная трудоемкость, построенная по аналогии с доверительными интервалами математической статистики. Предлагается использовать бета-распределение для аппроксимации распределения значений трудоемкости как ограниченной дискретной случайной величины, приводится методика определения доверительной трудоемкости как функции длины входа алгоритма.