Oversikt
Relevante deler av læreboken:
- Kapittel 1 (O-notasjon), ikke 1.4
- Seksjon 3.1 (µþ¾±²Ôæ°ù²õø°ì og binære søketrær)
- Seksjon 2.3 (°Õ°ùæ°ù)
µþ¾±²Ôæ°ù²õø°ì
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
°Õ°ùæ°ù
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.