Amorterad tidskomplexitet
Hej! Jag stötte på frågan att uppge den "amorterade tidskomplexiteten" för att göra några operationer i ett program. Jag kan dock inte hitta vad det innebär, är det den totala?
Det här är första gången jag hör begreppet och att googla det begreppet på svenska gav mig bara ett fåtal föreläsningsanteckningar som inte innehöll någon definition.
Däremot så verkar det relatera till det engelska begreppet amortized analysis och att söka vidare på det begreppet kan nog vara hjälpsamt. Jag skriver det här inlägget innan jag har hunnit sätta mig in i det alltför mycket men slutsatsen är att det är något annat än total tidskomplexitet (värsta fallet?) och är någon slagt hybrid mellan värsta-fall-analys och medelkomplexitet.
Historiaavsnittet på wikiesidan hänvisar till en 1985-artikel som begynnande begreppet så det kan ju inte skada att läsa den också för en orientering.
Jag har själva frågan och svaret för den delen då det är från en gammal tenta, men jag förstår inte riktigt vad det är han säger i svaret heller. Det gäller funktionell programmering och du kanske kan kika om du förstår bättre än mig vad det är han gör för att få den amorterade tidskomplexiteten:
