Nella notazione Big O, allocare un array di N elemento è definito da O (1) o O (n)? Ad esempio in C #, se alloco un array come questo:
int[] a = new int[10]
Quando visualizzo questo array, ho:
{0,0,0,0,0,0,0,0,0,0}
Normalmente, la dimensione di un array non ha alcun effetto sulla complessità dell'allocazione stessa. AFAIK, un array è internamente un puntatore a un indirizzo in cui inizia l'array e campi nascosti per la dimensione dell'elemento e il numero di elementi. Quindi sarebbe O(1) .
Almeno questo è il caso in Object Pascal, anche se non sono sicuro per C # o altre lingue.
Ma trovare il frammento di memoria adatto per il tuo array ha una complessità più alta che dipende dalla dimensione a un certo punto ma dipende più da come funziona il gestore di memoria attivo: Tempo temporale dell'assegnazione della memoria .
Leggi altre domande sui tag array big-o allocation