Referanseside · Kapittel 4

Begreper & formler

Alle nøkkelbegrepene og formlene fra Del og hersk, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards8 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Del-og-hersk

Strategi for å dele et problem i mindre delproblemer, løse dem rekursivt og kombinere resultatene.

02Rekursjonstre

Et tre som viser hvordan et problem brytes ned i delproblemer for hver rekursjon.

03Substitusjonsmetoden

Teknikk for å gjette løsningen på en rekurrens og bevise den ved induksjon.

04Masterteoremet

Formel som gir asymptotisk løsning for rekurrenser av typen $T (n) = a T (n / b) + f (n)$ .

05Strassen-algoritmen

Raskere metode for matrisemultiplikasjon enn standard $O (n^{3})$ ved å redusere antall multiplikasjoner.

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

T (n) = a T (\frac{n}{b}) + f (n)

T (n) = ⎩ ⎨ ⎧ Θ (n^{l o g_{b} a}) Θ (n^{l o g_{b} a} lo g n) Θ (f (n)) hvis f (n) = O (n^{l o g_{b} a - ε}) hvis f (n) = Θ (n^{l o g_{b} a}) hvis f (n) = Ω (n^{l o g_{b} a + ε}) og regularitet gjelder

T (n) = 7 T (\frac{n}{2}) + Θ (n^{2})