Tehokkuustesti

Toteuta kurssikirjan luvussa 2.1.4 kuvattu tehokkuustesti omalla koneellasi. Toteuta algoritmit haluamallasi ohjelmointikielellä 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.

Pythonissa voit käyttää moduulin time funktiota time seuraavasti:

import time

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

Javassa voit puolestaan käyttää metodia System.nanoTime seuraavasti:

long alku = System.nanoTime();
// testattava koodi
long loppu = System.nanoTime();
System.out.println("aikaa kului " + (loppu-alku)/1e9 + " s");

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: