Referanseside · Kapittel 17

Begreper & formler

Alle nøkkelbegrepene og formlene fra Amortisert analyse, 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.

01Amortisert kostnad

Gjennomsnittlig kostnad per operasjon i en sekvens av operasjoner.

02Aggregate method

Summér total kostnad og del på antall operasjoner.

03Accounting method

Tildel fiktive kostnader til operasjoner slik at summen dekker faktiske kostnader.

04Potential method

Definer en potensiell energi $Φ$ som øker og minker med strukturelle endringer.

05Eksempel: dynamiske arrayer

Når kapasiteten dobles, får man amortisert $O (1)$ for innsetting.

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

\overset{c}{^}_{i} = c_{i} + Φ (D_{i}) - Φ (D_{i - 1})

i \sum \overset{c}{^}_{i} = i \sum c_{i} + Φ (D_{n}) - Φ (D_{0})