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: comment
Od: gandor
|
Pridané:
2010-08-30 16:36:27
Pokusim sa trocha poludstit: polynomialny algoritmus moze ten problem vypocitat rychlejsie pre nejaky velmi velky vstup.
Co je nam to ale platne, ked taky velky vstup v praxi nemusime nikdy potrebovat...
Ci nastane tento efekt, kedy je exponencialny algoritmus v praxi vyhodnejsi zalezi od:
1, velkosti vstupnych dat
2, ako male su koeficienty v exponenialnom algoritme
3, aky velky je stupen polynomu
4, ako velke su koeficienty v polynomialnom algoritme
Zhrnute dokopy na priklade:
Majme vstup o 10 prvkov.
Exponencialny algoritmus 2^N (kde N predstavuje pocet prvkov na vstupe = u nas 10).
Polynomialny algoritmus N^4
V tomto pripade exponencialny algoritmus musi vykonat 2^10=1 024 operacii.
Polynomialny 10^4=10 000 operacii. Polynomialny algoritmus by teda isiel dlhsie.
Pri zvecseni vstupu na N=20 nam da polynomialny algoritmus 160 000 operacii ALE exponencialny dava 1 048 576 operacii...
|