neprihlásený Streda, 1. decembra 2021, dnes má meniny Edmund
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:
                               
 

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).

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".