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:39
Dalej ak predpokladame, ze na jeden krok vypoctu na istom pocitaci v istom case potrebujeme konstantny cas, tak je zrejme, ze ak napr. spracovanie 50 znakov trva pri linearnej zlozitosti 50 krokov a pri kvadratickej 2500 krokov a kedze pocet potrebnych krokov je 50-nasobny, tak aj cas potrebny na vypocet je pri kvadratickej zlozitosti 50-nasobny.
Exponencialna funkcia je ale este ovela vacsia svina. Ak je zlozitost vypoctoveho algoritmu umerna napr. 2^x, tak pri 25 spracuvanych znakoch to mame 2^25 = 33554432 potrebnych vypoctovych krokov ale pri 50tich spracuvanych znakoch az 2^50 = 1125899906842624 potrebnych krokov, t.j. (2^25 = )33554432-nasobne viac.
|
neprihlásený 