Реклама:

При тестировании программ их сложность определяется, в ^основном,; тремя видами ресурсов, которым соответствуют:

временная сложность программ в процессе тестирования, которая характеризуется временем счета типовых контрольных примеров, необходимых для проверки всех функций программы", или временем решения типовой задачи;

программная сложность модуля, группы или комплекса, соответствующая сложности текста и структуры программы, В совокупности определяющих разнообразие возможных характеристик ее функционирования;

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

Эти виды сложности определяют разные виды ресурсов Используемых при тестировании. Временная сложность прежде всего влияет на требующуюся производительность ЭВМ, на которой осуществляется тестирование, и в меньшей степени определяет ресурсы труда программистов. Программная сложность в основном потребляет ресурсы разработчиков программ для подготовки и анализа процесса функционирования программы при тестировании. В некоторых программах определяющей при тестировании может быть информационная сложность подготовки и анализа данных, используемых для проверки и нормального функционирования программ. В зависимости от алгоритма и характеристик программы при ее тестировании доминирующей может быть временная, программная или информационная, сложность.

Врежннйя сложность программ в основном определяется алгоритмами, используемыми для решения задач [54, 60]. Несмотря на возрастание быстродействия современных ЭВМ име-етсямиого задач, которые невозможно решать некоторыми точными, прежде всего комбинаторными, алгоритмами при необходимом объеме входных данных. Для того чтобы оценивать временную сложность алгоритмов независимо от быстродействия ЭВМ,,ее характеризуют количеством операций или условных единиц времени «шагов» работы ЭВМ, требующихся для обработки входных данных [541.

В принципе, для каждой вычисляемой функции существует бесконечно много алгоритмов, которые ее.вычисляют и которые могут значительно различаться по временной сложности. Для оценки и сравнения временной сложности различных алгоритмов проведены исследования, позволившие раскрыть сущность изменения объема вычислений от размерности исходных данных для ряда типовых вычислительных задач. Ускорение вычислений достигается за счет повышения сложности программ, вычислителя или расширения алфавита исходных данных. Для многих типов задач с помощью узкой специализации программ для ограниченной области изменения входных данных имеется возможность эффективного ускорения вычислений. Теоретически доказана принципиальная возможность р а з м е-н а времени решения любых задач на емкость памяти для хранения программ и данных, однако пока отсутствуют общие конструктивные пути размена и оценки соотношения между значениями изменяемых характеристик в зависимости от классов решаемых задач. Изучены алгоритмы типовых операций над матрицами, комбинаторные алгоритмы поиска и распознавания, алгоритмы выполнения арифметических операций на ЭВМ и т. д., для которых найдены предельные по экономии времени общие методы решения задач и, в некоторых случаях, соотношения размена времени на емкость оперативной памяти для хранения данных '154, 601.


⇐ Предыдущая страница| |Следующая страница ⇒