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:18
Vela zalezi aj od vysvetlenia. Ak ma program linearnu algoritnmicku zlozitost, tak pocet krokov potrebnych na vyriesenie problemu je priamo umerny mnozstvu vstupnych dat.
Veeeeeeeeeeelmi zjednodusene (nezodpoveda definicii linearnej funkcie y = ax+b): napr. ak program nakrmime poctom "n" dat, tak po "n" krokoch mame vysledok. Ak nabachame do programu "2n" vstupnych dat, na vypocet potrebujeme "2n" krokov ... atd az vseobecne "kn".
Napr. program potrebuje data v podobe 250 znakov no a po 250tich krokoch mame vysledok. Ak vsak vstupne data bude 500 znakov, potrebujeme uz 500 krokov na ukoncenie vypoctu. Ak program bude na zaciatku nacitavat a operovat (spracuvat 10 000 znakov, ktore budu tvorit vstup), potrebujeme az 10 000 krokov programoveho postupu na ukoncenie vypoctu (behu programu).
|
neprihlásený 