Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Rekursjon, sortering og søk, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En teknikk der en funksjon løser et problem ved å kalle seg selv på en mindre versjon av det samme problemet. Krever alltid et basistilfelle som stopper kjeden av kall.
Grenen i en rekursiv funksjon som returnerer et svar direkte uten å kalle funksjonen på nytt. Uten et basistilfelle vil rekursjonen aldri stoppe.
En søkealgoritme som finner et element i en sortert liste ved å gjentatte ganger halvere søkeområdet: man sammenligner med midt-elementet og forkaster den halvdelen som ikke kan inneholde svaret. Kjøretid O(log n).
Å ordne elementene i en samling etter en bestemt rekkefølge. Enkle metoder er O(n²); smartere metoder som flettesortering er O(n log n). Sortering er en forutsetning for binærsøk.
En notasjon (store-O) som beskriver hvordan en algoritmes arbeidsmengde vokser med datamengden, uavhengig av konstanter. Lineært søk er O(n), binærsøk O(log n).
Kodesnutter
Kodesnutter fra kapittelet, vist literal.
Fakultet rekursivt
def faktoriell(n): if n <= 1: # basistilfelle return 1 return n * faktoriell(n - 1) # rekursivt tilfelle print(faktoriell(4)) # 24Funksjonen kaller seg selv på et stadig mindre tall til den treffer basistilfellet n <= 1. Hvert kall venter på svaret fra kallet under seg i kall-stacken.
Pseudokode
Pseudokode som forklarer fremgangsmåten steg for steg.
Binærsøk (pseudokode)
binaersok(liste, mål): lav = 0 hoy = lengde(liste) - 1 så lenge lav <= hoy: midt = (lav + hoy) // 2 hvis liste[midt] == mål: returner midt # funnet ellers hvis liste[midt] < mål: lav = midt + 1 # let i høyre halvdel ellers: hoy = midt - 1 # let i venstre halvdel returner -1 # ikke funnetSøket holder to grenser, lav og hoy, og sammenligner med midt-elementet hver runde. Forutsetter at lista er sortert, og halverer søkeområdet hvert trinn.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Forklare hva rekursjon er, identifisere basistilfelle og rekursivt tilfelle, og skrive en enkel rekursiv funksjon
- 02Spore en rekursjon ved å beskrive hvordan kall-stacken bygges opp og rives ned ramme for ramme
- 03Forklare hvordan binærsøk halverer søkeområdet og hvorfor det krever en sortert liste
- 04Bruke O-notasjon til å sammenligne kjøretiden for lineært søk, binærsøk og enkle sorteringsmetoder