Verktøy

Formelsamling

Til eksamen i dette emnet deles det ikke ut noen formelsamling. Oversikten under er en studieressurs — på eksamen må alt kunnes uten hjelpemidler.

01 Asymptotikk og rekurrenser

$\displaystyle T(n) = aT(n/b) + f(n)$ Masterteoremets rekurrensform
$\displaystyle T(n) = 2T(n/2) + \Theta(n) = \Theta(n \lg n)$ Balansert splitt og hersk (Merge-Sort)

02 Sortering

$\displaystyle \Omega(n \lg n)$ Nedre grense for sammenligningsbasert sortering

03 Datastrukturer

$\displaystyle O(n)$ Build-Max-Heap bygger en haug i lineær tid (ikke $O(n \lg n)$ )

04 Grafer

$\displaystyle O(V + E)$ BFS og DFS med naboliste-representasjon
$\displaystyle d[v] \leftarrow \min\{\, d[v],\; d[u] + w(u,v) \,\}$ Kantoppdatering (Relax)
$\displaystyle O((V + E) \lg V)$ Dijkstra med binær min-haug
$\displaystyle O(V E)$ Bellman-Ford (tåler negative kanter)
$\displaystyle \Theta(V^3)$ Floyd-Warshall (alle-til-alle korteste veier)

05 Kompleksitet

$\displaystyle \Theta(n W)$ Binært ryggsekk-DP — pseudopolynomisk i kapasiteten $W$