Salve a tutti, sono nuova e spero di aver azzeccato la categoria. Sto studiando algoritmi e strutture dati e sono un po’ in difficoltà con gli esercizi sulla complessità. Quando credo di averli capiti, poi spunta qualcosa che mi fa ricredere. Comunque, l’esercizio che vi sottopongo è questo:
Analizzare la complessità di questo algoritmi che prende in input un array e restituisce l’ultima occorrenza di una lettera (in questo caso la g):
public static int lastIndexOf(char g, char[] S) {
int j;
for (j = S.length-1; j>=0; j–) {
if (S[j] == g) {
return j;
}
return -1;
}
per quanto riguarda il caso ottimo, f(n) =1, per quanto riguarda invece il caso pessimo f(n) = 2n + 1 .
Ho problemi invece con il caso medio… il risultato dovrebbe essere questo:
ma io non riesco assolutamente ad arrivarci. Qualche anima pia riuscirebbe a spiegarmi i vari passi?
P.s. ho visto che nelle altre discussioni riuscite a scrivere le formule. Se dovesse essere un problema la mia immagine e se mi spiegate come fare, modifico il mio topic.
Si tratta di vedere, per ogni possibile stringa data in input, quante operazioni vengono eseguite seguendo l’algoritmo. Si sommano questi valori, ottenendo un certo numero T. Dopo di che si divide T per il numero totale di stringhe possibili, ottenendo appunto la quantità media di operazioni svolte.
Il numero totale di stringhe è 26^n perché ogni carattere può assumere 26 valori diversi.
Data una stringa in input, il numero di operazioni che verrà eseguito dipende solamente dalla posizione dell’ultima occorrenza di g nella stringa. Quindi, invece di esaminare le stringhe una ad una, conviene esaminarle “a pacchetti”: un pacchetto contiene tutte le stringhe per cui l’ultima occorrenza del carattere g avviene in una fissata posizione. In questo modo il numero di operazioni dipende solo dal pacchetto a cui appartiene la stringa che viene data in input.
Bisogna ricordarsi di prendere in esame anche il pacchetto delle stringhe che non contengono g.
A questo punto dovresti essere in grado di ricavare T facendo una somma che ha tanti addendi quanti sono i pacchetti. Infine trovi f_{med}(n) dividendo per 26^n, come detto all’inizio.
Da queste parole sembra quasi che tu intenda l’ultima occorrenza della g (g intesa proprio come la settima lettera dell’alfabeto italiano), ma chiaramente l’algoritmo funziona con qualsiasi altra lettera. La g che è scritta nel codice è solo il nome di una variabile e chiaramente il suo valore può essere un carattere qualsiasi.
Ti ringrazio tantissimo