Complessità del tempo di inserimento nell'elenco collegato

Question

Scuse Se questa domanda si sente come una verifica della soluzione, ma questa domanda è stata posta nel mio test di ammissione laureata e c'è molto da cavalcare su questo:

.

Qual è la peggiore complessità del tempo del caso dell'inserimento di $ N $ elementi in un elenco collegato vuoto, se la lista collegata deve essere mantenuta nell'ordine ordinato? .

A mio parere, la risposta dovrebbe essere $ o (n ^ 2) $ perché in ogni inserimento, dovremo inserire l'elemento nel posto giusto e È possibile che ogni elemento debba essere inserito nell'ultimo posto, dandomi una complessità del tempo di $ 1 + 2 + ... (n-1) + n= o (n ^ 2) $

Tuttavia, la soluzione che ho detto che possiamo prima ordinare gli elementi in $ o (n \ log n) $ e poi, possiamo inserirli uno da uno in $ o (n) $ , dandoci una complessità complessiva di $ o (n \ log n) $ < / span>.

Dall'esercizio indicato della domanda, quale soluzione è più apt? A mio parere, poiché la domanda menziona "La lista collegata deve essere mantenuta in ordine ordinato", sono propenso a dire che non possiamo ordinare gli elementi in anticipo e quindi inserirli nell'ordine ordinato.

Answer 1

La domanda afferma solo che l'elenco di destinazione deve essere mantenuto in ordine ordinato. Non dice nulla di qualsiasi altra struttura dei dati che potresti scegliere di utilizzare. La soluzione proposta prima fa parte di pre-elaborazione degli argomenti da inserire, quindi l'inserimento corretto. Questo è consentito dall'istruzione del problema.

Un motivo pratico per farlo, anziché inserire gli elementi, quindi ordinare, se l'oggetto elenco collegato è condiviso con un altro thread che lo richiede sia sempre ordinato. (In tale scenario, avresti bisogno di assicurarti che l'inserimento di un elemento sia atomico.) Quindi questa domanda non sta solo facendo requisiti strani per il bene di essere strano. È il tipo di requisiti che vengono spesso nel mondo reale della programmazione.

Un'altra soluzione con la stessa complessità sarebbe quella di inserire gli elementi nell'elenco di destinazione come arrivano e mantengono un parallelo Struttura dei dati di mappatura dei valori dell'elemento per i puntatori del nodo nell'elenco di destinazione. Per inserire ciascun elemento, trovare l'elemento precedente nella mappatura e inserire il nuovo elemento dopo questo nodo. Ciò presuppone che il processo di inserzione crea i nodi dell'elenco come va (al contrario di riempire i nodi vuoti esistenti).

Questa domanda è più sulla comprensione della lettura rispetto agli algoritmi. Il modo in cui è formulato, è un po 'una domanda di trucco. È in qualche modo scarsamente formulato perché si basa sulla lettura precisa, ma non riesce a dichiarare alcune supposizioni chiave, come il fatto che ottenendo gli elementi per inserire i costi $ o (n) $ , confrontando due elementi possono essere eseguiti in $ o (1) $ e il dominio di ingresso è efficacemente illimitato (esercizio: inventa con una matematica $ o (n) $ algoritmo Se gli ingressi sono numeri interi nell'intervallo $ [1,42] $ ). Ma la risposta indicata è corretta.

Hai fatto il presupposto che non esiste un modo per utilizzare una struttura dei dati ausiliari. Nulla nell'istruzione del problema si impegna a utilizzare strutture dati ausiliarie. Un modo semplice per proibire le strutture dati ausiliarie sarebbe quella di richiedere $ o (1) $ memory overhead.

Si noti che anche sotto questa ipotesi, il tuo ragionamento è sbagliato, o almeno impreciso. Se ti capita di sapere che gli elementi sono forniti nell'ordine corretto, è possibile mantenere un puntatore alla coda della lista e continuare ad inserire lì, che prenderebbe $ o (n) $ . Il caso peggiore non è se ogni elemento deve essere inserito nell'ultima posizione nell'elenco di destinazione, ma all'ultima posizione raggiunta quando si attraversa l'elenco in qualche modo. Il caso peggiore è in effetti $ \ theta (n ^ 2) $ , ma per dimostrare questo, devi dimostrare che trovare il punto di inserimento nell'elenco prende $ \ theta (n) $ tempo, e questo richiede dimostrare che la distanza da qualsiasi puntatore che hai nell'elenco è delimitato di seguito da $ \ omega (n) $ . Questo è il caso se hai un numero costante $ A $ di puntatori (hai assunto implicitamente $ a= 1 $ , con un singolo puntatore all'inizio dell'elenco), in modo da poter attraversare almeno $ k / a $ nodi dopo $ k $ inserzioni nel caso peggiore.

Answer 2

La migliore struttura possibile che conosco, sono cumuli di fibonacci, è possibile inserire elementi in $ o (1) $ ed estrarre il minimo in $ o (\ log (n)) $ , questo significa se è necessario un ordine ordinato di tutti gli elementi ti vogliono $ o (n \ log(n))) $ Mentre inserenti nuovi elementi costano solo $ o (1) $ , non so nessun'altra struttura che potrebbe tenere il passo con questo.

Answer 3

È davvero una domanda complicata.Prima di tutto, la complessità di O (Nlogn) si applica solo agli algoritmi che utilizzano il confronto tra i loro elementi (algoritmo comparativo).Ci sono anche algoritmi che non sono comparativi come il radix ordinamento che la loro complessità dipende dalla dimensione in bit che i numeri devono essere memorizzati in memoria.Quindi, se assumiamo che possiamo ordinare i numeri in anticipo con qualsiasi algoritmo, quindi possiamo anche supporre che i numeri siano naturali e l'elemento massimo è M <10, quindi con radix ordinamento che si otterrebbe il caso peggiore o (10n)= o (n).Se non possiamo fare qualsiasi presupposto, allora hai ragione.Se sei autorizzato a utilizzare elenchi collegati e nient'altro (nessuna indicizzazione di alcun tipo), la complessità è o (n ^ 2) (Ordina bolla).

Answer 4

dovrebbe essere o (n). Segui l'algoritmo AS -

1) Se l'elenco collegato è vuoto, quindi effettuare il nodo come testa e restituiscilo.

2) Se il valore del nodo da inserire è più piccolo del valore del nodo della testa, quindi inserire il nodo All'inizio e renderlo testa.

3) In un ciclo, trova il nodo appropriato dopo che il nodo di input deve essere inserito.

Per trovare il nodo appropriato iniziare dalla testa, Continua a muoverti fino a raggiungere un nodo che il valore è maggiore di il nodo di input.Il nodo poco prima è il Nodo appropriato

4) Inserire il nodo dopo il nodo appropriato trovato nel passaggio 3