Válasz
Egy algoritmus polinom (polinom futási idővel rendelkezik), ha néhány $ k, C > 0 $, a $ n $ méretű bemenetek futási ideje legfeljebb $ Cn ^ k $. Ezzel egyenértékűen egy algoritmus polinom, ha néhány $ k > 0 $ esetében a $ n $ méretű bemenetek futási ideje $ O (n ^ k) $. Ez magában foglalja a lineáris, a másodfokú, a köbös és egyebeket. Másrészt az exponenciális futási idővel rendelkező algoritmusok nem polinomok.
Vannak dolgok között – például a faktoring legismertebb algoritmusa $ O (\ exp (Cn ^ {1 / 3} \ log ^ {2/3} n)) $ valamilyen állandó $ C esetén > 0 $; egy ilyen futási idő sub-exponenciális néven ismert. Más algoritmusok futhatnak $ O (\ exp (A \ log ^ C n)) $ időben néhány $ A > 0 $ és $ C > 1 $, és ezeket kvázi-polinom nak nevezik. Ilyen algoritmust a közelmúltban követeltek diszkrét naplózás miatt kis jellemzők felett.
Megjegyzések
- Lásd még itt .
- Mi az a k és a C?
- Ezek paraméterek.
- Tehát az állandó idejű algoritmusok polinomnak tekinthetők, helyesek?
- A konstans idejű algoritmusok a polinom idő algoritmusok speciális esetei.
Válasz
Egy algoritmus futtatása némi számítási időt igénybe vehet. Ez elsősorban attól függ, hogy az algoritmus mennyire összetett. A számítógépes tudósok módszert alkalmaztak az algoritmus osztályozására annak viselkedése alapján, hogy hány műveletet kell végrehajtania (több opció több időt vesz igénybe).
Az egyik osztály polinomiális időbonyolultságot mutat. Vagyis a műveleti bonyolultság arányos a $ n ^ c $ -val, míg n a bemenet mérete és c valamilyen állandó. A név nyilvánvalóan a $ n ^ c $ miatt következik be, amely polinom .
Vannak más algoritmusok is, amelyek a bemenet méretétől függetlenül állandó időt vesznek igénybe. Néhányan $ 2 ^ n $ időt vesznek igénybe (igen, a legtöbb esetben tényleg slllooooww).
Egyszerűen túl egyszerűsítettem a laikusok számára, és hibákat mutathattam be. Tehát olvassa el többet https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
Megjegyzések
- A Wolfram oldalán olvastam, hogy a polinom idő algoritmusokat " gyors " . Azt hallom azonban, hogy sokan azt mondják, hogy a logaritmikus vagy lineáris idő algoritmusokat részesítik előnyben a polinomiális idő algoritmusok helyett. Félreértem a " fast " szó használatát?
- A logaritmikus és a lineáris is polinom. Azt hiszem, a ' fast ' valószínűleg valami olyasmit jelent, mint ' valódi használat '.
Válasz
Laikus szavakkal ez az algoritmus futási ideje.
Az algoritmusok (növekedés) sorrendje lehet Big-oh (O), little-oh (o), omega (Ω) vagy theta (Θ).
Ha problémái adódnak az RR kiszámításával, kérjük, tekintse meg néhány kérdésemet, amelyeket korábban feltettem, és szavazzon, ha megértette.
Mondja el, hogy van egy for ciklusa:
for(i=1 to n) x++ A kóddarab sorrendje vagy időbeli összetettsége: O (n)
Miért nagy-ó? Mivel a kóddarab legrosszabb esetét akarjuk.
Olvassa el itt (ezek meghatározzák az algoritmus bonyolultságát, és tájékoztatják az algoritmusok polinomiális időben történő végrehajtásáról):
http://en.wikipedia.org/wiki/NP_(complexity) http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-hard Összefoglaló:
http://www.multiwingspan.co.uk/a23.php?page=types
Megjegyzések
- Ez nem ' nem felel meg pontosan a kérdésre: polinomiális idő nem " az algoritmus " futási ideje. Ehelyett egy algoritmus futási ideje lehet polinom stb. Jobbá teheti a választ, ha pontosabbá teszi. Például valóban el kell olvasnunk 3 Wikipédia-cikket valamiről, vagy valóban tudnunk kell még valamit a Big Oh-ról?