1. COMP.CS.300 Tietorakenteet ja algoritmit 1 »
  2. Kurssiviikko 8 - Amortisoitu kompleksisuus »
  3. Kurssiviikko 8

Kurssiviikko 8

Itseopiskelu

Viikon aiheet: (i) Amortisoitu tehokkuus,(ii) Tehokkuuden testaaminen ja parantaminen, (iii) Satunnaistaminen

Aiheiden opetusvideot ja kalvot:

Amortisoitu tehokkuus ja STL:n vectorin muistinhallinta

video: amortisoitu-tehokkuus

kalvot: amortisoitu tehokkuus

Asymptoottisen tehokkuuden testaaminen

video: tehokkuuden-testaaminen

kalvot: tehokkuuden testaaminen

Amortisoitu tehokkuus ja STL:n vectorin muistinhallinta

Amortisoitu tehokkuus on
Oletetaan, että STL-vektoria \(v\) käytetään ja alkioiden lisääminen vektorin \(v\) loppuun on ainoa operaatio mitä tehdään. Oletetaan myös, että vectorin \(v\) koko kaksinkertaistuu tilanteissa, joissa \(v\):n muisti loppuu. Mikä seuraavista pätee yhden alkion lisäämisen tehokkuudesta?

Asymptoottisen tehokkuuden testaaminen

Mitkä seuraavista väitteistä tehokkuuden testaamisesta ovat totta?
Oletetaan, että algoritmille \(X\) meillä on suuri kokoelma syötetapauksia, joissa tapausten koot kattavat useita suuruusluokkia. Oletetaan, että suoritamme \(X\) kaikille syöteille ja mittaamme suoritusajat (esimerkiksi sekunneissa). Jos haluamme sanoa jotain algoritmin \(X\) asymptoottisesta tehokkuudesta, miksi meidän pitäisi tehdä jonkinlainen tilastollinen analyysi mittauksista?

Vinkkejä todellisen tehokkuuden parantamiseen

Valitse menetelmät, joita voidaan käyttää parantamaan jonkin ohjelman todellista tehokkuutta.
Oletetaan, että C++:ssa vektoriin \(v\) on tallennettu \(n\) lukua ja \(n\) on hyvin suuri. Missä seuraavista tilanteista on järkevää lajitella vektorin \(v\) alkiot etukäteen?
Oletetaan, että C++:ssa meillä lajittelematon vektori \(vMax\), jossa on suuri määrä lukuja. Oletetaan myös, että lisäämme usein uusia lukuja vektoriin \(v\), mutta emme koskaan poista lukuja siitä. Oletetaan, että tarvitsemme lisäksi vektorin \(v\) suurimman luvun. Mikä seuraavista on vähiten tehokas tapa laskea suurin luku?

Satunnaistaminen

Mikä on pätevä syy käyttää satunnaistamista joissakin algoritmissa?
Kun satunnaistaminen lisätään pikalajitteluun pahimpien tapausten välttämiseksi, miten se yleensä lisätään?
Oletetaan, että on olemassa vektori \(v\), jossa on \(n\) alkiota ja kaikki vektorin \(v\) alkiot sekoitetaan satunnaisesti. Mitä voidaan sanoa tästä sekoitusoperaatiosta?
Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.
Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?
Oliko videoiden sisällössä jotain erityisen vaikeaa? Entä mielenkiintoista? Jotain josta haluaisit oppia lisää?

Lisäinformaatiota aiheesta:

On erilaisia mielipiteitä siitä, miten C++-koodin tehokkuutta kannattaisi parantaa. Seuraavasta linkistä löytyy keskustelua aiheesta. Varoitus: keskustelu on melko teknistä. -Keskustelu stackoverflow:ssa:

Viikko08 - Sanasto

Viikkoharjoitusten palautettavat kotitehtävät

Tällä viikolla palautettavat tehtävät