Analisi della complessità: ricerca di membri comuni di matrici non ordinate

Non penso che ci sia una risposta migliore per la worst case complessità nel caso generale. Probabilmente potresti solo migliorare casi specifici in cui l'input è in qualche modo limitato (diciamo i numeri tra 1 e N). In tal caso potresti usare qualcosa come Ordinamento digitale .

L'idea di Karl Bielefeldt di convertire gli array in insiemi non risolve il problema, lo nasconde solo poiché i set intersecanti (nel caso generale) vengono eseguiti in O (n ^ 2). Ad esempio, ecco l'implementazione retainAll () di Java:

public boolean retainAll(Collection<?> paramCollection) {
        int i = 0;
        Iterator localIterator = iterator();
        while (localIterator.hasNext()) {
            if (!(paramCollection.contains(localIterator.next())))
                ;
            localIterator.remove();
            i = 1;
        }

        return i;
    }

Notare l'iterazione sulla raccolta in arrivo. Per ogni elemento, il metodo chiama contains , che scorre sugli elementi del set corrente:

public boolean contains(Object paramObject) {
        Iterator localIterator = iterator();
        if (paramObject == null)
            while (true) {
                if (!(localIterator.hasNext()))
                    break label53;
                if (localIterator.next() == null)
                    return true;
            }
        while (localIterator.hasNext()) {
            if (paramObject.equals(localIterator.next()))
                return true;
        }
        label53: return false;
    }

La npinti soluzione di usare un HashSet è ugualmente problematica. Un HashSet non garantisce O (1) tempo di recupero nel peggiore dei casi. Infatti, se gli hash di tutti gli elementi N si scontrano, stai osservando O (n) recuperi / inserti. Questo ci riporta a O (n ^ 2) nel peggiore dei casi.

Non puoi fare meglio di O(n) , dato che devi esaminare ogni elemento almeno una volta per assicurarti che ci sia una corrispondenza o meno. La mia prima scelta sarebbe quella di convertire gli array in insiemi, che è O(n) , quindi prendere la loro intersezione, che è O(n) sul set più piccolo. In python:

set(array1) & set(array2)

Se devi farlo sul posto, che a volte è una restrizione in questo tipo di esercizi, la tua soluzione è piuttosto buona.

Perché non usare un set di hash? La maggior parte delle implementazioni del metodo add() , che viene utilizzato per iniettare elementi nel set, restituisce un valore booleano che indica se un elemento è stato inserito o meno. L'inserimento restituirà false se l'articolo era già lì. Quindi il tuo codice sarà simile a:

HashSet<int> set = {}
Array<int> items1 = ...
Array<int> items2 = ...

foreach (item in items1)
    set.add(item)

foreach(item in items2)
    if(set.add(item) == false)
        out >> item is duplicate

Ciò produrrebbe una complessità temporale di 2n , poiché i set di hash hanno un tempo di recupero pari a O(1) .

Se ricordo bene, O(2n) (che si riduce a O(n) ) sarebbe inferiore a O(n log(n)) . Ciò presuppone che non è necessario ottimizzare in termini di spazio.