Tehokkuustesti

Toteuta kurssikirjan luvussa 2.1.4 kuvattu tehokkuustesti omalla koneellasi. Toteuta algoritmit Pythonilla ja mittaa niiden suoritusaika, kun $n=10^5$. Käytä testissä satunnaista syötettä, jossa jokaisessa kohdassa merkin $0$ ja $1$ todennäköisyys tulla valituksi on yhtä suuri.

Hyvä tapa mitata koodin suoritusaika on kysyä ajanhetki järjestelmän kellosta juuri ennen koodin suoritusta ja sen jälkeen. Näiden ajanhetkien erotus kertoo, kauanko koodin suoritukseen meni aikaa.

Voit käyttää moduulin time funktiota time seuraavasti:

import time

alku = time.time()
# testattava koodi
loppu = time.time()
print("aikaa kului", loppu-alku, "s")

Huomaa, että kurssikirjassa vertailu on toteutettu Javalla, joka on nopeampi kieli kuin Python. Sen vuoksi voit varautua siihen, että omassa testissäsi aikaa menee enemmän kuin kirjan tuloksissa.

Tässä tehtävässä saat pisteen automaattisesti, kun ilmoitat tulokset ja käyttämäsi koodin ja painat lähetysnappia.

$O(n^2)$-algoritmin suoritusaika: s

$O(n)$-algoritmin suoritusaika: s

Testissä käyttämäsi koodi: