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



              

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


Обобщение линейности дает нам первый большой класс алгоритмов — полиномиальных.

Полиномиальным (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность есть O(p(n)), где p(n) — полином от n. Задачи, где для решения известен алгоритм, сложность которого составляет полином заданной, постоянной и не зависящей от размерности входной величины n степени, называют "хорошими" и относят их к классу P.

Экспоненциальной по природе считается задача сложностью не менее порядка xn, где x — константа или полином от n. Например, это задачи, в которых возможное число ответов уже экспоненциально. В частности, к ним относятся задачи, где требуется построить все подмножества заданного множества или все поддеревья заданного графа. Экспоненциальные задачи относят к классу E.

Соответственно, и алгоритмы, в оценку сложности которых n входит в показатель степени, относятся к экспоненциальным.

Необходимо отметить, что при небольших значениях n экспоненциальный алгоритм может быть даже менее сложным, чем полиномиальный. Тем не менее, различие между этими типами алгоритмов весьма велико и проявляется при больших значениях n.

Особую группу по значениям сложности, близким к полиномиальным, составляют алгоритмы, сложность которых является полиномиальной функцией от log n (поскольку log n растет медленнее, чем n).

Для большей убедительности и сравнения полиномиальных и экспоненциальных алгоритмов приведем таблицу, где единица времени — 1 мкс, а сложность совпадает с необходимым количеством единиц времени для обработки набора n данных:

Таблица 3.1. Сложность и время выполнения

СложностьРазмер задачи — n102030405060nn?n?n52n3n
0.00001 с0.00002 с0.00003 с0.00004 с0.00005 с0.00006 с
0.0001 с0.0004 с0.0009 с0.0016 с0.0025 с0.0036 с
0.001 с0.008 с0.027 с0.064 с0.125 с0.216 с
0.1 с3.2 с24.3 с1.7 мин5.2 мин13.0 мин
0.01 с1.0 с17.9 мин12.7 дней35.7 лет366 веков
0.59 с58 мин6.5 лет3855 веков2·108 веков1.3·1013 веков




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