il ciclo più esterno si ripete al massimo N volte, dove N è il numero di stringhe.
Per ognuna delle N iterazioni, devi scansionare delle stringhe di lunghezza L1, L2, L3, ....... fino a Ln.
La complessità nel caso peggiore è data quindi da O(N x L) dove L = max(L1, L2, .... , Ln)
Questa formula vale per N e L assolutamente arbitrari.
Nel caso in cui le stringhe abbiano un limite superiore, 127 nel tuo caso, la formula diventa O(N x 127), ma siccome 127 è una costante indipendente da N, l'andamento asintottico dell'upper bound rimane lineare, quindi semplicemente O(N).
La spiegazione sta nel fatto che, nel caso di lunghezza limitata a priori a 127 caratteri, posso (volendo) eliminare il for interno sostituendolo da una catena di 127 if else if else .... ecc... quindi avrei un numero costante di istruzioni all'interno di un ciclo lungo N.
Ultima modifica effettuata da TheKaneB il 18/03/2011 alle 3:11 |