Аннотация.

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

Ключевые слова:

бета-распределение, доверительная трудоемкость, критерий согласия Пирсона, метод моментов, трудоемкость алгоритма.

Авторы:

Ульянов Михаил Васильевич.
Профессор кафедры «Прикладная математика и моделирование систем» Московского государственного университета печати. Окончил Московский институт электронного машиностроения в 1979 году. Доктор технических наук (2005 г.), профессор (2006 г.). Автор более 75 научных работ, в том числе 5 монографий. Область научных интересов: анализ и разработка ресурсно-эффективных компьютерных алгоритмов.

Петрушин Владимир Николаевич.
Доцент кафедры «Прикладная математика и моделирование систем» Московского государственного университета печати. Окончил физический факультет Московского университета в 1974 году. Кандидат физико-математичсеких наук (1988 г.), доцент (1991 г.). Автор более 75 научных работ. Область научных интересов: теория вероятностей, математическая статистика, теория эксперимента.

Кривенцов Александр Сергеевич.
Студент 5-го курса Московского государственного университета приборостроения и информатики, кафедра «Управление и моделирование систем». Область научных интересов: исследование, анализ и разработка компьютерных алгоритмов.

Полная версия статьи в формате pdf.