Symboler

01 Grunnlag

Symbol	Betydning
$n$	Problemstørrelsen, som regel antall elementer I stavkapping er $n$ lengden på staven, i LCS lengden av $Y$ og i ryggsekkproblemet antall gjenstander.
$T(n)$	Kjøretiden som funksjon av $n$ Står på begge sider i en rekurrens, som $T(n) = 2T(n/2) + n$ . For Cut-Rod er $T(n)$ antall kall.
$O(g(n))$	Øvre grense: vokser høyst så raskt som $g(n)$ Som $a \le b$ for tall. Kan brukes på hvilket som helst tilfelle, også det beste.
$\Omega(g(n))$	Nedre grense: vokser minst så raskt som $g(n)$ Som $a \ge b$ for tall.
$\Theta(g(n))$	Stram grense: vokser like raskt som $g(n)$ Som $a = b$ for tall. Både $O$ og $\Omega$ : $c_1\,g(n) \le f(n) \le c_2\,g(n)$ for $n \ge n_0$ .
$o(g(n))$	Øvre grense som ikke er stram: vokser strengt saktere enn $g(n)$ Som $a < b$ for tall. Ulikheten må holde for enhver $c > 0$ , så $f(n)/g(n)$ går mot null.
$\omega(g(n))$	Nedre grense som ikke er stram: vokser strengt raskere enn $g(n)$ Som $a > b$ for tall. $f(n)/g(n)$ vokser over alle grenser.
$f(n),\ g(n)$	Funksjonene som sammenlignes, som i $f(n) = O(g(n))$ I masterteoremet er $f(n)$ den drivende funksjonen.
$c,\ n_0$	Konstantene i definisjonene av grensene $f(n) = O(g(n))$ når $0 \le f(n) \le c\,g(n)$ for alle $n \ge n_0$ . Ikke tabellen $c[i, j]$ i LCS.
$\lg n$	Toerlogaritmen, $\log_2 n$ Andre grunntall skrives ut, som $\log_b n$ . $\lg^k n$ betyr $(\lg n)^k$ .
$\lfloor x \rfloor,\ \lceil x \rceil$	Tallet $x$ rundet ned og rundet opp til et heltall Rekurrenser skriver $n/2$ for $\lfloor n/2 \rfloor$ . Det endrer ikke den asymptotiske løsningen.
$\langle a_1, \ldots, a_n \rangle$	En sekvens, som instansen $\langle 6, 8, 3, 5 \rangle$ I beslutningstreet tester noden $i\!:\!j$ om $a_i \le a_j$ .
$A[i]$	Element nummer $i$ i tabellen $A$ Læreboka teller fra 1, Python fra 0. Hauger regnes fra 1 i teksten og fra 0 i koden.
$A[p .. r]$	Segmentet $A[p], \ldots, A[r]$ , begge ender med Læreboka og forelesningene skriver $A[p : r]$ for det samme. I Python er slutten ikke med, så segmentet er `A[p : r + 1]`.

02 Datastrukturer

Symbol	Betydning
$a + b(i - s)$	Adressen til element $i$ : startadresse $a$ , elementbredde $b$ og startindeks $s$ Ikke $a$ og $b$ i masterteoremet.
$k$	En nøkkel, i hashtabeller og søketrær Ikke eksponenten $k$ i masterteoremet eller den største verdien $k$ i Counting-Sort.
$h(k)$	Hashfunksjonen: plassen nøkkelen $k$ hører til, en av $0, \ldots, m - 1$ Den enkleste er $h(k) = k \bmod m$ . Ikke høyden $h$ i et tre.
$m$	Antall plasser i hashtabellen I LCS er $m$ lengden av $X$ , og for ryggsekken antall bits i $W$ .
$\alpha$	Belastningsfaktoren, $n/m$ Med kjeding og jevn fordeling tar et søk forventet $\Theta(1 + \alpha)$ .

03 Problemer og reduksjoner

Symbol	Betydning
$R \subseteq I \times O$	Et problem, som relasjonen mellom mengden inputs $I$ og mengden outputs $O$ $O$ er her en mengde, ikke $O$ -notasjonen, og $R$ er ikke hjelpetabellen i Merge-Sort.
$x,\ y$	En instans og en løsning: $(x, y) \in R$ når $y$ er et riktig svar på $x$ Et sertifikat er en påstått løsning $y$ som verifiseres.
$X,\ Y$	To problemer i en reduksjon: $X$ løses med et orakel for $Y$ Er reduksjonen billig, er $Y$ minst like vanskelig som $X$ . Ikke sekvensene $X$ og $Y$ i LCS.
$G,\ k$	Grafen og antall noder i klikken i CLIQUE En klikk er en komplett delgraf.

