Cтраница 4
Основные трудности анализа алгоритма в среднем случае связаны как с выяснением значений трудоемкости для конкретных входов, так и с определением вероятности их появления. В связи с этим задача вычисления / А ( п) для алгоритмов класса NPR является достаточно трудоемкой. Эти методы могут быть использованы и для получения функции трудоемкости алгоритмов в среднем случае. [46]
Суть сетевого подхода состоит в выделении путей на графе алгоритма, соответствующих минимальной, средней и максимальной трудоемкости последовательности операторов. Эти пути могут быть выделены только на графах, не содержащих циклов. По этой причине методика сетевого подхода начинается с анализа трудоемкости алгоритмов, не содержащих циклы. Затем рассматривается прием исключения циклов из графа алгоритма путем замены их операторами с эквивалентной трудоемкостью. Этот прием позволяет распространить сетевой подход на любые алгоритмы, в том числе содержащие любое количество циклов. [47]
Однако сравнение двух алгоритмов на основе функций трудоемкости расходится с результатами их сравнения по реально наблюдаемым временам выполнения. Основной причиной такого расхождения является различная частотная встречаемость элементарных операций, порождаемая разными алгоритмами, и различие во временах выполнения элементарных операций на реальном процессоре. Возникает задача перехода от функции трудоемкости к оценке времени работы алгоритма на конкретном процессоре - мы хотим определить оценку времени работы программной реализации алгоритма ( Тд ( п)) на основе знания / д ( п) - функции трудоемкости алгоритма для худшего, лучшего или среднего случая. [48]
Если сложность алгоритма характеризует потребность алгоритма в памяти, то трудоемкость - его потребность во времени, связанном с периодом работы совокупности устройств, средствами которых реализуется алгоритм. Трудоемкость алгоритма иначе называют сложностью вычислений. Оценивается трудоемкость алгоритма количеством операций, выполняемых с целью обработки, ввода и вывода информации в процессе решения задачи. Каждой реализации алгоритма присущ элемент случайности, связанный с тем, что исходные данные представляют собой в общем случае случайную выборку из множества исходных данных, к которым применим алгоритм. [49]