Stały amortyzowany czas

Odpowiedzi:

776

Amortyzowany czas objaśniony prostymi słowami:

Jeśli wykonujesz operację, powiedz milion razy, tak naprawdę nie obchodzi Cię najgorszy przypadek lub najlepszy przypadek tej operacji - liczy się to, ile czasu zajmie całkowite powtórzenie operacji milion razy .

Nie ma więc znaczenia, czy operacja jest bardzo powolna raz na jakiś czas, o ile „raz na jakiś czas” jest na tyle rzadkie, że powolność może zostać osłabiona. Zasadniczo amortyzowany czas oznacza „średni czas potrzebny na operację, jeśli wykonujesz wiele operacji”. Amortyzowany czas nie musi być stały; możesz mieć liniowo i logarytmicznie amortyzowany czas lub cokolwiek innego.

Weźmy przykład maty dynamicznej tablicy, do której wielokrotnie dodajesz nowe elementy. Zwykle dodanie elementu zajmuje stały czas (to znaczy O(1)). Ale za każdym razem, gdy tablica jest pełna, alokujesz dwa razy więcej miejsca, kopiujesz dane do nowego regionu i zwalniasz stare miejsce. Zakładając, że przydziały i zwolnienia przebiegają w stałym czasie, ten proces powiększania wymaga O(n)czasu, gdzie n jest bieżącym rozmiarem tablicy.

Za każdym razem, gdy powiększasz, zajmuje to około dwa razy więcej czasu niż ostatnie powiększenie. Ale czekałeś też dwa razy dłużej! Koszt każdego rozszerzenia można zatem „rozłożyć” na wstawki. Oznacza to, że w długim okresie całkowity czas potrzebny na dodanie m elementów do tablicy wynosi O(m), a więc i amortyzowany czas (tj. Czas na wprowadzenie) wynosi O(1).

Artelius
źródło
61
Tylko uwaga w zakresie zapisu: Zamortyzowany stały czas wykonania O (n) jest często zapisywany jako O (n) +, a nie tylko O ​​(n). Dodanie znaku plus wskazuje, że ten czas wykonania nie jest gwarantowany jako O (n) i może faktycznie przekroczyć ten czas wykonania.
Jeffpowrs,
1
Jeśli chodzi o przydzielanie miejsca, czy to z kupy?
zaangażowanieandroider
3
Nie zgadzam się z twierdzeniem, że „nie obchodzi cię najgorszy przypadek”. To zależy od przypadku użycia. Jeśli w końcu interesuje Cię tylko wynik 1 miliona operacji, to naprawdę cię to nie obchodzi. Ale jeśli jest to aplikacja czasu rzeczywistego, która stale odczytuje dane, a następnie na nie reaguje, możesz mieć duży problem, jeśli przetwarzanie tych danych zajmuje 1 milion razy dłużej niż zwykle raz na 1 milion przetworzonych danych!
Kai Petzke
2
@Jeffpowrs Myślałem, że O (n) to czas liniowy, a O (1) to czas stały . Czy to oznacza, że ​​O (1) + byłby zamortyzowany czas stały, a O (n) + byłby zamortyzowany czas liniowy ?
John Meyer,
1
@JohnMeyer Tak.
Artelius
55

Oznacza to, że z czasem najgorszym scenariuszem będzie domyślnie O (1) lub stały czas. Typowym przykładem jest tablica dynamiczna. Jeśli już przydzieliliśmy pamięć dla nowego wpisu, dodanie jej będzie O (1). Jeśli go nie przydzieliliśmy, zrobimy to, przydzielając powiedzmy dwa razy bieżącą kwotę. Tym konkretnym wstawieniem nie będzie O (1), ale coś innego.

Ważne jest to, że algorytm gwarantuje, że po sekwencji operacji drogie operacje zostaną zamortyzowane, a tym samym renderowanie całej operacji O (1).

Lub ściślej,

Istnieje stała c, taka, że ​​dla każdej sekwencji operacji (także jednej kończącej się kosztowną operacją) o długości L czas nie jest większy niż c * L (Dzięki Rafał Dowgird )

