Комбинаторна експлозија

У математици комбинаторна експлозија описује ефекат функција које расту врло брзо. Примери таквих фунцкија укључују факторијел функцију и њој сродне функције. Патолошки пример комбинаторне екпслозије укључује функције као што је Акерманова функција.

Пример у рачунарству

Комбинаторна експлозија се може јавити у рачунарским окружењима на начин аналоган комуникацијама и више-димензионалним просторима. Замислите једноставан систем са само једном променљивом,променљивом А. Систем тада има два могуца стања, А = тачно и А = нетачно. Додавањем јос једне променљиве,променљиве Б,систем добија четири могућа стања, А=тачно Б=тачно, А=тачно Б=нетачно, А=нетачно Б=тачно, А=нетачно Б=нетачно. Систем са н променљивих има 2^н могућих стања,док систем са н променљивих од којих свака има З могућих стања (а не само два,тачно или нетачно) имаће З^н могућих стања.

Могућа стања могу да се посматрају као листа чворова стабла висине н,где сваки чвор има З деце. Овај нагли пораст листа чворова може бити користан у областима као што су претраживање,јер се мноштву резултата може приступити без потребе за дубоким спуштањем,али то такодје може бити и сметња код коришћења тих објеката.

Замислите хијерархију класа у објектно-оријентисаном језику. Хијерархија се може посматрати као дрво,са различитим типовима предмета наследјених од родитеља. Ако различите класе морају бити комбиноване,као у поређењу (попут А < Б),онда број могућих комбинација које се могу јавити експлодира.Ако свако поређење треба да се програмира онда ускоро систем постаје нерешив и за мали број класа. Вишеструко наслеђивање може да реши тај проблем дозвољавајући поткласи да има више родитеља без нарушавања постојеће хијерархије.

На пример,замислите хијерархију где различито поврће наслеђује од својих пра врста. Покушај да се упореди укус сваког поврћа са осталима постаје нерешив јер хијерархија садржи само информације о генетици и не помиње укус. Међутим,уместо да се пише поређење шаргарепа/шаргарепа, шаргарепа/кромпир, шаргерепа/краставац, кромпир/кромпир, кромпир/краставац, краставац/краставац, они могу сви наслеђивати од разлицитих класа укусе уједно чувајући своје тренутне хијерархије базиране на пра врстама,па се код свих може вршити укус/укус поређење.

Пример у аритметици

Претпоставимо да имамо факторијел броја н:

$n!=(n)(n-1)...(2)(1)$

Онда је 1! = 1, 2! = 2, 3! = 6, анд 4! = 24. Међутим,брзо долазимо до екстремно великих бројева,чак и за релатвно мало н. На пример, 100! = 9.33262154 × 10¹⁵⁷, број толико велики да не може бити приказан на већини дигитрона.