This is an old version of the compendium, written Nov. 18, 2013, 10:11 p.m. Changes made in this revision were made by oyvindrobertsen. View rendered version.

TDT4120: Algoritmer og datastrukturer

# Lenkede lister ## Kjøretider || **Handling** || **Kjøretid** || || Innsetting på starten || O(1) || || Innsetting på slutten || O(n) || || Oppslag || O(n) || || Slette element || oppslagstid + O(1) || # Trær # Traversering # Rekursjon

## Master teoremet Master teoremet er en kokebokløsning for å finne kjøretiden til rekurrenser på formen $$ T(n) = aT(n/b) + f(n) , a \ge 1, b \ge 1 $$ # Graf-algoritmer

# Kjøretidsberegning # Sortering # Korteste vei ## Dijkstras algoritme # Maksimal flyt # Dynamisk programmering # Grådige algoritmer # Problemkompleksitet ## P, NP, NPC