Referanseside · Kapittel 3

Begreper & formler

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

Øv med flashcards9 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Asymptotisk notasjon

Matematisk måte å beskrive vekst for funksjoner når $n$ går mot uendelig.

Logg inn for forklaring

02Big-O-notasjon

$O (g (n))$ er mengden av funksjoner som vokser maksimalt like raskt som $g (n)$ .

Logg inn for forklaring

03Omega-notasjon

$Ω (g (n))$ er mengden av funksjoner som vokser minst like raskt som $g (n)$ .

Logg inn for forklaring

04Theta-notasjon

$Θ (g (n))$ beskriver funksjoner som vokser proporsjonalt med $g (n)$ .

Logg inn for forklaring

05Dominant ledd

Det leddet i et uttrykk som bestemmer veksten for store $n$ .

Logg inn for forklaring

Formler

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

f (n) = O (g (n)) hvis det finnes c, n_{0} > 0 slik at f (n) \leq c g (n) for alle n > n_{0}

Definisjon av $O$-notasjon

Logg inn for forklaring

f (n) = Ω (g (n)) hvis f (n) \geq c g (n) for store n

Definisjon av $\Omega$-notasjon

Logg inn for forklaring

f (n) = Θ (g (n)) hvis f (n) = O (g (n)) og f (n) = Ω (g (n))

Definisjon av $\Theta$-notasjon

Logg inn for forklaring

lo g_{a} n = \frac{lo g _{b} n}{lo g _{b} a}

Logaritmiske og polynomielle funksjoner

Logg inn for forklaring

Tilbake til kapittelet

CMD + K

CMD + K

Begreper & formler

Begreper

Formler

Definisjon av $O$-notasjon

Definisjon av $\Omega$-notasjon

Definisjon av $\Theta$-notasjon

Logaritmiske og polynomielle funksjoner