Курсовая работа: Оценка трудоемкости алгоритма на основе эмпирического анализа

Содержание



2




















































3

Введение

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

• основе программной реализации. Однако, асимптотические оценки вы-числительной сложности, получаемые в теоретическом исследовании алго-ритмов, не всегда справедливы для конечного диапазона длин входов, что объясняется большими значениями коэффициентов у компонентов функ-ции трудоемкости. В работе предлагается практический подход на основе эмпирического анализа времени выполнения программной реализации, для чего создана автоматизированная система с критерием оценки по величине доверительной трудоемкости в выбранном диапазоне входных данных.

Вычисление доверительной трудоемкости основано на построении до-верительных интервалов оцениваемой величины трудоемкости с заданной доверительной вероятностью в классическом подходе математической ста-тистики [1]. Данный метод требует использования репрезентативных вы-борок достаточно большого объема и многократного запуска программ-ных реализаций исследуемых алгоритмов в соответствующем многоэтап-ном процессе; поэтому, несомненно, актуальной является разработка си-стемы для автоматизированного проведения