Mats Fredriksson
źródło
11
„po wystarczająco dużej liczbie operacji” - stały amortyzowany czas nie wymaga tego warunku. Istnieje stała c, taka, że ​​dla każdej sekwencji operacji (także jednej kończącej się kosztowną operacją) o długości L czas nie jest większy niż c * L.
Rafał Dowgird
Skąd ta alokacja podwójna kwota pochodzi? Czy nie powinniśmy przeznaczyć jednego wpisu? Czy jest to hipotetyczny przykład?
talekeDskobeDa
@talekeDskobaDa To nie jest arbitralny przykład, ale powszechnie stosowany algorytm. Jeśli przydzielimy miejsce dla jednego wpisu na raz, jak sugerujesz, zamortyzowany czas na wstawienie pojedynczej wartości wynosiłby O (n). Jeśli podwoimy przestrzeń, gdy się zapełni, czas zamortyzowany jest znacznie lepszy, O (1). Dla jasności problem z przydzielaniem miejsca dla jednego elementu na raz polega na tym, że tablica potrzebuje dużego bloku ciągłego miejsca. Łatwo jest uzyskać większy blok z systemu operacyjnego, ale często niemożliwe jest rozszerzenie istniejącego bloku, ponieważ mogą być przechowywane inne dane bezpośrednio po nim.
Artelius
23

Aby opracować intuicyjny sposób myślenia o tym, rozważ wstawienie elementów do tablicy dynamicznej (na przykład std::vectorw C ++). Narysujmy wykres, który pokazuje zależność liczby operacji (Y) potrzebnych do wstawienia N elementów w tablicy:

wątek

Pionowe części czarnego wykresu odpowiadają realokacji pamięci w celu rozszerzenia tablicy. Widzimy tutaj, że tę zależność można z grubsza przedstawić w postaci linii. A to równanie liniowe jest Y=C*N + b( Cjest stałe, bw naszym przypadku = 0). Dlatego możemy powiedzieć, że musimy wydać C*Nśrednio operacje na dodanie N elementów do tablicy lub C*1operacje na dodanie jednego elementu (zamortyzowany stały czas).

Megamozg
źródło
14

Uznałem, że poniższe wyjaśnienie Wikipedii jest użyteczne po trzykrotnym przeczytaniu:

Źródło: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

„Tablica dynamiczna

Amortyzowana analiza operacji wypychania dla tablicy dynamicznej

Rozważ dynamiczną tablicę, która powiększa się wraz z dodawaniem do niej większej liczby elementów, takich jak ArrayList w Javie. Gdybyśmy zaczęli od dynamicznej tablicy o rozmiarze 4, zajęłoby to cały czas, aby wcisnąć na nią cztery elementy. Jednak pchnięcie piątego elementu na tę tablicę zajęłoby więcej czasu, ponieważ tablica musiałaby utworzyć nową tablicę o podwójnym rozmiarze obecnego rozmiaru (8), skopiować stare elementy na nową tablicę, a następnie dodać nowy element. Kolejne trzy operacje push zajmowałyby podobnie stały czas, a następnie kolejne dodawanie wymagałoby kolejnego powolnego podwojenia wielkości tablicy.

Ogólnie biorąc, jeśli weźmiemy pod uwagę dowolną liczbę wypychań n do tablicy o rozmiarze n, zauważymy, że operacje wypychania wymagają stałego czasu, z wyjątkiem ostatniego, który zajmuje czas O (n) do wykonania operacji podwojenia wielkości. Ponieważ wykonano n operacji łącznie, możemy wziąć średnią z tego i przekonać się, że do wypychania elementów na tablicę dynamiczną potrzeba: O (n / n) = O (1), stały czas. ”

W moim rozumieniu jako prosta historia:

Załóżmy, że masz dużo pieniędzy. I chcesz je ułożyć w stos. I masz długie ręce i nogi, tyle ile potrzebujesz teraz lub w przyszłości. I musisz wypełnić wszystko w jednym pokoju, więc łatwo go zamknąć.

Idź prosto do końca / rogu pokoju i zacznij układać je w stosy. Gdy układasz je w stos, powoli w pokoju zabraknie miejsca. Jednak po wypełnieniu łatwo było je ułożyć w stos. Mam pieniądze, włóż pieniądze. Łatwy. To O (1). Nie musimy przenosić żadnych poprzednich pieniędzy.

Gdy w pokoju zabraknie miejsca. Potrzebujemy innego pokoju, który jest większy. Tutaj jest problem, ponieważ możemy mieć tylko 1 pokój, więc możemy mieć tylko 1 zamek, musimy przenieść wszystkie istniejące pieniądze z tego pokoju do nowego większego pokoju. Więc przenieś wszystkie pieniądze z małego pokoju do większego. Oznacza to, że ułóż je wszystkie ponownie. Tak więc, musimy przenieść wszystkie poprzednie pieniądze. Więc to jest O (N). (zakładając, że N jest całkowitą liczbą pieniędzy z poprzednich pieniędzy)

