This is an old version of the compendium, written Nov. 18, 2013, 10:16 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 (mange) rekurrenser på formen

$$ T(n) = aT(^n/_b) + f(n) \\ a \ge 1, b \ge 1 $$

Denne typen rekurrenser oppstår gjerne i sammenheng med splitt-og-hersk algoritmer, f.eks. Mergesort. Problemet deles opp i $a$ deler av størrelse $^n/_b$

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