Referanseside · Kapittel 2

Begreper & formler

Alle nøkkelbegrepene og formlene fra Kom i gang, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards8 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Pseudokode

Språk-uavhengig beskrivelse av en algoritme som fremhever logikk fremfor syntaks.

02Løkkeinvariant

Et utsagn som er sant før og etter hver iterasjon av en løkke, brukt til å bevise korrekthet.

03Kjøretid

Antall elementære operasjoner algoritmen utfører som funksjon av $n$ .

04Del-og-hersk

Strategi der problemet deles i delproblemer, løses rekursivt, og kombineres.

05Rekursjon

Et kall til algoritmen i seg selv for mindre instanser av samme problem.

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

A [1.. i - 1] er sortert før hver iterasjon

T (n) = Θ (n^{2})

T (n) = 2 T (n /2) + Θ (n)