Innymi słowy, było łatwo do N, tylko 1 operacja, ale kiedy musimy przenieść się do większego pokoju, wykonaliśmy N. operacji. Innymi słowy, jeśli uśrednimy, to jest 1 wkładka na początku i 1 dodatkowy ruch podczas przeprowadzki do innego pokoju. Łącznie 2 operacje, jedna wkładka, jeden ruch.

Zakładając, że N jest duży jak 1 milion, nawet w małym pomieszczeniu, 2 operacje w porównaniu z N (1 milion) nie są tak naprawdę porównywalną liczbą, więc uważa się je za stałe lub O (1).

Zakładając, że wykonamy wszystkie powyższe czynności w innym większym pokoju i znów musimy się przenieść. To jest wciąż to samo. powiedzmy, N2 (powiedzmy 1 miliard) to nowa ilość pieniędzy w większym pokoju

Mamy więc N2 (który obejmuje N poprzedniego, ponieważ przenosimy wszystkie z małego do większego pokoju)

Nadal potrzebujemy tylko 2 operacji, jedna jest włożona do większego pokoju, a następnie kolejna operacja przeniesienia, aby przenieść się do jeszcze większego pomieszczenia.

Tak więc, nawet dla N2 (1 miliard), są to 2 operacje dla każdego. co znowu jest niczym. Jest więc stały lub O (1)

Tak więc, gdy N wzrasta z N do N2, lub innych, nie ma to większego znaczenia. Nadal jest stały lub operacje O (1) są wymagane dla każdego z N.


Załóżmy teraz, że masz N jako 1, bardzo mały, liczba pieniędzy jest niewielka, i masz bardzo mały pokój, który zmieści tylko 1 liczbę pieniędzy.

Gdy tylko wypełnisz pieniądze w pokoju, pokój jest pełny.

Kiedy idziesz do większego pokoju, załóż, że zmieści się w nim tylko jedno dodatkowe pieniądze, łącznie 2 liczby pieniędzy. Oznacza to, że poprzedni przeniósł pieniądze i jeszcze 1. I znowu jest wypełniony.

W ten sposób N rośnie powoli i nie jest już stałym O (1), ponieważ przenosimy wszystkie pieniądze z poprzedniego pokoju, ale możemy zmieścić tylko 1 dodatkowy pieniądze.

Po 100-krotności nowy pokój zmieści 100 pieniędzy z poprzedniego i 1 więcej pieniędzy, które może pomieścić. To jest O (N), ponieważ O (N + 1) to O (N), to znaczy stopień 100 lub 101 jest taki sam, oba są setkami, w przeciwieństwie do poprzedniej historii, od milionów do miliardów, a do miliardów .

Jest to więc nieefektywny sposób przydzielania pokoi (lub pamięci / pamięci RAM) na nasze pieniądze (zmienne).


Tak więc dobrym sposobem jest przydzielenie większej ilości miejsca z potęgami 2.

Rozmiar pierwszego pokoju = pasuje na 1 liczbę pieniędzy
Rozmiar drugiego pokoju = mieści 4 liczbę pieniędzy
3 rozmiar pokoju = pasuje 8 ilość pieniędzy
Rozmiar 4 pokoju = pasuje 16 ilość pieniędzy
5 rozmiar pokoju = pasuje 32 ilość pieniędzy
6 rozmiar pokoju = pasuje 64 ilość pieniędzy
7. wielkość pokoju = mieści 128 ilość pieniędzy
8. wielkość pokoju = pasuje 256 ilość pieniędzy
9. wielkość pokoju = pasuje 512 ilość pieniędzy
10. wielkość pokoju = pasuje 1024 ilość pieniędzy
11. wielkość pokoju = pasuje 2.048 ilość pieniędzy
. ..
16. rozmiar pokoju = pasuje do 65 536 liczby pieniędzy
...
32 rozmiar pokoju = pasuje do 4 294 967 296 liczby pieniędzy
...
64 rozmiar pokoju = pasuje do 18 446,744,073,709,551,616 liczby pieniędzy

Dlaczego to jest lepsze? Ponieważ na początku wygląda on powoli, a później szybciej, to znaczy w porównaniu do ilości pamięci w naszej pamięci RAM.

