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:
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Re: ...som asi za kopec...
Od: Pjetro de
|
Pridané:
2010-08-18 07:52:28
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.
|
neprihlásený 