Kombinatorna eksplozija

U matematici kombinatorna eksplozija opisuje efekat funkcija koje rastu vrlo brzo. Primeri takvih funckija uključuju faktorijel funkciju i njoj srodne funkcije. Patološki primer kombinatorne ekpslozije uključuje funkcije kao što je Akermanova funkcija.

Primer u računarstvu

Kombinatorna eksplozija se može javiti u računarskim okruženjima na način analogan komunikacijama i više-dimenzionalnim prostorima. Zamislite jednostavan sistem sa samo jednom promenljivom,promenljivom A. Sistem tada ima dva moguca stanja, A = tačno i A = netačno. Dodavanjem jos jedne promenljive,promenljive B,sistem dobija četiri moguća stanja, A=tačno B=tačno, A=tačno B=netačno, A=netačno B=tačno, A=netačno B=netačno. Sistem sa n promenljivih ima 2ⁿ mogućih stanja,dok sistem sa n promenljivih od kojih svaka ima Z mogućih stanja (a ne samo dva,tačno ili netačno) imaće Zⁿ mogućih stanja.

Moguća stanja mogu da se posmatraju kao lista čvorova stabla visine n,gde svaki čvor ima Z dece. Ovaj nagli porast lista čvorova može biti koristan u oblastima kao što su pretraživanje,jer se mnoštvu rezultata može pristupiti bez potrebe za dubokim spuštanjem,ali to takodje može biti i smetnja kod korišćenja tih objekata.

Zamislite hijerarhiju klasa u objektno-orijentisanom jeziku. Hijerarhija se može posmatrati kao drvo,sa različitim tipovima predmeta nasledjenih od roditelja. Ako različite klase moraju biti kombinovane,kao u poređenju (poput A < B),onda broj mogućih kombinacija koje se mogu javiti eksplodira.Ako svako poređenje treba da se programira onda uskoro sistem postaje nerešiv i za mali broj klasa. Višestruko nasleđivanje može da reši taj problem dozvoljavajući potklasi da ima više roditelja bez narušavanja postojeće hijerarhije.

Na primer,zamislite hijerarhiju gde različito povrće nasleđuje od svojih pra vrsta. Pokušaj da se uporedi ukus svakog povrća sa ostalima postaje nerešiv jer hijerarhija sadrži samo informacije o genetici i ne pominje ukus. Međutim,umesto da se piše poređenje šargarepa/šargarepa, šargarepa/krompir, šargerepa/krastavac, krompir/krompir, krompir/krastavac, krastavac/krastavac, oni mogu svi nasleđivati od razlicitih klasa ukuse ujedno čuvajući svoje trenutne hijerarhije bazirane na pra vrstama,pa se kod svih može vršiti ukus/ukus poređenje.

Primer u aritmetici

Pretpostavimo da imamo faktorijel broja n:

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

Onda je 1! = 1, 2! = 2, 3! = 6, and 4! = 24. Međutim,brzo dolazimo do ekstremno velikih brojeva,čak i za relatvno malo n. Na primer, 100! = 9.33262154 × 10¹⁵⁷, broj toliko veliki da ne može biti prikazan na većini digitrona.