Qual è la complessità (big-oh) per la funzione remove() nella classe Coda priorità in Java? Non riesco a trovare nulla di documentato da nessuna parte, penso che sia O (n), considerando che devi trovare l'elemento prima di rimuoverlo e quindi rimescolare l'albero. ma ho visto altri che non sono d'accordo e pensano che sia O (logn). Qualche idea?Elimina il tempo di complessità
La complessità per la rimozione è O (N) in quanto la complessità per la contiene è O (N) (in classe di coda con priorità di Java)
Un modo questo O può essere fatto (log N) nel proprio priorità L'implementazione della coda è di mantenere una struttura di dati ausiliari come una HashMap che mantiene i mapping da un valore nella coda di priorità alla sua posizione nella coda. Quindi, in qualsiasi momento, conoscerai la posizione dell'indice di qualsiasi valore.
Si noti che questa modifica non influisce sul tempo di esecuzione di nessuna delle operazioni esistenti: sarà necessario aggiornare solo i mapping durante le operazioni di heapify.
Quindi, se conosco la posizione dell'indice di un elemento, come lo rimuovo nell'API della coda di priorità in base all'indice? (nel tempo O (logN)) – novalain
@novalain Sfortunatamente, l'API Java non espone un modo di accedere agli elementi in una coda di priorità per indice, quindi dovrai usare la tua implementazione di una coda di priorità. –
Come mai è O (logN) rimuovere dalla nostra implementazione e non da O (1)? Sono sicuro che mi mancano alcuni dettagli, ma una coda di priorità è solo una struttura dati ordinata da priorità alta a bassa. Se è implementato utilizzando un elenco collegato e conosciamo l'indice, non possiamo semplicemente rimuovere quell'elemento e connettere il nodo precedente al nodo seguente? – user3125693
Secondo la documentazione di Oracle: "nota implementazione: questa implementazione fornisce O (log (n)) tempo per i metodi Enqueing e dequeing (offerta, sondaggio, remove() e aggiungere); tempo lineare per il metodo remove (Object) e contiene (Object) e il tempo costante per i metodi di recupero (peek, element e size). "
Penso che intendesse remove (object) not remove() il primo è O (n), il secondo è O (log n) –
'remove()' e 'poll()' sono gli stessi tranne per la semantica degli elementi mancanti. La rimozione di un elemento specifico ('remove (Object)') è 'O (n)'. Penso che la domanda non sia chiara e anche questa è una risposta valida ... – TWiStErRob
La confusione è effettivamente causato dalla funzione "remove". In Java, ci sono due funzioni di rimozione.
remove() -> Questo per rimuovere la testata/root, richiede O (logN) tempo.
remove (Object o) -> Questo è per rimuovere un oggetto arbitrario. La ricerca di questo oggetto richiede tempo O (N) e la sua rimozione richiede tempo O (logN).
Hai pensato di leggere Javadoc? ["questa implementazione fornisce il tempo O (log (n)) per i metodi di enqueing e dequeing (offerta, polling, remove() e add)"] (http://docs.oracle.com/javase/6/docs/api /java/util/PriorityQueue.html). – EJP
Sì, l'ho fatto. Nella riga successiva dice 'tempo lineare per la rimozione (Object) e contiene i metodi (Object); e tempo costante per i metodi di recupero (peek, element e size) ', che era il punto in cui mi stavo confondendo. Penso di aver capito ora però. – samturner