Formelsamling

01 Asymptotisk notasjon

$\displaystyle O(n^a) + \Omega(n^b) + \Theta(n^c) = \Omega(n^b + n^c)$ Summer øvre og nedre grenser hver for seg. Står bare en nedre grense igjen, skrives den med $\Omega$ .

$\displaystyle \sum_{k=1}^{n-1} k = \dfrac{n(n-1)}{2} = \Theta(n^2)$ Trekanttall, og antall forskyvninger i verste tilfelle for Insertion-Sort

$\displaystyle \sum_{i=0}^{h-1} 2^i = 2^h - 1$ Toerpotens-summen: $1 + 2 + 4 + \cdots + n/2 = n - 1$ når $n = 2^h$ . Det totale kopieringsarbeidet i tabelldobling.

$\displaystyle a^{\log_b n} = n^{\log_b a}$ Antall løvnoder i rekursjonstreet til $T(n) = aT(n/b) + f(n)$ , skrevet som en potens av $n$ . Ta logaritmen på begge sider: $\log_b n \cdot \log a = \log_b a \cdot \log n$ .
$\displaystyle T(n) = T(n/2) + 1 = \lg n + 1 = \Theta(\lg n)$ Binærsøk: ett kall på halve instansen pluss konstant arbeid. Argumentet halveres per ekspansjon, så det trengs $\lg n$ ekspansjoner.
$\displaystyle T(n) = 2T(n/2) + n = n \lg n + n = \Theta(n \lg n)$ Merge-Sort: rekursjonstreet har $\lg n + 1$ nivåer som hvert koster $n$ .
$\displaystyle T(n) = T(n-1) + n = \dfrac{n(n+1)}{2} = \Theta(n^2)$ Quicksort i verste tilfelle: pivoten står alene på hvert nivå, og nivåkostnadene $n, n-1, \ldots, 1$ summerer til trekanttallet.
$\displaystyle T(n) = aT(n/b) + f(n) \implies T(n) = \begin{cases} \Theta(n^{\log_b a}) & f(n) = O(n^{\log_b a - \epsilon}) \\ \Theta(n^{\log_b a} \lg^{k+1} n) & f(n) = \Theta(n^{\log_b a} \lg^{k} n),\ k \ge 0 \\ \Theta(f(n)) & f(n) = \Omega(n^{\log_b a + \epsilon}) \end{cases}$ Masterteoremet. Sammenlign $f(n)$ med vannskillefunksjonen $n^{\log_b a}$ ; avstanden må være en faktor $n^\epsilon$ i tilfelle 1 og 3, og tilfelle 3 krever i tillegg $a f(n/b) \le c f(n)$ for en $c < 1$ .

$\displaystyle n! > (n/e)^n \implies \lg n! > n \lg n - n \lg e = \Omega(n \lg n)$ Sorteringsgrensen. Et beslutningstre med $n!$ løvnoder har høyde minst $\lg n!$ , og Stirlings formel gir $n! > (n/e)^n$ . Enhver sammenligningsbasert sortering bruker $\Omega(n \lg n)$ sammenligninger i verste tilfelle.
$\displaystyle T(n) = T(n/2) + n = 2n - 1 = \Theta(n)$ Randomized-Select når pivoten deler på midten: ett kall på halve instansen pluss lineært arbeid, en geometrisk sum $n + n/2 + \cdots + 1$ . Forventet kjøretid er $\Theta(n)$ for enhver input; verste tilfelle er $\Theta(n^2)$ .
$\displaystyle T(n) \le T(n/5) + T(7n/10) + \Theta(n) = \Theta(n)$ Select. Medianen av gruppemedianene garanterer at minst $3n/10$ elementer ligger på hver side av pivoten, så det rekursive kallet får høyst $7n/10$ . Kallene får til sammen $9n/10 < n$ , og rota dominerer.
$\displaystyle T(n) = \Theta(n + k)$ Counting-Sort på $n$ heltall i området $0 .. k$ : to løkker over $A$ og én over $C$ . Lineær når $k = O(n)$ .
$\displaystyle T(n) = \Theta(d(n + k))$ Radix-Sort: $d$ siffer, hvert med $k + 1$ mulige verdier, sortert stabilt ett siffer om gangen med Counting-Sort.

