vastaus
Algoritmi on polynomi (sillä on polynomin ajoaika), jos jotkut $ k, C > 0 $, sen käyntiaika koon $ n $ syötteillä on enintään $ Cn ^ k $. Vastaavasti algoritmi on polynomi, jos joillekin $ k > 0 $: lle sen käyntiaika koon $ n $ syötteillä on $ O (n ^ k) $. Tähän sisältyy lineaarinen, neliöllinen, kuutio ja paljon muuta. Toisaalta, eksponentiaaliset ajoajat sisältävät algoritmit eivät ole polynomeja.
Välillä on asioita – esimerkiksi tunnetuin factoring-algoritmi kulkee ajassa $ O (\ exp (Cn ^ {1 / 3} \ log ^ {2/3} n)) $ jostain vakiosta $ C > 0 $; tällainen juoksuaika tunnetaan nimellä subeksponentiaalinen . Muut algoritmit voisivat toimia ajassa $ O (\ exp (A \ log ^ C n)) $ joillekin $ A > 0 $ ja $ C > 1 $, ja nämä tunnetaan nimellä lähes polynomi . Tällainen algoritmi on hiljattain vaadittu erillisestä lokista pienten ominaisuuksien vuoksi.
Kommentit
- Katso myös täällä .
- Mikä on k ja C?
- Ne ovat parametreja.
- Eli vakioaikaisia algoritmeja pidetään polynomina, oikein?
- Vakiovuorealgoritmit ovat erityinen tapaus polynomiaika-algoritmeja.
Vastaus
Algoritmin suorittaminen voi viedä jonkin aikaa laskentaan. Se riippuu pääasiassa siitä, kuinka monimutkainen algoritmi on. Tietojenkäsittelytieteen tutkijat ovat tehneet tavan luokitella algoritmi sen käyttäytymisen perusteella sen mukaan, kuinka monta operaatiota sen on suoritettava (useampi optio vie enemmän aikaa).
Yksi luokan luokista osoittaa polynomisen ajan monimutkaisuuden. Eli operatiivinen monimutkaisuus on verrannollinen $ n ^ c $: een, kun taas n on syötteen koko ja c on jokin vakio. Nimi on tietysti johtuen $ n ^ c $: sta, joka on polynomi .
On olemassa myös muita algoritmityyppejä, jotka vievät vakioaikaa syötteen koosta riippumatta. Jotkut vievät $ 2 ^ n $ aikaa (kyllä, todella slllooooww suurimman osan ajasta).
Yksinkertaistin sen vain maallikoille ja olen saattanut aiheuttaa virheitä. Joten lue lisää https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
Kommentit
- Luin Wolframista, että polynomi-aikalgoritmien sanotaan olevan " nopeita " . Kuulen kuitenkin, että monet ihmiset sanovat suosivan logaritmisia tai lineaarisia aika-algoritmeja polynomi-aika-algoritmien sijaan. Ymmärränkö väärin sanan " fast " käyttöä?
- Logaritminen ja lineaarinen ovat myös polynomia. Luulen, että ' fast ' tarkoittaa todennäköisesti jotain sellaista kuin ', joka on todennäköisesti todennäköisempää todellinen käyttö '.
Vastaa
Maallikkona se algoritmin käyntiaika.
Algoritmien järjestys (kasvu) voi olla iso-oh (O), pieni-oh (o), omega (Ω) tai teeta (Θ).
Jos sinulla on ongelmia RR: n laskemisessa, tutustu joihinkin kysymyksiin, jotka kysyin aiemmin, ja äänestä, jos ymmärrät.
Sano, että sinulla on for loop:
for(i=1 to n) x++ Tämän koodinpätkän järjestys tai aikakompleksi on: O (n)
Miksi iso-oh? Koska haluamme pahimman tapauksen, jossa tämä koodikappale toimii.
Lue täältä (nämä määrittelevät algoritmin monimutkaisuuden ja ilmoittavat sinulle, kuinka algoritmit tehdään polynomiajassa):
http://en.wikipedia.org/wiki/NP_(complexity) http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-hard Yhteenveto:
http://www.multiwingspan.co.uk/a23.php?page=types
kommentit
- Tämä ei ' vastaa tarkasti kysymykseen: polynomiaika ei ole " algoritmin käyntiaika ". Sen sijaan algoritmin ajonaika voi olla polynomi ja niin edelleen. Voisit tehdä vastauksesta paremman tekemällä siitä tarkemman. Pitäisikö meidän todella lukea esimerkiksi 3 Wikipedia-artikkelia jostakin, vai onko meidän edes tiedettävä mitään Big Ohista?