|
|
|
|
Strumenti |
11-08-2017, 15:59 | #1 |
Junior Member
Iscritto dal: Aug 2014
Messaggi: 12
|
[Algoritmi] Complessità computazionale del metodo "lastIndexOf"
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: https://ibb.co/jmaeuv ma io non riesco assolutamente ad arrivarci. Qualche anima pia riuscirebbe a spiegarmi i vari passi? P.s. Se dovesse essere un problema la mia immagine mi scuso anticipatamente. (non riuscivo a caricarla e così ho messo il link) Grazie anticipatamente! |
13-08-2017, 13:26 | #2 |
Senior Member
Iscritto dal: Nov 2005
Messaggi: 2745
|
Perché il caso peggiore è 2n+1? n cos'è? Il caso peggiore è n dove n è la lunghezza della stringa. La soluzione del caso medio riportata nell'immagine presuppone che il carattere cercato compaia con una probabilità di 1/26 ma non capisco la moltiplicazione per 2i, dovrebbe essere moltiplicato per i.
Inviato dal mio F5121 utilizzando Tapatalk |
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 21:22.