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
Algoritmi - calcolo complessità
Forum - Algoritmi - calcolo complessità

Avatar
andrex91 (Member)
Pro


Messaggi: 101
Iscritto: 01/05/2009

Segnala al moderatore
Postato alle 14:06
Lunedì, 30/01/2012
Salve,

sta mattina ho dato l'esame di IP e mi è stato chiesto di calcolare la complessità nel caso peggiore della seguente funzione:

Codice sorgente - presumibilmente C++

  1. void r(vector<int> & v, int n) {
  2.     int i=0;
  3.     while (i<v.size()) {
  4.     if (v[i]>n) {
  5.          for (int j=i+1; j<v.size(); j++) v[j-1]=v[j];
  6.          v.resize(v.size()-1);
  7.     }
  8.     else i++;
  9.     }
  10. }



N è la dimensione del vettore.
I miei calcoli mi hanno portato a stimarne una complessità quadratica, mentre in teoria (secondo le soluzioni) dovrebbe essere lineare.
Qualcuno sa darmi qualche delucidazione? Grazie :)

Ultima modifica effettuata da andrex91 il 30/01/2012 alle 14:34
PM
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Up
5
Down
V
Segnala al moderatore
Postato alle 10:51
Martedì, 31/01/2012
HeDo, ha ragione lui. Nel caso pessimo, ossia quando l'array è costituito da elementi sempre maggiori di n, la complessità è quadratica.
Infatti, in questo caso, il contatore i non viene mai incrementato, ma solo la dimensione dell'array diminuisce. Ciò significa che se i inizia da 0, alla prima iterazione del while il for interno farà size - 1 iterazioni, poi size - 2, poi size - 3, eccetera... Calcolando la somma di questa serie aritmetica si ottiene una complessità pari a size * (size - 1) / 2.
Ho anche fatto una simulazione per essere sicuro e i risultati combaciano.

allora ha failato la prof, dovrebbe presentarsi a ricevimento con questa analisi :) - HeDo - 31/01/12 13:04
cmq potrebbe essere che il testo del problema non sia solo quello, magari c'è altro in giro - HeDo - 31/01/12 13:07
Boh, forse... Meglio che rileggi il testo prima di andare a contestare il voto XD - Il Totem - 31/01/12 15:01
Ieri in laboratorio ci hanno confermato che era sbagliata la soluzione, la complessità è veramente quadratica ;) - andrex91 - 01/02/12 08:56
PM
Avatar
HeDo (Founder Member)
Guru^2


Messaggi: 2765
Iscritto: 21/09/2007

Up
3
Down
V
Segnala al moderatore
Postato alle 15:04
Lunedì, 30/01/2012
anche se ci sono due cicli annidati, il ciclo interno contiene una resize, ovvero una funzione che riduce la lunghezza del vettore ad ogni iterazione :)

Quindi il fatto che l'indice i rimane a 0 non conta nulla vero? comunque grazie ;) - andrex91 - 30/01/12 16:34
Ok ho capito :) - andrex91 - 30/01/12 17:01
PM