Big O di array JavaScript

Gli array in JavaScript sono molto facili da modificare aggiungendo e rimuovendo gli elementi. In qualche modo nasconde il fatto che la maggior parte degli array di lingue sono a dimensione fissa e richiedono operazioni di ridimensionamento complesse. Sembra che JavaScript faciliti la scrittura di codice dell’array mal funzionante. Questo porta alla domanda:

Quali prestazioni (in termini di grande complessità temporale O) posso aspettarmi dalle implementazioni di JavaScript per quanto riguarda le prestazioni dell’array?

Presumo che tutte le implementazioni ragionevoli di JavaScript abbiano almeno le seguenti O grandi.

  • Accesso – O (1)
  • Aggiunta – O (n)
  • Prepending – O (n)
  • Inserimento – O (n)
  • Eliminazione – O (n)
  • Scambio – O (1)

JavaScript consente di pre-riempire un array con una certa dimensione, usando la new Array(length) syntax di new Array(length) . (Domanda bonus: sta creando un array in questo modo O (1) o O (n)) Questo è più simile a un array convenzionale e, se usato come array pre-dimensionato, può consentire l’aggiunta di O (1). Se viene aggiunta la logica del buffer circolare, è ansible ottenere O (1) in anticipo. Se viene utilizzato un array ad espansione dynamic, O (log n) sarà il caso medio per entrambi.

Posso aspettarmi prestazioni migliori per alcune cose rispetto alle mie supposizioni qui? Non mi aspetto che nulla sia delineato in alcuna specifica, ma in pratica potrebbe essere che tutte le principali implementazioni utilizzino array ottimizzati dietro le quinte. Esistono matrici che espandono dynamicmente o altri algoritmi di incremento delle prestazioni al lavoro?

PS

La ragione per cui mi sto chiedendo questo è perché sto ricercando alcuni algoritmi di ordinamento, molti dei quali sembrano presupporre che l’aggiunta e l’eliminazione siano operazioni O (1) quando descrivono il loro O generale.

Contrariamente alla maggior parte delle lingue, che implementano gli array con, beh, gli array, in Java Array sono oggetti, e i valori sono memorizzati in un hashtable, proprio come i normali valori degli oggetti. Come tale:

  • Accesso – O (1)
  • Aggiunta – Ammortizzato O (1) (a volte è necessario ridimensionare l’hashtable, in genere è richiesto solo l’inserimento)
  • Prepending – O (n) tramite unshift , poiché richiede la riassegnazione di tutti gli indici
  • Inserimento – Ammortizzato O (1) se il valore non esiste. O (n) se si desidera spostare i valori esistenti (ad es. Usando la splice ).
  • Eliminazione – Ammortizzato O (1) per rimuovere un valore, O (n) se si desidera riassegnare gli indici tramite splice .
  • Scambio – O (1)

In generale, l’impostazione o la distriggerszione di qualsiasi tasto in un dict viene ammortizzata O (1), e lo stesso vale per gli array, indipendentemente da quale sia l’indice. Qualsiasi operazione che richiede la rinumerazione dei valori esistenti è O (n) semplicemente perché è necessario aggiornare tutti i valori interessati.

Tutte le complessità che hai menzionato sembrano buone. Ma se l’object dell’array mantiene la lunghezza, l’aggiunta può essere eseguita anche in tempo O (1).