Referanseside · Kapittel 39

Begreper & formler

Alle nøkkelbegrepene og formlene fra Appendiks D – Summasjoner og rekurrenser, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards7 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Rekursjon

Uttrykk som definerer en verdi basert på tidligere verdier, som $T (n) = 2 T (n /2) + n$ .

Logg inn for forklaring

02Iterativ substitusjon

Utvid rekursjonen trinn for trinn for å oppdage mønster.

Logg inn for forklaring

03Master-teoremet

Gir løsning for $T (n) = a T (n / b) + f (n)$ basert på sammenligning av $f (n)$ og $n^{l o g_{b} a}$ .

Logg inn for forklaring

04Karakteristisk ligning

Brukes for lineære rekursjoner med konstante koeffisienter.

Logg inn for forklaring

05Asymptotisk dominans

Når et ledd i rekursjonen vokser raskere enn resten.

Logg inn for forklaring

Formler

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

T (n) = a T (n / b) + f (n) \Rightarrow ⎩ ⎨ ⎧ O (n^{l o g_{b} a}) O (n^{l o g_{b} a} lo g n) O (f (n)) f (n) = O (n^{l o g_{b} a - ε}) f (n) = Θ (n^{l o g_{b} a}) f (n) = Ω (n^{l o g_{b} a + ε})

Master-teoremet

Logg inn for forklaring

T (n) = c_{1} T (n - 1) + c_{2} T (n - 2)

Lineær rekursjon

Logg inn for forklaring

Tilbake til kapittelet

CMD + K

CMD + K

Begreper & formler

Begreper

Formler

Master-teoremet

Lineær rekursjon