Параллельное программирование



              

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


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

 \begin{equation} \frac{C_{m+n+1}^{n+1}}{C_{m+n}^n}=\frac{(m+n+1)(m+n)\ldots (m+1)n!}{(n+1)!(m+n)\ldots(m+1)}=\frac{m+n+1}{n+1}=\frac{m}{n+1}+ 1 \end{equation}

(4.5)

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

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

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




Содержание  Назад  Вперед