Array vs Dynamic Array

Naviga le tue risposte
3

In Manuale di progettazione dell'algoritmo di Edition 2 di Steven Skiena, parla di array dinamici su pagina 67 , che li porta ad avere lo stesso Big-Oh degli array normali. Non capisco come. Questo è ciò che afferma il libro

Half the elements [in final array] were moved once, a quarter twice, and so on, so total movements M is given by

Nonstacontandoalcunimovimentiduevolte?

(La parte rossa viene copiata dall'ultimo array e blu è la nuova parte inserita)

Per gli inserimenti n ci sono lg n reallocations di array. Quindi 1 ° elemento viene copiato lg n volte, il secondo lg n - 1 volte, il prossimo 2 lg n - 2 volte, il prossimo 4 lg n - 3 volte e così via.

Nonsocomerisolverequestoproblema,macosastopensandomale?

Eccoilmiocodiceinlattice,sequalcunovuolemodificarlo qui 

M = 1 \cdot lg_2 n + 1 \cdot (lg_2 n - 1) + 2 \cdot (lg_2 n - 2) + 4 \cdot (lg_2 n - 3)  
= \sum_{i = 1}^{lg_2 n - 1} 2^i \cdot (lg_2 n - i)
    
posta Sourabh 14.02.2017 - 20:42
fonte

2 risposte

2

Immaginiamo di inserire i primi sedici numeri naturali: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

La sequenza va così: 

1 
1 2
1 2 3 4
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
  • I numeri 9-16 vengono copiati una volta.
  • I numeri 5-8 sono copie due volte.
  • I numeri 3-4 sono copie tre volte.
  • Il numero 2 è copie quattro volte.
  • Il numero 1 è copie cinque volte.

Isn't this counting some movements twice?

No, la metà e il quarto nella citazione sono distinti i valori. Il trimestre non fa parte della metà.

    
risposta data 15.02.2017 - 02:03
fonte
2

Gli array dinamici non riallocano le loro dimensioni ogni volta che fai un inserimento.

Piuttosto, un inserimento che richiede che la dimensione della matrice aumenti causerà in genere la dimensione della matrice . Il costo di espansione risultante è ammortizzato su tutti gli inserimenti, che significa che il costo viene impiegato una volta su un numero di inserimenti geometricamente crescente e non ripreso per gli inserimenti originali.

Ulteriori letture
Espansione geometrica e costo ammortizzato

    
risposta data 14.02.2017 - 20:53
fonte

Leggi altre domande sui tag

Devo nidificare repository come bambole russe? Se non è richiesto #include aggiuntivo, "questo metodo non deve essere modificato" una buona ragione per definire un metodo in .h?