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.