Kurssiviikko 4¶

Mitä iso-O-merkintä ( \(O\) ) kuvaa?

Oletetaan, että algoritmin ajoaikafunktio on \(f(n)\) ja tiedämme, että \(f(n)\) kuuluu ryhmään \(O(1)\). Mikä seuraavista väittämistä on totta?

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

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

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.)

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?

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

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\)?

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?

Lomituslajittelua kutsutaan syötetaulukolla \(A\), jossa on \(n\) elementtiä. Mikä seuraavista on paras yläraja lomituslajittelun käyttämien rekursiotasojen lukumäärälle?

Oletetaan, että pikalajittelun asymptoottinen ajonaikainen tehokkuus analysoidaan, kun aloitustaulukossa \(A\) on :math:n elementtiä. Mitkä seuraavista ovat totta?

Verrataan lomituslajittelua, pikalajittelua ja lisäyslajittelua, mitkä seuraavista ovat totta?

Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?