This is an old version of the compendium, written Nov. 18, 2013, 10:19 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$Test

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