Kurssin materiaalin viikon 4 esimerkissä on sanakirjaa käyttävä algoritmi, joka laskee kierrosten lukumäärän, kun luvut kerätään listasta. Aiemmin viikon 2 tehtävässä oli aiheena toteuttaa samanlainen algoritmi listan avulla.
Kierrosten laskemisen apuna voikin käyttää joko listaa tai sanakirjaa, koska lukuja voi käyttää joko listan indekseinä tai sanakirjan avaimina. Miten tietorakenteen valinta vaikuttaa ratkaisun tehokkuuteen?
Vertaile yllä mainittujen toteutusten tehokkuutta tapauksessa, jossa lista sisältää luvut 1,2,\dots,10^7 satunnaisessa järjestyksessä.
Tässä tehtävässä saat pisteen automaattisesti, kun ilmoitat tulokset ja käyttämäsi koodin ja painat lähetysnappia.
Listatoteutuksen suoritusaika: s
Sanakirjatoteutuksen suoritusaika: s
Testissä käyttämäsi koodi:
