Dynamické arrayEdit
Zvážit dynamické pole, které roste ve velikosti jako další prvky jsou přidány, například ArrayList v Java nebo std::vector v C++. Pokud bychom začali s dynamickým polem velikosti 4, mohli bychom na něj tlačit 4 prvky a každá operace by trvala konstantní čas. Ještě tlačí pátý element na pole by trvat déle, pole by vytvořit nové pole na dvojnásobek aktuální velikosti (8), kopii staré prvky do nového pole, a pak přidat nový prvek. Další tři operace push by podobně trvaly konstantní čas a následné přidání by vyžadovalo další pomalé zdvojnásobení velikosti pole.
obecně, pokud vezmeme v úvahu libovolný počet tlačí n + 1 pole o velikosti n, můžeme všimnout, že push operace trvat konstantní čas až na ten poslední, který trvá Θ ( n ) pro {\displaystyle \Theta (n)}
čas provést velikosti zdvojnásobení provozu. Vzhledem k tomu, že byly operace N + 1 Celkem, můžeme vzít průměr tohoto a zjistit, že tlačení prvků do dynamického pole trvá: n Θ ( 1 ) + Θ ( n ) n + 1 = Θ ( 1 ) {\displaystyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}
, konstantním čase.
QueueEdit
Zobrazí se Ruby provádění Fronta, FIFO, struktura dat:
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
operace enqueue jen posouvá prvek na vstupní pole; tato operace nezávisí na délce buď vstupní nebo výstupní, a proto běží v konstantním čase.
nicméně operace dequeue je složitější. Pokud výstupní pole již má některé prvky v něm, pak dequeue běží v konstantním čase; jinak, dequeue trvá O ( n ) {\displaystyle O(n)}
čas přidat všechny prvky na výstupní pole ze vstupního pole, kde n je aktuální délka vstupního pole. Po zkopírování n prvků ze vstupu můžeme provádět n dequeue operace, z nichž každá trvá konstantní čas, než je výstupní pole opět prázdné. Můžeme tedy provést posloupnost n dequeue operace v O ( n ) {\displaystyle O(n)}
čas, což znamená, že odepisován čas každého dequeue operace je O ( 1 ) {\displaystyle O(1)}
