Algoritmin suoritusaika on aina enintään 1 sekunti riippumatta syötetietojen koosta; tietokoneesta, jolla algoritmi ajetaan; tai algoritmin koodaamiseen käytetystä kielestä.

Riittävän suurelle \(n\), \(f(n)\) ei ole koskaan suurempi kuin jokin vakio.

Funktio \(f(n)\) ei riipu \(n\):stä.

Algoritmissa ei ole for- tai while-silmukoita.

Kysymys 3

Mitä iso-omega( \(\Omega\)) kuvaa?

algoritmin ajonaikaisen tehokkuuden ylärajaa, kun syötteen koko on riittävän suuri

algoritmin ajonaikaisen tehokkuuden alarajaa, kun syötteen koko on riittävän suuri

algoritmin toteuttamiseen tarvittavien pseudokoodirivien tarkka lukumäärää

sekä ylä- että alarajaa algoritmin ajonaikaiselle tehokkuudelle, kun syötteen koko on riittävän suuri

Kysymys 4

Oletetaan, että algoritmeja A ja B voidaan käyttää saman asian laskemiseen. Mikä seuraavista väittämistä on totta?

Jos A suoritetaan lineaarisessa ajassa ja B logaritmisessa ajassa, A on nopeampi, kun syötetyn datan koko on riittävän suuri.

Jos A suoritetaan linearitmisessa ajassa ja B logaritmisessa ajassa, A on nopeampi, kun syötetyn datan koko on riittävän suuri.

Jos A suoritetaan neliöllisessä ja B lineaarisessa ajassa, B on nopeampi, kun syötetyn datan koko on riittävän suuri.

Jos A suoritetaan logaritmisessa ajassa ja B vakioajassa, A on nopeampi, kun syötetyn datan koko on riittävän suuri.

Jos A suoritetaan lineaarisessa ajassa ja B linearitmisessa ajassa, A on nopeampi, kun syötetyn datan koko on riittävän suuri.

Kysymys 5

Oletetaan, että algoritmin funktio on \(f(n)\) ja tiedämme, että \(f(n)\) kuuluu ryhmään \(O(n)\). Mikä seuraavista väittämistä on totta? (Moni kuin yksi voi olla totta.)

\(f(n)\) kuuluu ryhmään \(O(1)\)

\(f(n)\) kuuluu \(O(n \log n)\)

\(f(n)\) kuuluu \(O(\log n)\)

\(f(n)\) kuuluu ryhmään \(O(n^2)\)

Kysymys 6

Oletetaan, että algoritmin funktio on \(f(n)\) ja tiedämme, että \(f(n)\) kuuluu ryhmään \(O(g(n))\) ja myös :math:` Omega(h(n))`. Mikä seuraavista väittämistä on aina totta?

on olemassa vakiot \(c_1\) ja \(c_2\) siten että asymptoottisesti \(f(n)\) kasvaa vähintään yhtä nopeasti kuin \(c_1 g(n)\) ja korkeintaan yhtä nopeasti kuin \(c_2 h(n)\)

math:	“g(n) = h(n)”.

on olemassa vakiot \(c_1\) ja \(c_2\) niin että asymptoottisesti \(f(n)\) kasvaa korkeintaan yhtä nopeasti kuin \(c_1 g(n)\) ja vähintään yhtä nopeasti kuin \(c_2 h(n)\)

on olemassa vakio \(c_1\) tai vakio \(c_2\) siten, että asymptoottisesti joko \(f(n) = c_1 g(n)\) tai \(f(n) = c_2 h(n)\).

Kysymys 1

Mikä väite pätee lisäyslajitteluun?

se toimii log(n) tehokkuudella parhaan tapauksen syötteellä

se toimii lineaarisessa ajassa huonoimman tapauksen syötteellä

se toimii neliöllisellä tehokkuudella pahimman tapauksen syötteellä

Kysymys 2

Oletetaan, että taulukko \(A\) annetaan syötteenä lisäyslajittelulle ja oletetaan, että lisäyslajittelu tuottaa taulukon \(A\), jonka elementit on lajiteltu pienimmästä suurimpaan. Mikä on pahimman tapauksen syöte \(A\)?

kaikki syötetaulukot \(A\) ovat pahimpia tapauksia

taulukko \(A\), jonka elementit on lajiteltu suurimmasta pienimpään

taulukko \(A\) jonka ensimmäinen elementti on pienin ja muut elementit voivat olla missä tahansa järjestyksessä

Kysymys 3

Oletetaan, että meillä on taulukko \(A\), jossa on numeroita. \(A_{best}\) ja \(A_{worst}\) vastaavat lisäyslajittelun parasta ja huonointa syötettä. Mikä seuraavista on totta?

Sekä \(A_{best}\) että \(A_{worst}\) suoritusaikaiset tehot kuuluvat samaan \(\Theta\) -joukkoon.

Kohteen \(A_{best}\) suoritusaikainen tehokkuus ei kuulu mihinkään \(\Theta\) joukkoon. Samaa voidaan sanoa \(A_{pahin}\) suoritusajan tehokkuudesta.

\(A\):lle on olemassa koko, jonka suoritusaikainen tehokkuus pahimmalle tapaukselle \(A_{worst}\) voi olla miljoona kertaa suurempi kuin parhaalle tapaukselle \(A_{best}\).

Extra links on the topic:

Khan Academy material on asymptotic notation

Week04 - Glossary

Viikko04 - Sanasto

Palauta viikkotehtävät¶

Kysymyksiä tälle viikolle

Kurssiaiheet 3 ja 4¶

Itseopiskelu (videot ja kalvot suomeksi)¶

hajota ja hallitse¶

Pikajärjestäminen (Quicksort)¶

Pikajärjestäminen: ositus (Partition)¶

Lomitusjärjestäminen (Mergesort)¶

Lomitusjärjestäminen: Lomitus (Merge)¶

Luentokysymykset¶

Palauta viikkotehtävät¶

Kurssiaihe 4¶

Itseopiskelu (videot ja kalvot suomeksi)¶

O-notaatio¶

Omega- ja Theta-notaatiot¶

Tehokkuuden analysointi pseudokoodista¶

Järjestysalgoritmien tehokkuuden vertailu¶

O, Omega, Theta, paras, huonoin¶

Palauta viikkotehtävät¶