Algorytmy i struktury danych · Senior · Pytanie 28 z 75
Czym jest analiza zamortyzowana metodą „księgowania” lub „potencjału”?
- 1Wielokrotnym mierzeniem czasu operacji i uśrednianiem
- ✓Poprawna odpowiedź: Tanie operacje płacą z góry za rzadkie drogie
- 3Uśrednianiem czasu działania po losowych danych
Wyjaśnienie
Daje oszacowanie najgorszego przypadku dla ciągu operacji, bez żadnego prawdopodobieństwa. Każdy push do tablicy dynamicznej „odkłada” stałą, która później płaci za kopiowanie przy powiększeniu. Uśrednianie po losowych danych to analiza przypadku średniego, coś innego.