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

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

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

Различают временную и пространственную сложность. Первая определяет время, требуемое на решение задачи заданной размерности с помощью данного алгоритма, а вторая — количество требуемых ресурсов (памяти) при тех же условиях.

Каждый вычислительный алгоритм может быть отнесен к одному из двух классов сложности. В данном случае это множество задач, для решения которых известны алгоритмы, схожие по трудоемкости. В классе 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 операций.

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...