aikakompleksisuus, o-notaatio, algoritmin tehokkuus??

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Hei!

Voisikohan joku auttaa ja selventää tällaisia käsitteitä eli aikakompleksisuus, o-notaatio, algoritmin tehokkuus... Määriteltävänä olisi O(k).

Kiitos kaunis!

Kommentit (5)

Vierailija

Aikakompleksisuus tarkoittaa yleensä algoritmin suoritusajan kasvua suhteessa syötteen koon kasvuun. O-notaatio (esim. O(f(k))) tarkoittaa sitä, että kaikkein pahimmalla syötteellä algoritmi vie enintään aikaa f(k):n verran. Funktio f(k) voi olla vähän mikä vain. Mutta siis käytännössä se on lupaus siitä, että algoritmi käyttää aikaa millä tahansa syötteen pituudella k aikaa enintään f(k) verran. Tarkka määrittely on hieman vaikea tähän purkaa, mutta se liittyy siihen miten funktio f kasvaa suhteessa k:hon, joka on siis yleensä syötteen pituus.

Algoritmit ovat tehokkaita, jos niiden suoritusaika ei kasva "hirveästi" verrattuna syötteen pituuteen. Eli on mahdollista, että algoritmi vie aikaa aina enintään saman verran, eli jonkun vakion verran. Tällöin merkitään O(1). Siis olipa syöte miten suuri tahansa - algoritmi suorituu samassa ajassa. Yleensä matematiikassa k on joku vakio, eli O(k) on sama kuin O(1). Jos k kuvastaa syötteen pituutta, O(k) tarkoittaa sitä, että kun syöte kasvaa yhden yksikön, kasvaa aikavaativuuskin yhden yksikön. Aikavaativuus on siis lineaarinen suhteessa syötteen kokoon. Lineaariset algoritmit ovat yleensä myös "riittävän" hyviä.

Aikavaativuus voi kasvaa myös esimerkiksi eksponentiaalisesti suhteessa syötteen pituuteen (merkitään O(2^k)), ne ovat selvästi liian hitaita käytännön tarpeisiin, lukuun ottamatta muutamaa erikoistapausta. Jos algoritmi vie esim. luokkaa O(2^k), voi se esimerkiksi syötteellä jonka pituus on 3, viedä 8 laskenta-askelta. Kuitenkin jos syötteen pituus on vaikka 20, vie se jo yli miljoona laskenta-askelta. Tässä siis f(k) = 2^k.

Vierailija
mariaerika
Hei!

Voisikohan joku auttaa ja selventää tällaisia käsitteitä eli aikakompleksisuus, o-notaatio, algoritmin tehokkuus... Määriteltävänä olisi O(k).

Kiitos kaunis!

Eikös se mennyt niin, että
O(f(k)) tarkoittaa sitä, että algoritmin kompleksisuus on *enintään* f(k),
o(f(k)) tarkoittaa sitä, että algoritmin kompleksisuus on *täsmälleen* f(k)
ja
Ω(f(k) tarkoittaa sitä, että algoritmin kompleksisuus on *vähintään* f(k).

Vierailija

Teräslilja: Ei se noin mene.

Vaan näin:

O(f(k)) tarkoittaa sitä, että algoritmin kompleksisuus on *enintään* f(k),
IsoTheeta(f(k)) tarkoittaa sitä, että algoritmin kompleksisuus on *täsmälleen* f(k)
ja
Ω(f(k) tarkoittaa sitä, että algoritmin kompleksisuus on *vähintään* f(k).

Lisäksi:
o(f(k)) tarkoittaa sitä, että algoritmin kompleksisuus on *aidosti vähemmän kuin* f(k),
ja
pikkuoomega(f(k) tarkoittaa sitä, että algoritmin kompleksisuus on *aidosti enemmän kuin* f(k).

(Miten nuo kreikkalaiset kirjaimet saadaan?)

Vierailija

Niin tarkentaisin vielä Sampsan vastausta, että jos algoritmin aikavaativuus on O(f(k)), niin k:n mittaisella syötteellä algoritmin suoritusaika on korkeintaan vakio * f(k).

Esim. O(k) on sama kuin O(2k) tai O(3k), ja näistä käytetäänkin kaikista nimitystä O(k).

Esimerkkejä vaativuusluokista ("nopeimmasta hitaampaan"):

O(1): Algoritmin suoritus vie aina vakioajan riippumatta syötteen pituudesta.

O(log k): Algoritmin suoritus vie korkeintaan ajan vakio * log(syötteen pituus). Huom. myös vakioaikaiset algoritmit eli luokan O(1) algoritmin kuuluvat tähän luokkaan, koska niiden viemä aika, vakio, on aina pienempää kuin vakio * log(syötteen pituus).

O(k): Algoritmin suoritus vie korkeintaan ajan vakio * syötteen pituus.

O(k²): Algoritmin suoritus vie korkeintaan ajan vakio * syötteen pituus².

Vierailija

Olisiko kellään tietoa (linkkejä,kirjoja) lähteistä, jossa tätä aikavaativuutta ja sen laskemista ja etenkin todistamista käsitellään ihan alusta pitäen kunnollisilla esimerkeillä? Ei siis pelkkää matemaattisten symbolien sekasotkua vaan kunnollinen maallikolle sopiva johdatus aiheeseen.

Saisi melkein olla tyyliä "for dummies". Jostain syystä tämä aikavaativuuden pyörittely on aina ollut minulle vaikeaa

Uusimmat

Suosituimmat