Il tempo di complessità per la Ricerca e l’operazione di Inserimento nel ordinati e non ordinati matrici che include i valori duplicati

1-)Per array ordinato ho usato la Ricerca Binaria.
Sappiamo che il caso peggiore complessità dell’operazione di RICERCA in un array ordinato è O(lg N), se vogliamo utilizzare la Ricerca Binaria, dove N è il numero di elementi di un array.
Qual è il peggior caso di complessità per l’operazione di ricerca nella matrice che include i valori duplicati, utilizza la ricerca binaria??
Sarà l’essere stesso O(lg N)?? Per favore mi corregga se sbaglio!!

Anche quello che è il caso peggiore per l’operazione di INSERIMENTO in array ordinato utilizzando la ricerca binaria??
La mia ipotesi è O(N)…. e ‘ giusto??

2-) Per la lista non ordinata ho usato la ricerca Lineare.
Ora abbiamo una lista non ordinata, che accetta anche duplicare i elemento/i valori.
Quali sono le migliori peggiore dei casi complessità sia per la RICERCA e l’operazione di INSERIMENTO.
Penso che si può utilizzare ricerca lineare, che ci consentiranno di O(N) nel peggiore dei casi sia per la ricerca
e le operazioni di eliminazione.
Possiamo fare di meglio per una lista non ordinata e la complessità delle modifiche, se si accetta duplicati nella matrice.

  • vedere come le persone buone sono qui! 2 risposte @iecut imparare ad accettare le risposte di uomo o anche non leggerli?
  • Eli.. questo è tutto il mio impegno e grazie per l’aggiunta di compiti tag! E ho appena avuto modo di sapere che uno deve accettare la risposta, ora accetto la risposta che mi sembra utile.
  • Sono contento che si sta imparando. Buona fortuna
InformationsquelleAutor iecut | 2010-04-03

 

3 Replies
  1. 2
    1. Sì.

    2. Migliore dei casi è poco interessante. (Si pensi al perché che potrebbe essere.) Il caso peggiore è O(N), fatta eccezione per gli inserti. Si inserisce in un array non ordinato sono veloce e con una sola operazione. (Di nuovo, pensare se non la vedi.)

    In generale, i duplicati fare poca differenza, tranne estremamente patologico distribuzioni.

    • Parte 1: la RICERCA complessità sarà la stessa in caso di duplicare gli elementi dell’array? L’ho preso O(N lgN)..logN per trovare il primo valore dell’array e N per tutti gli altri valori duplicati che stiamo cercando.
    • Nella parte 1, l’array è ordinato. Quindi tutti i duplicati e nello stesso luogo. Durante la ricerca, il costo è solo il tempo per trovare il primo duplicato, quindi per scorrere in avanti su tutti i duplicati, che sarà in una riga. Quindi O(lg(n) + k) dove k sarà il numero massimo di copie per una voce. Il tipico caso sarebbe k << n, e così noi di solito non si preoccupano dei duplicati. Se ci aspettiamo un enorme numero di duplicati, ci sarebbe probabilmente la nostra struttura di dati in modo diverso.
    • Rob:Così la spiegazione di part1, si può ipotizzare che la ricerca in part2 in una lista non ordinata con valori duplicati può essere fatto solo in tempo O(N) nel peggiore dei casi?? Voglio dire, se ci mettiamo a cercare un elemento in un array non ordinato,siamo in grado di farlo in tempo O(N), per quanto riguarda l’simili/duplicare uno dopo abbiamo trovato il primo valore?? Si prega di elaborare, come io sono nuovo di questa complessità dei problemi….grazie!!
    • Sì. Se sei alla ricerca di articoli, la maggior parte del lavoro si potrebbe avere a che fare è quello di passare attraverso ogni singolo elemento. Quindi O(N).
  2. 0

    Qualche aiuto sulla strada, ma non l’intera soluzione.

    1. Un caso migliore per una ricerca binaria è se l’elemento cercato è il primo elemento pivot. Il caso peggiore è quando dover scorrere tutta la strada a due elementi adiacenti e continua a non trovare quello che stai cercando. Ciò cambia se ci sono duplicati nei dati? L’inserimento di dati in un array ordinato include rimescolamento di distanza tutti i dati con una maggiore ordinamento “un passo a destra”. Il caso peggiore è che si inserisce un elemento che ha il più basso ordinamento di ogni elemento esistente.
    2. La ricerca in un array non ordinato non c’è scelta, ma la ricerca lineare come suggerisci te. Se non ti interessa l’ordinamento c’è un molto più veloce, modo più semplice per eseguire l’inserimento. Eliminare può essere pensato come prima la ricerca e quindi la rimozione.
    • Abel: grazie per la risposta. per part1: non ha affrontato il duplicato problema sia di ricerca e le operazioni di inserimento per il caso peggiore.Per la ricerca possiamo utilizzare la ricerca binaria prima di trovare il valore della chiave e quindi utilizzare la ricerca lineare per tutti i valori duplicati stesso come valore chiave che è stato trovato dalla ricerca binaria?? la complessità in questo caso sarà O(N lg N). È l’approccio corretto??
    • No, non mi darà la risposta completa, solo alcuni suggerimenti su come affrontare il problema 🙂
  3. 0

    Possiamo fare di meglio all’eliminazione di un array non ordinato! Come l’ordine non è importante in questo caso possiamo scambiare l’elemento da cancellare con l’ultimo elemento che può evitare inutili spostamenti di elementi nella matrice. Così l’eliminazione in O(1).

Lascia un commento