Mitä eroa on välillä O (n!) Vs. O (2 ^ n) ajan monimutkaisuus?


Vastaus 1:

O (n!) Antaa huomattavasti enemmän resursseja (ajan suhteen) ratkaisijalle.

Tarkista seuraavat kolme kuvaa:

Kuva 1: Heti kun n = 3, tekijäluokka johtaa.

Kuva 2: Lisää resurssierot nopeasti nopeasti viiden lisävaiheen jälkeen.

Kuva 3: Tekijäluokka näyttää eksponentiaalisen luokan yhtenä hiekkapartikkelina verrattuna Himalajan vuoreen. Ja tämä on juuri kun syöttö on vain 15 yksikköä.

Kuten saatat huomata, kun syöttökoosi kasvaa, samoin on ero ”tekijänopeudessa”.

Joten periaatteessa aikahierarkia kertoo, että mitä enemmän resursseja sinulla on, sitä enemmän ongelmia voit ratkaista.


Vastaus 2:

n! ja 2 ^ n ovat molemmat eksponentiaalisia funktioita - mutta n! On paljon vahvempi kuin 2 ^ n. n! Tavoittaa äärettömyyteen paljon nopeammin.

Se on kuin ero x ^ 2 - x ^ 200 - ne ovat molemmat polynomifunktioita - mutta x ^ 200 on paljon vahvempi.

Monimutkaisusteoriassa - nämä erot eivät ole kovin merkittäviä tai merkityksellisiä; x ^ 2 ja x ^ 200 ovat molemmat poly (x) -funktioita - molemmat polynomifunktioluokassa - kuten kaikki funktiot muodossa x ^ k, kun taas k on vakioluku; Ja n! ja 2 ^ n ovat molemmat exp (n) - ne molemmat kuuluvat eksponenttifunktioiden luokkaan - mutta eivät poly (n). [jokainen poly (x) on myös exp (x), koska exp (x) on O (exp (x)) (ja poly (x) on O (poly (x))]]