04 Splitt og hersk

Symbol	Betydning
$a$	Antall rekursive kall i $T(n) = aT(n/b) + f(n)$ Nivå $i$ i rekursjonstreet har $a^i$ noder av størrelse $n/b^i$ .
$b$	Faktoren instansen krymper med: hvert kall får $n/b$ Masterteoremet krever konstanter $a \ge 1$ og $b > 1$ , så $T(n - 1)$ er ikke på formen.
$f(n)$	Den drivende funksjonen, arbeidet med å dele og kombinere
$n^{\log_b a}$	Vannskillefunksjonen, antall løvnoder i rekursjonstreet Kjøretiden avgjøres av om $f(n)$ er polynomisk større, lik opp til en faktor $\lg^k n$ med $k \ge 0$ eller polynomisk mindre. Andre $f(n)$ dekkes ikke av masterteoremet.
$k$	Eksponenten til $\lg n$ i tilfelle 2 av masterteoremet, en konstant $k \ge 0$ Gir $\Theta(n^{\log_b a} \lg^{k+1} n)$ . I simuleringen av rekursjonstreet er eksponenten i $f(n) = n^d$ en annen størrelse, $d$ .
$\epsilon$	Avstanden i tilfelle 1 og 3: $f(n)$ skiller seg fra $n^{\log_b a}$ med en faktor $n^\epsilon$ En konstant $\epsilon > 0$ . Tilfelle 3 krever i tillegg $a f(n/b) \le c f(n)$ for en konstant $c < 1$ .
$x$	Pivoten, elementet segmentet deles rundt Partition bruker det siste elementet, $x = A[r]$ . I Select er $x$ medianen av gruppemedianene.
$q$	Plassen segmentet deles ved: midten, eller pivotens endelige plass etter Partition
$L,\ R$	Venstre og høyre halvdel, kopiert ut før flettingen i Merge-Sort Ikke relasjonen $R$ i et problem.
$\infty$	Vaktposten bakerst i $L$ og $R$ , så ingen av halvdelene går tom $-\infty$ markerer en delinstans som ikke er løst i memo-tabellen $r$ , og er nøkkelen et nytt element får i Max-Heap-Insert før den økes.

05 Rangering i lineær tid

Symbol	Betydning
$n!$	Antall rekkefølger av $n$ elementer, og dermed det minste antallet løvnoder i beslutningstreet Høyden, antall sammenligninger i verste tilfelle, er minst $\lg n! = \Omega(n \lg n)$ .
$i$	Rangen som søkes: det $i$ -ende minste elementet Rang 1 er minimum og rang $n$ maksimum. Medianen har rang $\lfloor (n+1)/2 \rfloor$ .
$k$	Rangen til pivoten i segmentet, $q - p + 1$ Er $i < k$ , søkes rang $i$ blant de små, ellers rang $i - k$ blant de store.
$k$	Den største verdien i Counting-Sort: inputen er heltall i $0 .. k$ I Radix-Sort har hvert siffer $k + 1$ mulige verdier, $k = 9$ for desimale siffer.
$C[v]$	Antall elementer lik $v$ , og etter den kumulative summen antall $\le v$ Den sorterte outputen legges i $B$ .
$d$	Antall siffer i Radix-Sort

06 Rotfaste trestrukturer

Symbol	Betydning
$h$	Høyden til et tre, den største dybden Operasjonene i et binært søketre koster $O(h)$ , og en haug har $h = \lfloor \lg n \rfloor$ . Ikke hashfunksjonen $h(k)$ .
$x,\ y,\ z$	Noder i et binært søketre Tree-Insert setter inn $z$ og lar $y$ gå ett steg bak $x$ , så $y$ blir forelderen.
$\text{Left}(i)$	Venstre barn til node $i$ i en haug, $2i$ Rota er $A[1]$ . Med indekser fra 0, som i Python, er rota $A[0]$ og venstre barn $2i + 1$ .
$\text{Right}(i)$	Høyre barn til node $i$ i en haug, $2i + 1$ Med indekser fra 0 er høyre barn $2i + 2$ .
$\text{Parent}(i)$	Forelderen til node $i$ i en haug, $\lfloor i/2 \rfloor$ Med indekser fra 0 er forelderen $\lfloor (i - 1)/2 \rfloor$ . Haugegenskapen er $A[\text{Parent}(i)] \ge A[i]$ .

07 Dynamisk programmering

