neprihlásený Sobota, 4. decembra 2021, dnes má meniny Barbora
P vs NP pre každého. Čo by znamenalo P != NP a čo P = NP


Diskusia k článku: P vs NP pre každého. Čo by znamenalo P != NP a čo P = NP

Prispievajte do diskusií ako prihlásený užívateľ.

Komentár, na ktorý odpovedáte:
                               
 

Ak by bola zavislost kvadraticka a nie linearna (podobne je to zjednodusene a nezodpoveda to celkom kvadratickej zavislosti vo vseobecnom zmysle), tak zatialco pri vstupe 1 znak potrebujeme 1 krok na vypocet, pri velkosti vstupu 25 znakov potrebujeme az 25^2 = 625 krokov vypoctu! No a 25 a 625 je nenaaaaapadny rozdil. Pri velkosti vstupu 50 znakov (program nacita a bude oparovat s 50 znakmi), postup s kvadratickou zlozitostou potrebuje az 50^2 = 2500 krokov! A zase 50 a 2500 je rozdiel. Pri 10 000 spracuvanych znakoch to bude pri kvadratickej zlozitosti az 100 000 000 potrebnych krokov a opat 10 000 krokov a 100 000 000 krokov je rozdiel.

Pr kubickej zlozitosti je to este horsie, napr. pri 25 znakoch potrebujeme az 25^3 = 15625 krokov vypoctu, pri 50 spracuvanych znakoch az 125000 krokov no a pri 10 000 znakoch az 1 000 000 000 000 krokov.

Meno:


Titulok:


Text:


Prihláste sa a povoľte si emailové notifikácie na odpovede na Váš príspevok.

Overovací text:



Pre overenie, že komentár sa nepridáva automatizovanými prostriedkami, prosím prepíšte text, ktorý vidíte na obrázku. Písmená musíte zadávať rovnako ako na obrázku veľké. Pokiaľ text neviete prečítať, kliknite prosím na tlačidlo "Obnoviť obrázok". V texte sa používajú iba znaky "BCDJKMPRSVWXY1234589".