calcola la complessità di LinkedHashSet

Question

calcola la complessità di LinkedHashSet

#1 da (3 voti)
#2 da (0 voti)

1

Ho un ArrayList<LinkedHashSet<String>> setOfStrings per esempio questo arraylist internamente è composto come:

positionX[hello,car,three,hotel,beach]
positionY[.....]
...

Voglio trovare auto all'interno di questa struttura dati, quindi l'ho fatto

for (Iterator<LinkedHashSet<String>> iterator = setOfStrings.iterator(); iterator.hasNext();) { 
    LinkedHashSet<String> subSet = iterator.next();
    if (subSet.contains("hotel"))
        System.out.println("found");
}

Il per iterare sull'intero arrayList e la complessità nel caso peggiore è O (n), ma sono confuso sulla complessità del metodo contains() di set. In base a javadocs questo metodo viene eseguito in tempo costante , ma ho sentito che in alcuni casi la complessità potrebbe diventare O(n) . Detto questo, non sono sicuro della complessità di questo algoritmo di snippet.

Qualcuno può fornirmi una spiegazione?

java big-o algorithm-analysis

posta OiRc 18.06.2014 - 15:05

fonte

2 risposte

0

Per operazioni di hashing come contains() hai sopra, la complessità del caso peggiore è grande O di n. Questo accade quando ci sono n istanze con lo stesso valore di hash e l'implementazione dell'hashing è concatenata. Ciò accade anche quando n istanze hanno la stessa sequenza di valori hash e l'implementazione è indirizzamento aperto. Entrambi questi casi sono improbabili, ma tuttavia contiene () è grande O di (n) e piccolo O di (n) e quindi è theta di (n).

In pratica, le persone spesso si preoccupano della complessità del tempo di esecuzione medio e la complessità del tempo di esecuzione medio di contains() in esecuzione su una sequenza abbastanza grande di input è infatti ammortizzata in circa costante.

risposta data 19.06.2014 - 12:56

fonte

Leggi altre domande sui tag java big-o algorithm-analysis

Abbastanza confuso su ciò che costituisce lo stato corrente di una risorsa Come cambierei la precisione di una variabile in Python?

score 3 · Accepted Answer

LinkedHashSet , per gli intenti e gli scopi di accesso con contains è semplicemente un hash impostato. Usa il ritorno da hashCode degli oggetti inseriti in esso per determinare la posizione in cui inserirlo nel set di hash. Se hai una collisione, allora controllerà l'elemento successivo. Se questo è occupato, controllerà quello dopo, e così via. Pertanto, per i set di hash con capacità o tipi relativamente piccoli che non restituiscono valori di hashCode distinguibili, verrà visualizzato fino a O(n) complessità per l'inserimento o il controllo dell'esistenza di un elemento nel set di hash. Tuttavia la maggior parte delle volte non vedi collisioni e quindi nella maggior parte dei casi sarà O(1) .

Combina questo con un'operazione O(n) su tutte le entrate in ArrayList , e finisci con O(n)*O(1) complessità in media o O(n) . Tuttavia se hashCode() non distingue correttamente i valori o se la capacità è piccola per LinkedHashSet , è possibile visualizzare fino a O(n*m) complessità ( O(n)*O(m) ) dove n è il numero di elementi in ArrayList e m essendo il numero di elementi in media in ogni LinkedHashSet .

Spero che risponda alla tua domanda!