[ALGORITMI] Complessità in tempo del metodo “LastIndexOf”

[Calliope007]

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:

1e707a0ccd28cafaf43fb418dd727d8cbd1fd7d6.png


ma io non riesco assolutamente ad arrivarci. Qualche anima pia riuscirebbe a spiegarmi i vari passi?


Grazie anticipatamente!

[MItaly]

Assumendo che l'intera stringa sia composta da lettere minuscole a caso (e g sia una particolare lettera minuscola), c'è probabilità 1 su 26 di beccare g ad ogni iterazione del loop.

Complessivamente:
Che probabilità c'è di beccarla alla prima iterazione (un solo giro, costo = 1)? 1/26
Alla seconda iterazione (un giro per il primo check, un giro per il secondo check, costo = 2)? 1/26 * 25/26
(il 25/26 deriva dal fatto che, per beccarla alla seconda iterazione, devo non averla beccata alla prima, per cui siamo nelle probabilità "residue" rispetto all'averla beccata nel primo caso)
Con lo stesso ragionamento, per beccarla alla terza iterazione (costo = 3, perché ho fatto tre giri di loop per arrivare fin qui), abbiamo 1/26 * 25/26 * 25/26
(siamo nei residui della prima e nei residui della seconda)
Generalizzando questo ragionamento, abbiamo che la probabilità di beccare la lettera che cerchiamo all'i-esima iterazione è:


Ora, per ottenere il costo medio moltiplico ciascun costo per la sua probabilità e li sommo tutti assieme, da cui la formula che cercavi:


Qualche considerazione in proposito:

• manca un 2 che potrebbe saltare fuori dal fatto che il tuo professore considera per ciascun loop 2 invece che 1 come costo perché boh ci sono due istruzioni; la cosa è comunque completamente irrilevante, dato che (1) addirittura le istruzioni assembly eseguono in tempo diverso l'una dall'altra, quindi stare a fare queste finezze su istruzioni Java di alto livello è completamente privo di ogni senso, e (2) in notazione asintotica in ogni caso le costanti cadono, dato che interessa l'andamento generale al variare di n;
• l'assunzione iniziale delle 26 lettere minuscole può essere ovviamente generalizzata ad un alfabeto più ampio (52 lettere maiuscole e minuscole; 62 includendo i numeri; tutti e 256 i valori possibili che può assumere un byte; tutti i 65536 valori che può assumere un char in Java); basta sostituire nella formula risultante il 26 con il numero di caratteri totali dell'alfabeto considerato e il 25 con lo stesso numero meno uno;
• l'assunzione di fondo che tutti i caratteri dell'alfabeto siano equamente distribuiti è ovviamente falsa in praticamente ogni ambito, come sa chiunque abbia mai giocato a Scarabeo . Può essere un esercizio interessante ragionare un po' su come si può "correggere" il caso medio per tenere conto di questo fatto.