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

Сложность алгоритма


Если считать, что чаще всего из одной вершины исходят n граней, то число решаемых систем n линейных уравнений при поиске смежных вершин определяется как

r = n ? (m + n - n) = n ? m.

Число вершин k, по которым производится перемещение в поисках решения, предсказать трудно. Однако очевидно, что k << Cnm + n, т.к. лишь локально затрагивается некоторый "бок" многогранника R. Считая, как и раньше, m

n, можно оценить сложность решения данным методом, как O(kn5). Эта сложность является полиномиальной.



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