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:
-
Per il
arrayList
dioperations
, ottengo sempre una posizione specifica, quindi non eseguo l'iterazione. È sempreO(1)
. -
Per
ArrayList<LinkedHashSet<String>>
, devo eseguire l'iterazione, quindi la complessità nel caso peggiore è O (n) -
l'operazione
if (subSet.contains(toPrint))
, sarà O (1), perché hashSet ha mappato tutti gli oggetti al suo interno. -
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.