Вычислительная сложность алгоритмов

Вычислительная сложность алгоритма – количество элементарных операций, затрачиваемых алгоритмом для решения конкретной задачи. Сложность зависит не только от размерности входных данных, но и от самих данных. Очевидно, что чем сложнее алгоритм в вычислительном плане, тем больше времени и вычислительных ресурсов потребует его выполнение.
Различают временную и пространственную сложность. Первая определяет время, требуемое на решение задачи заданной размерности с помощью данного алгоритма, а вторая – количество требуемых ресурсов (памяти) при тех же условиях.
Каждый вычислительный алгоритм может быть отнесен к одному из двух классов сложности. В данном случае это множество задач, для решения которых известны алгоритмы, схожие по трудоемкости. В классе P вычислительные затраты линейно растут с увеличением размерности. Например, время, требуемое на уборку снега, прямо пропорционально площади. Если ее увеличить вдвое, то и временные затраты также возрастут в два раза. Класс NP включает задачи, для решения которых известны только алгоритмы, сложность которых экспоненциально зависит от размерности данных. Поэтому они, как правило, неэффективны при работе с большими множествами. Примером является задача поиска выхода из лабиринта, временные затраты на который экспоненциально растут с увеличением числа разветвлений.
Определим вычислительные сложнасти алгоритмов поиска кратчайших путей Дейкстры, Флойда, и Данцига.
Вычислительная сложность алгоритма Дейкстры
При каждом пересчете величины d(x) мы совершаем 2 операции (сложение и сравнение). всего при каждой новой итерации алгоритма совершается n-1 такие операции. Всего же в процессе построения дерева путей для одной вершины графа мы совершаем Σ2(n-1)=n2 таких операций. Чтобы получить все кратчайшие пути в графе нам необходимо провести алгоритм дейкстры для каждой из n вершин и затратить n*n2=n3 операций. Если учесть операции окрашивания вершин и выбора min(d(x)) то получим ≈1.5n3 операций для графа с числом вершин равным n.
Вычислительная сложность алгоритма Флойда
Расчет каждого нового элемента матрицы Dm включает в себя 2 операции (сложение и сравнение). Каждая матрица содержит N*N элементов, следовательно при каждой итерации необходимо выполнить 2N2операций. Всего в процессе алгоритма расчитывается N таблиц, то есть вычислительная сложность алгоритма Флойда составляет 2N3 операций.
Вычислительная сложность алгоритма Данцига
Алгоритм Данцига отличается от Флойда только последовательностью выполнения операций, поэтому имеет такую же вычислительную сложность порядка 2N3 операций.

   

Выполненные готовые работы

Так же вы можете купить уже выполненные похожие работы. Для удобства покупки работы размещены на независимой бирже. Подробнее об условиях покупки тут.

 
4.78
zcxfcnkbdfz
Рефераты и контрольные работы по всем отраслям права для студентов юридических ВУЗов, а так же по дисциплине "Правоведение" и другим правовым дисциплинам для студентов не юридических ВУЗов, техникумов, колледжей.