Oversikt
Relevante deler av læreboken:
- Kapittel 1 (O-notasjon), ikke 1.4
- Seksjon 3.1 (Binærsøk og binære søketrær)
- Seksjon 2.3 (Trær)
Binærsøk
O-notasjon
Eksempler:
Følgende video går gjennom flere eksempler, handler om hvordan man finner c og n0, og i hvilke tilfeller man kanskje foretrekker "tregere algoritmer".
Finn riktig c og n0: PDF
Kodeanalyse
Følgende video viser hvordan man analyserer koden sin ved hjelp av O notasjon
Kodeanalyse: PDF
Trær
Rekursive funksjoner i Logiske Metoder
Binære søketrær
Oppgaver
Vi anbefaler å implementere alle algoritmer dekket av pensumet.
O Notasjon
Fra boka:
R-1.9, R-1.11-1.15
C-1.8
C-1.19 (ignorer minnerestriksjonen)
C.1.24
Variant av C.1.24: La A være et array (lengde n) og ikke en matrise. Finn en algoritme som teller hvor mange 1ere A inneholder. Tips: dette kan gjøres raskere enn lineær tid.