Qual è la complessità asintotica di List.Add?

Question

Ho scoperto che ci sono molte controversie sulla complessità asintotica di List.Add(). Sospetto che sia la causa peggiore dello scenario that causes underlying array to resize e logicamente sarebbe l'operazione O(n). Tuttavia, lo array grows twice in size ogni elenco di tempo esaurisce lo spazio. Ciò rende la proporzione necessaria per gli elementi n proporzionale a log(n).

Ciò non significa che la complessità asintotica dell'operazione Add nel caso medio sarà O(n/log(n))?

Il vero parametro di riferimento per List.Add() è il seguente. Tuttavia, i benchmark non sono realmente espressivi per tale operazione - potremmo essere a corto di memoria prima che qualsiasi deviazione dalla linea retta (in scala logaritmica) diventi visibile.

Answer 1

Ciò significa che la amortized complexity di List.Add() può essere calcolato sommando le operazioni di ridimensionamento e quindi moltiplicando per numero totale aggiunte apportate all'elenco.

T(n) = (2 + 4 + 8 + ... + n/2 + n)/n 

ma nota che la somma è un geometric series, e possiamo fare meglio di supponendo che è (sommatoria) n*log(n):

T(n) < 2n/n = 2 -> T(n) is in O(1) 

---

Nota: Qui io parto dal presupposto che dire add() come aggiungendo . L'inserimento di un elemento in una posizione arbitraria richiede tempo O(n) e sarà necessario tenere conto anche di quello, che modificherà il risultato finale dalla complessità ammortizzata O(1) alla complessità ammortizzata O(n).