dinamikus arrayEdit
tekintsünk egy dinamikus tömb méretét növelő dinamikus tömböt mivel több elemet adunk hozzá, mint példáulArrayListJava vagy STD::Vector C++. Ha egy 4-es méretű dinamikus tömbbel kezdenénk, 4 elemet nyomhatnánk rá, és minden művelet állandó időt vesz igénybe. Ennek ellenére az ötödik elem ráhelyezése erre a tömbre hosszabb időt vesz igénybe, mivel a tömbnek létre kell hoznia egy új tömböt, amely kétszerese az aktuális méretnek (8), át kell másolnia a régi elemeket az új tömbre, majd hozzá kell adnia az új elemet. A következő három push művelet hasonlóan állandó időt vesz igénybe, majd az azt követő hozzáadáshoz a tömb méretének újabb lassú megduplázására lenne szükség.
általában, ha tetszőleges számú N + 1 lökést veszünk figyelembe egy n méretű tömbbe, akkor azt vesszük észre, hogy a push műveletek állandó időt vesznek igénybe, kivéve az utolsót, amely a méret duplázási művelet végrehajtásához szükséges ( n ) {\displaystyle \Theta (n)}
időt vesz igénybe. Mivel összesen n + 1 művelet volt, ennek átlagát figyelembe véve megállapíthatjuk, hogy az elemek dinamikus tömbre tolása: N (1) + (N ) N + 1 = (1 ) {\displaystyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}
, állandó idő.
QueueEdit
látható egy sor Ruby implementációja, egy FIFO adatstruktúra:
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
az enqueue művelet csak egy elemet tol a bemeneti tömbbe; ez a művelet nem függ sem a bemenet, sem a kimenet hosszától, ezért állandó időben fut.
a dequeue művelet azonban bonyolultabb. Ha a kimeneti tömb már tartalmaz néhány elemet, akkor a dequeue állandó időben fut; ellenkező esetben a dequeue o ( n ) {\displaystyle O(n)}
időt vesz igénybe, hogy az összes elemet hozzáadja a bemeneti tömb kimeneti tömbjéhez, ahol n A bemeneti tömb aktuális hossza. Miután n elemet másoltunk a bemenetről, n dequeue műveletet hajthatunk végre, mindegyik állandó időt vesz igénybe, mielőtt a kimeneti tömb ismét üres lenne. Így n dequeue műveletek sorozatát csak O ( n ) {\displaystyle O(n)}
időben hajthatjuk végre, ami azt jelenti, hogy az egyes dequeue műveletek amortizált ideje O ( 1 ) {\displaystyle O(1)}
