Dynamic arrayEdit
rozważmy dynamiczną tablicę, która rośnie w rozmiarze ponieważ dodawane są do niego kolejne elementy, takie jak ArrayList w Javie lub std::vector w C++. Gdybyśmy zaczęli od dynamicznej tablicy wielkości 4, moglibyśmy na nią wcisnąć 4 elementy, a każda operacja zajęłaby stały czas. Jednak wciśnięcie piątego elementu na tę tablicę zajęłoby więcej czasu, ponieważ tablica musiałaby utworzyć nową tablicę o podwójnym rozmiarze (8), skopiować stare elementy do nowej tablicy, a następnie dodać nowy element. Kolejne trzy operacje push zajęłyby podobnie stały czas, a kolejne dodanie wymagałoby kolejnego powolnego podwojenia rozmiaru tablicy.
ogólnie, jeśli weźmiemy pod uwagę dowolną liczbę push n + 1 do tablicy o rozmiarze n, zauważymy, że operacje push zajmują stały czas, z wyjątkiem ostatniej, która zajmuje Θ ( n ) {\displaystyle \Theta (n)}
czas na wykonanie operacji podwojenia rozmiaru. Ponieważ było n + 1 operacji razem możemy wziąć średnią z tego i stwierdzić, że pchanie elementów na tablicę dynamiczną trwa: n Θ ( 1 ) + Θ ( N ) n + 1 = Θ ( 1 ) {\displaystyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}
, czas stały.
QueueEdit
pokazana jest implementacja kolejki w języku Ruby, struktura 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 endend
operacja enqueue po prostu przesuwa element na tablicę wejściową; operacja ta nie zależy od długości wejścia ani wyjścia i dlatego działa w stałym czasie.
jednak operacja dequeue jest bardziej skomplikowana. Jeśli macierz wyjściowa zawiera już pewne elementy, to dequeue działa w stałym czasie; w przeciwnym razie, dequeue przyjmuje O (n) {\displaystyle O(n)}
Czas dodania wszystkich elementów do macierzy 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 dequeue, z których każda zajmuje stały czas, zanim wyjściowa tablica będzie ponownie pusta. W ten sposób możemy wykonać sekwencję N operacji dequeue tylko w O ( n ) {\displaystyle O(N)}
czasie, co oznacza, że zamortyzowanym czasem każdej operacji dequeue jest O ( 1 ) {\displaystyle O(1)}
