Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - complessità algortimo
Forum - C/C++ - complessità algortimo

Avatar
frank87 (Normal User)
Newbie


Messaggi: 20
Iscritto: 10/03/2011

Segnala al moderatore
Postato alle 18:03
Giovedì, 17/03/2011
Ciao raga sapete fornirmi quale è la complessita del seguente algoritmo:

int almenoTre(const list<string>& l,string s)
{
  assert(s.lenght>3);

int cont=0;
for(list<string>::const_iterator it=l.begin();it!=l.end();it++)
  if(it->size()<3)
  continue;
  int num_ch=0;
   for(int i=0;i<it->size() && num_ch<4;it++)
     if(s==(*it))
     num_ch++;

if(num_ch>=3)
cont++;
}

return cont;
}

Mi confonde il fatto che i due "for" non abbiano la stessa lunghezza.
Comunque questo algoritmo,data una lista di stringhe e una stringa,calcola quante di stringhe di l hanno almeno tre caratteri uguali a s. s e ogni stringa di l hanno al max 127 caratteri.
Grazie in anticipo.
}

PM
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1792
Iscritto: 26/06/2009

Up
2
Down
V
Segnala al moderatore
Postato alle 3:07
Venerdì, 18/03/2011
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
Grazie mille,sei stato molto chiaro.spiegazione perfetta. Però scusa TheKaneB,ho sbagliato a votare,volevo fare +1,ma non me lo fa piu cambiare.scusa....e grazie ancora - frank87 - 18/03/11 10:15
figurati, del voto non me ne frega una sega :-D l'importante è che tu abbia imparato una cosa in più :-) - TheKaneB - 18/03/11 20:55
PM