Perché la complessità temporale dell'eliminazione dei nodi in elenchi con collegamenti concatenati (O (1)) più rapida dell'eliminazione dei nodi in elenchi concatenati (O (n))?Complessità temporale dell'eliminazione dei nodi negli elenchi con collegamento singolo e doppio
risposta
Ha a che fare con la complessità di correggere il puntatore successivo nel nodo precedente a quello che si sta eliminando.
Perché non si può guardare indietro ...
Il problema assume che il nodo da cancellare è noto e un puntatore a quel nodo è disponibile.
Per eliminare un nodo e collegare insieme il nodo precedente e quello successivo, è necessario conoscere i rispettivi indicatori. In una lista doppiamente collegata, entrambi i puntatori sono disponibili nel nodo che deve essere cancellato. La complessità temporale è costante in questo caso, cioè O (1).
Mentre in un elenco a collegamento singolo, il puntatore al nodo precedente è sconosciuto e può essere trovato solo attraversando l'elenco dalla testa fino a raggiungere il nodo che ha un puntatore del nodo successivo al nodo che deve essere eliminato . La complessità temporale in questo caso è O (n).
Nei casi in cui il nodo da eliminare è noto solo per valore, l'elenco deve essere ricercato e la complessità temporale diventa O (n) in entrambe le liste con collegamento singolo e doppio.
Questo non è corretto per quanto riguarda la rimozione di un nodo da un elenco collegato singolarmente che richiede complessità O (n) - vedere la mia risposta di seguito. C'è un trucco in cui si copia il valore dal nodo successivo da quello che viene rimosso e poi si salta quello in modo che punti al nodo in seguito, eliminando così la necessità di attraversare la lista. – Ben
L'inserimento e la cancellazione in una posizione nota è O (1). Tuttavia, trovare quella posizione è O (n), a meno che non sia la testa o la coda della lista.
Quando parliamo di complessità di inserimento e cancellazione, generalmente pensiamo che sappiamo già dove ciò accadrà.
A meno che l'elemento da eliminare sia il nodo principale (o primo), è necessario attraversare il nodo prima di quello da eliminare. Quindi, nel peggiore dei casi, cioè, quando abbiamo bisogno di cancellare l'ultimo nodo, il puntatore deve andare fino all'ultimo secondo nodo attraversando così (n-1) le posizioni, il che ci dà una complessità temporale di O (n) .
In realtà la cancellazione in elenchi concatenati può essere implementata anche in O (1).
Dato un elenco singolarmente concatenata con il seguente stato:
SinglyLinkedList:
Node 1 -> Node 2
Node 2 -> Node 3
Node 3 -> None
Head = Node 3
Siamo in grado di implementare delete Note 2
in modo tale:
Node 2 Value <- Node 3 Value
Node 2 -> None
Qui Sostituire il valore della Node 2
con il valore della sua prossima nodo (Node 3
) e impostare il puntatore del valore successivo sul puntatore del valore successivo di Node 3
(None
), ignorando l'efficace "duplicato" Node 3
. Quindi nessuna traversata necessaria.
- 1. Complessità temporale ricerca alfa beta
- 2. Algoritmo di Dijkstra Vs Ricerca uniforme dei costi (Complessità temporale)
- 3. complessità temporale di javascript .length
- 4. Analisi algoritmi per complessità temporale
- 5. Complessità temporale di una funzione
- 6. Complessità temporale della sottostringa Java()
- 7. La complessità temporale di Math.Sqrt()?
- 8. Javascript ES6 complessità computazionale/temporale delle raccolte
- 9. La complessità temporale del conteggio degli ordinamenti
- 10. La complessità temporale del seguente algoritmo?
- 11. La complessità temporale per l'ordinamento Shell?
- 12. Qual è la complessità temporale dell'albero trasversale?
- 13. Complessità temporale di un algoritmo ricorsivo
- 14. Java Math.pow (a, b) complessità temporale
- 15. Complessità del tempo dei metodi HashMap
- 16. Ricerca Python negli elenchi di elenchi
- 17. Complessità di std :: list :: splice e altri contenitori di elenchi
- 18. La complessità temporale delle operazioni di set python?
- 19. Codice sorgente negli elenchi puntati con testo ricostruito
- 20. WPF: clic singolo con pulsante + doppio clic
- 21. Echo citando singolo e doppio in PHP
- 22. Comprensione differenza tra doppio preventivo e preventivo singolo con __repr __()
- 23. Come fare doppio clic e singolo evento per il pulsante di collegamento del controllo Asp.net?
- 24. Collegamento doppio a TextBox
- 25. Perché la complessità temporale di questo ciclo non è lineare?
- 26. elenco doppio collegamento corrotto?
- 27. Qual è la complessità temporale di questa funzione in Scheme?
- 28. Qual è la complessità temporale della mia funzione?
- 29. Quale sarebbe la complessità temporale dell'algoritmo del triangolo pascal
- 30. Complessità ciclopica con condizioni composte e cortocircuiti
Compiti? Scrivi il codice per eliminare un nodo da un elenco collegato singolarmente, e quindi sarà ovvio. –
Penso che non ci dovrebbero essere abbreviazioni come dll nel titolo, ma non riesco a pensare ad una migliore. –