Symbol	Betydning
$u \to v$	En kant i delinstansgrafen: svaret for $v$ bygger på svaret for $u$ Læreboka tegner kantene motsatt vei.
$p_i$	Prisen for en bit med lengde $i$ $p_1, \ldots, p_8 = 1, 5, 8, 9, 10, 17, 17, 20$ i eksemplene. I Python er `p[0]` en ubrukt plassholder.
$r_n$	Den største totalprisen for en stav med lengde $n$ Lagres i tabellen $r[0 .. n]$ . Ikke segmentgrensen $r$ i $A[p .. r]$ .
$s[j]$	Lengden på den første biten i en optimal kapping av lengde $j$ Kappingen leses av bakfra: skriv ut $s[n]$ , trekk den fra $n$ og gjenta.
$X,\ Y$	Sekvensene i LCS, $\langle x_1, \ldots, x_m \rangle$ og $\langle y_1, \ldots, y_n \rangle$ Ikke problemene $X$ og $Y$ i en reduksjon.
$X_i,\ Y_j$	Prefiksene $\langle x_1, \ldots, x_i \rangle$ og $\langle y_1, \ldots, y_j \rangle$ , delinstansene i LCS
$c[i, j]$	Lengden av en LCS av $X_i$ og $Y_j$ Ikke konstanten $c$ i asymptotisk notasjon.
$b[i, j]$	Pilen som viser hvilken celle $c[i, j]$ fikk verdien fra Print-LCS følger pilene bakfra fra $b[m, n]$ .
$v_i,\ w_i$	Verdien og vekten til gjenstand $i$
$W$	Kapasiteten til ryggsekken $\Theta(nW)$ er polynomisk i tallet $W$ , men ikke i antall bits.
$K[i, j]$	Den største verdien med gjenstandene $1, \ldots, i$ og kapasitet $j$ Tabellen har $(n + 1)(W + 1)$ celler.
$m$	Antall bits i $W$ , $\lfloor \lg W \rfloor + 1$ $\Theta(nW) = \Theta(n 2^m)$ , som er eksponentielt i $m$ .

08 Grådighet

Symbol	Betydning
$v_i / w_i$	Kiloprisen til gjenstand $i$ , verdi per vektenhet Den grådige algoritmen fyller sekken etter synkende kilopris.
$[s_i, f_i)$	Aktivitet $a_i$ : starttiden $s_i$ og sluttiden $f_i$ , et halvåpent intervall Aktivitetene er sortert etter $f_i$ . Den tenkte $a_0$ har $f_0 = 0$ . Ikke funksjonen $f(n)$ .
$k$	Indeksen til den sist valgte aktiviteten En ny aktivitet $a_m$ tas med når $s_m \ge f_k$ .
$C$	Alfabetet: tegnene som skal kodes Ikke tellertabellen $C$ i Counting-Sort.
$c.\mathit{freq}$	Frekvensen til tegnet $c$ : hvor mange ganger det står i teksten En indre node i et huffmantre har summen av frekvensene under seg.
$d_T(c)$	Dybden til løvnoden for $c$ i kodetreet $T$ , som er lengden av kodeordet
$B(T)$	Kostnaden til kodetreet $T$ : antall bits i den kodede teksten
$x,\ y,\ z$	I Huffman: de to trærne med lavest frekvens, og den nye noden som blir forelderen deres $z$ får frekvensen $x.\mathit{freq} + y.\mathit{freq}$ . Ikke nodene i et binært søketre.

09 Traversering av grafer

Symbol	Betydning
$G = (V, E)$	En graf med nodene $V$ og kantene $E$ Inne i asymptotisk notasjon står $V$ og $E$ for antall noder og kanter, som i $O(V + E)$ .
$G.\mathit{Adj}[u]$	Nabolista til $u$ : ut-naboene
$a_{uv}$	Elementet i rad $u$ , kolonne $v$ i nabomatrisen: 1 når $(u, v)$ er en kant, ellers 0
$s$	Startnoden i en traversering Ikke starttiden $s_i$ til en aktivitet.
$u.d$	I DFS: starttiden, da $u$ ble oppdaget og grå I BFS er $u.d$ avstanden fra startnoden.
$u.f$	I DFS: sluttiden, da $u$ ble ferdig og svart Ikke sluttiden $f_i$ til en aktivitet eller funksjonen $f(n)$ .
$u.d$	I BFS: avstanden fra startnoden $s$ til $u$ $\infty$ til $u$ er oppdaget.
$u.\pi$	Forgjengeren til $u$ : noden $u$ ble oppdaget fra nil for startnoden og for røttene i en dybde-først-skog.
$\delta(s, v)$	Avstanden fra $s$ til $v$ : det minste antallet kanter på en sti $\infty$ når $v$ ikke kan nås fra $s$ .
$G^{\mathrm T}$	Den transponerte grafen: $G$ med alle kantene snudd