Порядки сложности оценок методов
Алгоритм
Порядок
Радо–Эдмондса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
n
Динамическое программирование . . . . . . . . . . . . . . . . . .
n
2
Локальных улучшений . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
n
3
Полного перебора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p
n
n
2
Ветвей и границ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p
n
+1
+
p
n
n
Случайного поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
k
(
n
)
n
2
Рис. 8. Графическое сравнение методов
решению надо присоединить еще
q
исходных кодов
p
раз. В итоге
для вычисления целевых функций потребуется
n
i
=1
p
i
iq
элементарных
операций чтения. Получаем оценку сложности для метода ветвей и
границ:
ϕ
в–г
(
n
) = (1 +
p
n
−
p
2
)
p
(
p
+ 1) +
n
i
=1
p
i
iq.
Конечно, это оценка для случая, когда потребуется обход всего
дерева, что маловероятно. Тем не менее, по порядку величины она
сопоставима с оценкой для метода полного перебора.
Ниже приведены все вычисленные порядки сложности для различ-
ных методов, а на рис. 8 — графическое сравнение методов при
p
= 2
.
Графики построены только для небольших значений входных данных,
так как рост функций сильно отличается и их сложно отобразить на
одном рисунке.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 3 31
