Комбинаторный взрыв

Комбинаторный взрыв — термин, используемый для описания эффекта резкого («взрывного») роста временной сложности алгоритма при увеличении размера входных данных задачи.

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

Происхождение названия связано с тем, что для решения задачи не удается найти иного способа, кроме полного перебора всех возможных вариантов. В этом случае время, требуемое для решения, пропорционально количеству всех возможных конфигураций, которое определяется из тех или иных комбинаторных соображений (сочетания, перестановки).

Для обхода проблемы комбинаторного взрыва ищут специальные методы решения, в частности, применяют эвристические алгоритмы.

Источник: Википедия

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я