$\displaystyle \begin{aligned} \text{Left}(i) &= 2i \\ \text{Right}(i) &= 2i + 1 \\ \text{Parent}(i) &= \lfloor i/2 \rfloor \end{aligned}$ Haugen som tabell, nummerert nivå for nivå med rota som 1. Med indekser fra 0 blir barna $2i + 1$ og $2i + 2$ og forelderen $\lfloor (i - 1)/2 \rfloor$ .
$\displaystyle 2^h \le n \le 2^{h+1} - 1$ Antall elementer i en haug med høyde $h$ : nivåene over det nederste er fulle, og det nederste har fra 1 til $2^h$ noder. Altså er $h = \lfloor \lg n \rfloor$ .
$\displaystyle \sum_{k=0}^{\lfloor \lg n \rfloor} \left\lceil \dfrac{n}{2^{k+1}} \right\rceil O(k) = O(n)$ Build-Max-Heap. Høyst $\lceil n/2^{k+1} \rceil$ noder har høyde $k$ , og hver av dem synker høyst $k$ steg. Summen er $O(n \sum_{k \ge 0} k/2^k) = O(2n)$ , for $\sum_{k \ge 0} k x^k = x/(1-x)^2$ . Ikke det samme som $n$ innsettinger, som koster $\Theta(n \lg n)$ .
$\displaystyle \begin{aligned} T(n) &= \Theta(n) + (n - 1) \cdot O(\lg n) \\ &= O(n \lg n) \end{aligned}$ Heapsort: bygg haugen i lineær tid, og ta ut maksimum $n - 1$ ganger med Max-Heapify på $O(\lg n)$ hver. $\Theta(n \lg n)$ i verste tilfelle og $\Theta(n)$ i beste, når alle elementene er like.

$\displaystyle r_0 = 0 \allowbreak\quad r_n = \max_{1 \le i \le n} (p_i + r_{n-i})$ Stavkapping: prøv alle lengder $i$ på den første biten, og kapp resten optimalt. Med memoisering eller nedenfra og opp er det $\Theta(n^2)$ .
$\displaystyle T(n) = 1 + \sum_{j=0}^{n-1} T(j) = 2^n$ Antall kall Cut-Rod gjør uten lagring, rota medregnet. Trekk $T(n-1)$ fra $T(n)$ : da er $T(n) = 2T(n-1)$ , og $T(0) = 1$ .
$\displaystyle c[i, j] = \begin{cases} 0 & i = 0 \text{ eller } j = 0 \\ c[i-1, j-1] + 1 & i, j > 0 \text{ og } x_i = y_j \\ \max(c[i-1, j],\, c[i, j-1]) & i, j > 0 \text{ og } x_i \ne y_j \end{cases}$ Lengden av en LCS av prefiksene $X_i$ og $Y_j$ . Tabellen fylles rad for rad i $\Theta(mn)$ .
$\displaystyle K[i, j] = \begin{cases} 0 & i = 0 \\ K[i-1, j] & w_i > j \\ \max(K[i-1, j],\, K[i-1, j - w_i] + v_i) & w_i \le j \end{cases}$ Det binære ryggsekkproblemet med gjenstandene $1, \ldots, i$ og kapasitet $j$ . Tabellen har $(n+1)(W+1)$ celler, så kjøretiden er $\Theta(nW)$ .
$\displaystyle \Theta(nW) = \Theta(n 2^m) \allowbreak\quad m = \lfloor \lg W \rfloor + 1$ Kjøretiden for ryggsekkproblemet uttrykt ved antall bits $m$ i $W$ . Den er polynomisk i tallet $W$ , men eksponentiell i inputstørrelsen, altså pseudopolynomisk.

$\displaystyle B(T) = \sum_{c \in C} c.\mathit{freq} \cdot d_T(c)$ Kostnaden til kodetreet $T$ : antall bits i den kodede teksten. Dybden $d_T(c)$ er lengden av kodeordet til $c$ . For et huffmantre er det også summen av frekvensene i de indre nodene.
$\displaystyle B(T) = B(T') \allowbreak + x.\mathit{freq} + y.\mathit{freq}$ Optimal delstruktur for Huffman: $T'$ har det nye tegnet $z$ i stedet for $x$ og $y$ . Får $z$ barna $x$ og $y$ , blir kodeordene deres én bit lengre.

$\displaystyle \sum_{u \in V} |G.\mathit{Adj}[u]| = |E|$ Nabolistene i en rettet graf: kanten $(u, v)$ står bare i lista til $u$ . I en urettet graf står den i begge listene, og summen er $2|E|$ . Nabolistene tar $\Theta(V + E)$ plass, og en nabomatrise tar $\Theta(V^2)$ .
$\displaystyle \Theta(V) + \sum_{u \in V} \Theta(1 + |G.\mathit{Adj}[u]|) \allowbreak = \Theta(V + E)$ DFS: initialiseringen, og ett kall til DFS-Visit per node, som går gjennom nabolista én gang. BFS bruker $O(V + E)$ med samme argument. Topological-Sort og Strongly-Connected-Components bruker også $\Theta(V + E)$ .
$\displaystyle u.d < v.d < v.f < u.f$ Parentesteoremet: $v$ er en ekte etterkommer av $u$ i dybde-først-skogen hvis og bare hvis intervallet til $v$ ligger inni intervallet til $u$ . Ellers er intervallene disjunkte, eller $u$ er en etterkommer av $v$ .
$\displaystyle (u, v) \in E \;\Rightarrow\; v.f < u.f$ I en DAG går hver kant fra en node med høyere sluttid til en med lavere. Derfor gir synkende sluttid en topologisk sortering.
$\displaystyle v.d = \delta(s, v)$ Etter BFS fra $s$ er $v.d$ det minste antallet kanter på en sti fra $s$ til $v$ , og $\infty$ hvis $v$ ikke kan nås. Stien i bredde-først-treet fra $s$ til $v$ er en korteste vei.