| Vector dinámico (C) | Listas | |
|---|---|---|
| Create | O(n) | O(n) |
| Destroy | O(1) | O(n) |
| Get | O(1) | O(n) |
| Set_at | O(1) | O(n) |
| insert_first | O(n) | O(1) |
| insert_last | O(n) | O(1) |
cost_insert(n) =
{ n, cuando log 2 (n) es entero
{ 2 en otro caso
N = CANTIDAD DE INSERCIONES
Siempre que el logaritmo en base dos de n es entero, copio mi vector y lo pego en otro lugar de la memoria porque no voy a poder seguir escribiendo
Ejemplo:
[1] costo=2
[1][2] costo = 2 + 1 (n=1)
[1][2][3][ ] costo = 2 + 2 (n=2)
[1][2][3][4] costo=2 (n=3)
[1][2][3][4][5][ ][ ][ ] costo = 2 + 4 (n=4)
Costo amortizado =
n
Σ cost_insert(i)
i=1 ———————
N