problema nel calcolo della complessità di Big O

0

ho questa funzione su cui devo calcolare la complessità temporale con la notazione Big O :

public void print(ArrayList<String> operations, ArrayList<LinkedHashSet<String>> setOfStrings) {
    int numberOfStrings = 0;
    int numberOfLetters = 0;
    String toPrint = operations.get(1);
    for (Iterator<LinkedHashSet<String>> iteratorSets = setOfStrings.iterator(); iteratorSets.hasNext();) {
        LinkedHashSet<String> subSet = iteratorSets.next();
        if (subSet.contains(toPrint)) {
        for (Iterator<String> iterator = subSet.iterator(); iterator.hasNext();) {
            numberOfLetters = numberOfLetters + iterator.next().length();
        }
        numberOfStrings = subSet.size();
        break;
        }
    }
}

il metodo esegue questa operazione:

Ad esempio, se ho come operazione print foo , devo fare questi passaggi, prima di tutto, devo trovare dove foo è:

  • Dentro setOfStrings , posso avere questa situazione:

            position 1 : [car, tree, hotel]
            ...
            position n : [lemon, coffee, tea, potato, foo]
    
  • Quando trovo la stringa foo , devo salvare il numero di stringhe all'interno di quella posizione e il numero di lettere di ogni stringa, quindi in questo caso, salverò:

       5(number of strings) 23(sum of number of letters)
    

alcune considerazioni:

  1. Per il arrayList di operations , ottengo sempre una posizione specifica, quindi non eseguo l'iterazione. È sempre O(1) .

  2. Per ArrayList<LinkedHashSet<String>> , devo eseguire l'iterazione, quindi la complessità nel caso peggiore è O (n)

  3. l'operazione if (subSet.contains(toPrint)) , sarà O (1), perché hashSet ha mappato tutti gli oggetti al suo interno.

  4. l'iterazione all'interno dell'hashset fatto con for (Iterator<LinkedHashSet<String>> iteratorSets = setOfStrings.iterator(); iteratorSets.hasNext();) , sarà O (m), perché devo scorrere all'interno dell'intero hashset per sommare le lettere di ogni parola

quindi in conclusione penso che la complessità temporale di questo algoritmo sia (O(n)*O(m))

queste considerazioni sono tutte corrette? grazie.

    
posta OiRc 19.06.2014 - 15:07
fonte

1 risposta

1

È un po 'più complicato di così. La complessità peggiore è O(M * N) e la complessità del caso migliore è O(N) .

Esistono due scenari peggiori:

  • quando ogni sottoinsieme contiene la stringa toPrint o
  • quando i sottoinsiemi contengono stringhe che hanno tutti lo stesso valore.

(Il secondo è estremamente improbabile, a meno che qualcuno non inserisca deliberatamente la struttura dati con dati con quella proprietà, ma è comunque un caso che deve essere considerato in un'analisi approfondita della complessità.)

Lo scenario migliore è quando le stringhe nei sottoinsiemi hanno un hash "bello" E la probabilità del contains test che restituisce true tende a zero.

Infine, N è la dimensione di setOfStrings , e M è la dimensione media di un sottoinsieme.

    
risposta data 19.06.2014 - 15:29
fonte

Leggi altre domande sui tag