Не так много алгоритмов имеют оценку сложности выше полиномиальной. Оценки сложности у большинства комбинаторных алгоритмов относятся ко второму классу.
Для них время решения Т как функция от размерности задачи T=f(n) имеет характер, показанный на рисунке. До какого-то критического значения nкр время счета нарастает медленно, а затем следует резкий скачок.
Т
0 nкр n
Такое явление называют комбинаторным взрывом. От него не спасает самый быстродействующий компьютер. Для каждой отдельной задачи значение nкр может сдвигаться в ту или другую сторону.
Оно зависит от всех факторов, перечисленных в начале § 5.5. Но рано или поздно при увеличении размерности задачи время решения резко возрастет, и наступит явление комбинаторного взрыва.
Возможность комбинаторного взрыва – это основная опасность, которую следует учитывать при выборе метода решения комбинаторной задачи.
