Voglio sapere qual è il migliore: Array O Albero di ricerca binario in (inserire, eliminare, trovare max e min) e come posso migliorarli entrambi?Qual è la differenza tra l'albero di ricerca Array e Binary in termini di efficienza?
risposta
Un array consente random access a ciascun elemento in esso. quindi ottieni inserto, elimina e cerca un elemento specifico in O(1)
e max/min, elimina in O(n)
. [puoi anche fare max/min O(1)
e cancellare invece O(n)
]. Se si mantiene ordinato il proprio array, ciò causerà l'inserimento/eliminazione dello O(n)
, ma si otterrà O(logn)
find e O(1)
min/max.
Un BST è ordinato per definizione, e per un regolare [sbilanciato] BST, si ottiene O(n)
peggiore comportamento caso. Per BST bilanciato, si ottiene O(logn)
inserire/eliminare/trovare. È possibile ottenere O(1)
min/max qualsiasi come per entrambi.
Gli array sono in genere più veloci fino a iterate [presupponendo che l'ordine di iterazione non sia importante] poiché si ottiene una migliore prestazione cache. Inoltre, a differenza del BST, che ha una dimensione illimitata per natura, un array richiede la riallocazione e copia i dati quando l'array è pieno.
Migliorare un BST può essere fatto rendendo balanced - come AVL o red-black-trees.
Quale è il migliore? dipende dall'applicazione. Di solito quando si pianifica di inserire dati e tenerli ordinati, verrà preferita la BST. Se l'accesso casuale o l'iterazione è lo scopo principale: di solito si utilizza un array.
Perché le operazioni costanti 'findMin/findMax'' O (1) 'per un BST bilanciato? – Cratylus
@ user384706: Ogni volta che si inserisce/rimuove un elemento da un BST bilanciato, è 'O (logn)' e 'O (n)' per BST non bilanciato. Puoi mantenere puntatori extra 'min' e' max', che verranno modificati solo quando inserisci/rimuovi elementi dalla BST. Trovare il nuovo massimo/minimo è 'O (logn)' per BST bilanciato e 'O (n)' per non bilanciati - quindi non c'è alcuna perdita di prestazioni [grandi termini O] in questa operazione, e in termini di grande O, tu è possibile mantenere questi puntatori per "gratis" – amit
Ah, quindi si consiglia di utilizzare i puntatori extra.Ma in questo caso, si tratta di un'ottimizzazione non direttamente correlata agli algoritmi BST. Quindi non è in qualche modo incoerente/fuorviante rivendicare in un confronto con un'altra struttura dati (in questo caso un array) che 'max/min' è' O (1) 'dato che non è di default? Si deve implementarlo in modo tale che sia – Cratylus
confronto delle prestazioni di array e alberi binari di ricerca:
Array Binary search tree
Unsorted Sorted Average Worst case
Space O(n) O(n) O(n) O(n)
Search O(n) O(log n) * O(log n) O(n)
Max/Min O(n) O(1) O(1) ** O(1) **
Insert O(1) O(n) O(log n) O(n)
Delete O(1) O(n) O(log n) O(n)
*
assumendo ricerca binaria
**
richiede puntatori in più per min e max, altrimenti è O (log n)
Perché 'O (1) 'trova il massimo/minuto di un BST? – Cratylus
Ora che chiedi, non sono sicuro che sia corretto. Gli alberi di ricerca binaria sono ordinati per definizione, ma (a seconda dell'implementazione?) Potrebbe non essere possibile ottenere il minimo/il massimo in O (1). In tal caso sarebbe invece O (log n). – Peladao
Non è 'O (1)' a meno che la tua implementazione mantenga un puntatore ai valori 'min' e' max'. Controlla anche i commenti nella risposta di amit – Cratylus
- 1. Qual è la differenza tra ricerca lineare e ricerca binaria?
- 2. binario efficienza di ricerca vs. efficienza ricerca lineare in FORTRAN
- 3. Qual è la differenza tra barra di ricerca, barra di ricerca e controller di visualizzazione ricerca?
- 4. Qual è la differenza tra ndarray e array in numpy?
- 5. MWAIT vs HALT in termini di efficienza
- 6. Qual è la differenza tra classe astratta e interfaccia in termini di archiviazione in JVM
- 7. Servizi Java RESTful - Qual è la differenza tra QueryParam e PathParam in termini di utilizzo?
- 8. Qual è la differenza tra UTF8/UTF16 e Base64 in termini di codifica
- 9. qual è la differenza tra doGet() e doPost() in termini di flusso?
- 10. Qual è la differenza tra un array e un oggetto?
- 11. Qual è la differenza tra un dizionario e un array?
- 12. Qual è la differenza tra queste due iterazioni di array?
- 13. Qual è la differenza tra array di parentesi quadre e array di puntatori?
- 14. Qual è la differenza tra == e =: = in Erlang se usato con termini in generale?
- 15. Qual è la differenza tra i termini "file sorgente" e "unità di traduzione"?
- 16. Qual è la differenza tra dati in chiaro e binari?
- 17. Qual è la differenza tra modelli di fabbrica e strategia?
- 18. Qual è la differenza tra cogliere e raccogliere in Rails?
- 19. Qual è la differenza tra memset e memcpy in C
- 20. Qual è la differenza tra Boxing e AutoBoxing in Java?
- 21. Qual è la differenza tra objcopy e dsymutil?
- 22. Qual è la differenza tra MessageListener e Consumer in JMS?
- 23. F #: In termini reali, qual è la differenza tra una "stringa" e una "opzione stringa"?
- 24. Quindi qual è la differenza tra distribuito e in cluster?
- 25. Qual è la differenza tra PreserveReferencesHandling e ReferenceLoopHandling in Json.Net?
- 26. In Ember.js, qual è la differenza tra [] e Ember.A ([])?
- 27. Qual è la differenza tra = e: =
- 28. Differenza tra i termini di Android?
- 29. Differenza tra la valutazione e l'esecuzione dei termini di Gradle
- 30. Qual è la differenza tra dict() e {}?
hai provato alla ricerca di queste informazioni? Dovrebbe essere facile da trovare. – Howard
Intendi le strutture dati astratte [elenco collegato] (http://en.wikipedia.org/wiki/Linked_list) e [albero di ricerca binario] (http://en.wikipedia.org/wiki/Binary_search_tree)? – Gumbo
migliorare in che modo? il meglio per cosa? quelle sono strutture di dati completamente diverse e ognuna di esse potrebbe essere la "migliore" per una determinata applicazione. – amit