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

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

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