infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Lepadat Mihai-Alexandru din Martie 13, 2012, 21:53:44

Titlul: Problema complexitate
Scris de: Lepadat Mihai-Alexandru din Martie 13, 2012, 21:53:44

Pseudocod:

Cod:

m = n;
s = 0;
while n >= 1 {
   m = m * 2;
   for i = 1 ... m {
      s = s + i;
   }
   n = [n/2];
}

Trebuie determinat timpul de executie in functie de n(notatie-theta (http://mathworld.wolfram.com/Big-ThetaNotation.html)).
Am avut problema asta la tema si au aparut fel si fel de capete luminate cu fel si fel de pareri(solutiile variand in special intre theta(nÂ²) si theta(nÂ²log n)). Voi ce parere aveti?

Titlul: RÄƒspuns: Problema complexitate
Scris de: Laurentiu Ion din Martie 13, 2012, 22:26:11

2*(n-1)*n -> O(n²)

Titlul: RÄƒspuns: Problema complexitate
Scris de: MciprianM din Martie 13, 2012, 22:27:20

For-ul interior executa m instructiuni, unde m ia valori, pe rand: 2*n, 4*n, 8*n, ..., 2^k * n unde k este de cate ori se executa corpul while-ului. Adica k = 1+ floor (log n). De unde timpul total de executie Theta (2*n + 4 * n + 2^k * n) = Theta (n^2). k este egal cu numarul de biti din scrierea lui n in baza 2. Impartirea la 2 este echivalenta cu o shiftare la dreapta. In suma dai factor comun pe n si ramane sa calculezi suma unei progresii geometrice.