Сложность алгоритма прямого перебора

Основным элементом решаемой задачи является решение системы n линейных уравнений. Сложность решения такой системы можно считать полиномиальной O(n3). Число решений определяется как Cnm+n. Чтобы найти зависимость сложности от основных параметров n и m, определим, во сколько раз увеличивается сложность при увеличении размерности n на единицу:

(4.5)

Если считать, что m соразмерно с n, т.е. m

n, то увеличение размерности n на единицу при больших n примерно в два раза увеличивает сложность задачи, т.е. ее сложность определяется как O(2nn3). Это экспоненциальная сложность, практически сильно ограничивающая размерность решаемых задач.

Простота параллельного алгоритма прямого перебора делает его привлекательным для значений n порядка двух-трех десятков. Для большей размерности необходимо искать алгоритмы полиномиальной сложности.

Содержание раздела

Главная сайта