Analiza amortyzowana - Amortized analysis

„Amortyzowane” przekierowuje tutaj. W przypadku innych zastosowań zobacz Amortyzacja .

W informatyce , koszt zamortyzowany jest metodą analizy danego algorytmu złożoność , czyli jak dużo zasobów, zwłaszcza czasu lub pamięci, to ma do wykonania . Motywacją do analizy amortyzowanej jest to, że patrzenie na najgorszy czas działania może być zbyt pesymistyczne. Zamiast tego analiza amortyzowana uśrednia czasy wykonywania operacji w sekwencji w tej sekwencji. Podsumowując: „Analiza amortyzowana jest użytecznym narzędziem, które uzupełnia inne techniki, takie jak analiza najgorszego przypadku i analiza przeciętnego przypadku ”.

Dla danej operacji algorytmu pewne sytuacje, np. parametryzacje wejściowe czy zawartość struktury danych, mogą wiązać się ze znacznym kosztem zasobów, podczas gdy inne sytuacje mogą być mniej kosztowne. Amortyzowana analiza uwzględnia zarówno kosztowne, jak i mniej kosztowne operacje łącznie w całej sekwencji operacji. Może to obejmować uwzględnienie różnych rodzajów danych wejściowych, długości danych wejściowych i innych czynników, które wpływają na jego wydajność.

Historia

Analiza amortyzowana początkowo wyłoniła się z metody zwanej analizą zagregowaną, która jest obecnie podłączona do analizy amortyzowanej. Technika ta została po raz pierwszy formalnie wprowadzona przez Roberta Tarjana w jego pracy z 1985 r. Amortized Computational Complexity , która odnosiła się do potrzeby bardziej użytecznej formy analizy niż powszechnie stosowane metody probabilistyczne. Amortyzację początkowo stosowano dla bardzo specyficznych typów algorytmów, szczególnie tych obejmujących drzewa binarne i operacje sumujące . Jednak obecnie jest wszechobecny i wchodzi w grę również podczas analizy wielu innych algorytmów.

metoda

Główne artykuły: metoda rachunkowości i metoda potencjalna

Analiza amortyzowana wymaga wiedzy o tym, jakie serie operacji są możliwe. Najczęściej dzieje się tak w przypadku struktur danych , których stan utrzymuje się między operacjami. Podstawową ideą jest to, że najgorsza operacja może zmienić stan w taki sposób, że najgorszy przypadek nie może się powtórzyć przez długi czas, tym samym „amortyzując” jego koszt.

Zasadniczo istnieją trzy metody przeprowadzania analizy zamortyzowanej: metoda zagregowana, metoda księgowa i metoda potencjalna . Wszystkie te dają poprawne odpowiedzi; wybór, którego użyć, zależy od tego, który jest najwygodniejszy w danej sytuacji.

  • Analiza agregacyjna określa górną granicę T ( n ) całkowitego kosztu sekwencji n operacji, a następnie oblicza zamortyzowany koszt jako T ( n )/ n .
  • Metoda księgowa jest formą analizy zbiorczej, która przypisuje każdej operacji zamortyzowany koszt, który może różnić się od jej kosztu rzeczywistego. Wczesne operacje mają zamortyzowany koszt wyższy niż rzeczywisty koszt, co powoduje gromadzenie zaoszczędzonego „kredytu”, który płaci za późniejsze operacje, których zamortyzowany koszt jest niższy niż rzeczywisty koszt. Ponieważ kredyt zaczyna się od zera, rzeczywisty koszt sekwencji operacji jest równy zamortyzowanemu kosztowi minus skumulowany kredyt. Ponieważ kredyt musi być nieujemny, zamortyzowany koszt jest górną granicą rzeczywistego kosztu. Zwykle wiele krótkoterminowych operacji gromadzi taki kredyt w małych przyrostach, podczas gdy rzadkie operacje długoterminowe drastycznie go zmniejszają.
  • Metoda potencjalna jest formą metody księgowania, w której zapisany kredyt jest obliczany jako funkcja („potencjał”) stanu struktury danych. Koszt zamortyzowany to koszt natychmiastowy plus zmiana potencjału.

Przykłady

Tablica dynamiczna

Image
Amortyzowana analiza operacji push dla tablicy dynamicznej

Rozważmy tablicę dynamiczną, która rośnie wraz z dodawaniem do niej kolejnych elementów, na przykład ArrayListw Javie lub std::vectorC++. Gdybyśmy zaczęli z tablicą dynamiczną o rozmiarze 4, moglibyśmy wepchnąć na nią 4 elementy, a każda operacja zajęłaby stały czas . Jednak wypchnięcie piątego elementu do tej tablicy zajęłoby więcej czasu, ponieważ tablica musiałaby utworzyć nową tablicę o dwukrotnie większym rozmiarze bieżącego (8), skopiować stare elementy do nowej tablicy, a następnie dodać nowy element. Kolejne trzy operacje wypychania podobnie zajęłyby stały czas, a kolejne dodanie wymagałoby kolejnego powolnego podwojenia rozmiaru tablicy.

Ogólnie rzecz biorąc, jeśli weźmiemy pod uwagę dowolną liczbę wypchnięć n + 1 do tablicy o rozmiarze n , zauważymy, że operacje wypychania zajmują stały czas, z wyjątkiem ostatniego, który wymaga czasu na wykonanie operacji podwojenia rozmiaru. Ponieważ łącznie było n + 1 operacji, możemy wziąć średnią z tego i stwierdzić, że włożenie elementów do tablicy dynamicznej zajmuje: , stały czas.

Kolejka

Pokazana jest implementacja Rubiego Queue , struktury danych FIFO : 

class Queue
  def initialize
    @input = []
    @output = []
  end

  def enqueue(element)
    @input << element
  end

  def dequeue
    if @output.empty?
      while @input.any?
        @output << @input.pop
      end
    end

    @output.pop
  end
end

Operacja enqueue po prostu wypycha element do tablicy wejściowej; operacja ta nie zależy od długości wejścia lub wyjścia i dlatego działa w stałym czasie.

Jednak operacja usuwania z kolejki jest bardziej skomplikowana. Jeśli tablica wyjściowa zawiera już jakieś elementy, dequeue działa w stałym czasie; w przeciwnym razie dequeue zajmuje trochę czasu, aby dodać wszystkie elementy do tablicy wyjściowej z tablicy wejściowej, gdzie n jest bieżącą długością tablicy wejściowej. Po skopiowaniu n elementów z wejścia, możemy wykonać n operacji usuwania z kolejki, z których każda zajmuje stały czas, zanim tablica wyjściowa będzie ponownie pusta. W ten sposób możemy wykonać sekwencję n operacji usuwania z kolejki tylko w czasie, co oznacza, że ​​zamortyzowany czas każdej operacji usuwania z kolejki wynosi .

Alternatywnie możemy obciążyć koszt kopiowania dowolnego elementu z tablicy wejściowej do tablicy wyjściowej do wcześniejszej operacji wpisywania do kolejki dla tego elementu. Ten schemat opłat podwaja amortyzowany czas na kolejkowanie, ale zmniejsza amortyzowany czas na kolejkowanie do .

Powszechne zastosowanie

  • W powszechnym użyciu „algorytm amortyzowany” to taki, którego amortyzacja wykazała, że ​​działa dobrze.
  • Algorytmy internetowe powszechnie wykorzystują analizę amortyzowaną.

Bibliografia

Literatura