Jest to pomocne, ponieważ w pierwszym przypadku, chociaż jest to dobre, łączna ilość pracy do wykonania na pieniądze jest stała (2) i nieporównywalna z wielkością pokoju (N), pomieszczenie, które wzięliśmy na początkowych etapach, może być zbyt duży (1 milion), który może nie być w pełni wykorzystany, w zależności od tego, czy w pierwszym przypadku możemy uzyskać tyle pieniędzy, aby w ogóle zaoszczędzić.

Jednak w ostatnim przypadku, moc 2, rośnie w granicach naszej pamięci RAM. I tak, zwiększając moc 2, zarówno analiza Zmotoryzowana pozostaje stała i jest przyjazna dla ograniczonej pamięci RAM, którą mamy dzisiaj.

Manohar Reddy Poreddy
źródło
2
Ach, więc to O (najgorszy przypadek / liczba operacji). Najbardziej podoba mi się ta odpowiedź.
nukleartyd
1

Powyższe objaśnienia dotyczą analizy agregatów, która polega na przyjęciu „średniej” z wielu operacji. Nie jestem pewien, w jaki sposób odnoszą się one do metody Bankersa lub fizykalnej metody amortyzacji.

Teraz. Nie jestem do końca pewny poprawnej odpowiedzi. Miałoby to jednak związek z podstawowym warunkiem obu metod fizyków + bankiera:

(Suma zamortyzowanego kosztu operacji)> = (Suma rzeczywistego kosztu operacji).

Główna trudność, z jaką się spotykam, polega na tym, że biorąc pod uwagę fakt, że zamortyzowane koszty asymptotyczne operacji różnią się od kosztów normalnie asymptotycznych, nie jestem pewien, jak ocenić znaczenie kosztów zamortyzowanych.

Wtedy ktoś podaje mój zamortyzowany koszt, wiem, że to nie to samo, co normalny koszt asymptotyczny. Jakie zatem wnioski wyciągnę z zamortyzowanego kosztu?

Ponieważ mamy do czynienia z nadmiernym obciążeniem niektórych operacji, podczas gdy inne są zaniżone, jedną hipotezą może być to, że cytowanie zamortyzowanych kosztów poszczególnych operacji byłoby bez znaczenia.

Na przykład: w przypadku stosu fibonacciego wycenę zamortyzowanego kosztu samego Klucza Zmniejszającego na O (1) jest bez znaczenia, ponieważ koszty są redukowane przez „pracę wykonaną przez wcześniejsze operacje zwiększania potencjału stosu”.

LUB

Moglibyśmy przyjąć następującą hipotezę uzasadniającą koszty zamortyzowane:

  1. Wiem, że kosztowna operacja będzie poprzedzona operacjami WIELU NISKICH KOSZTÓW.

  2. Dla celów analizy zamierzam przeciążyć niektóre tanie operacje, TAKIE, ŻE ICH KOSZT ASYMPTOTYCZNY NIE ZMIENIA SIĘ.

  3. Dzięki tym zwiększonym kosztom operacji mogę udowodnić, że kosztowna operacja ma MNIEJSZY KOSZT ASYMPTOTYCZNY.

  4. W ten sposób poprawiłem / zmniejszyłem ASYMPTOTIC-BOUND kosztu n operacji.

Zatem analiza zamortyzowanego kosztu + limity zamortyzowanego kosztu mają teraz zastosowanie tylko do kosztownych operacji. Tanie operacje mają taki sam koszt asymptotyczny zamortyzowany jak ich normalny koszt asymptotyczny.

Misraji
źródło
Ciekawe myśli
Lonnie Best,
0

Wydajność dowolnej funkcji można uśrednić, dzieląc „całkowitą liczbę wywołań funkcji” przez „całkowity czas wszystkich wykonanych wywołań”. W ten sposób można uśrednić nawet funkcje, które trwają coraz dłużej dla każdego wykonywanego połączenia.

Zatem istotą funkcji, która wykonuje, Constant Amortized Timejest to, że ten „średni czas” osiąga pułap, którego nie można przekroczyć w miarę zwiększania liczby połączeń. Każde połączenie może różnić się wydajnością, ale w dłuższej perspektywie ten średni czas nie będzie coraz większy.

Jest to podstawowa zaleta czegoś, co działa Constant Amortized Time.

Lonnie Best
źródło