Complexitate

[nikel1992]

Am si eu nevoie , daca ma poate ajuta sa imi zica si mie cineva complexitatea acestui program.

void function(int* a, int n){

int m=0,aux;

for(int i=0;i<n/2;i++){

for(int j=i+1;j<n;j++){

if(a[j]<a){

aux=a; a=a[j]; a[j]=aux;

}

}

}

}

[Silviu]

O(n patrat) cred.

[nikel1992]

As avea nevoie pe pasi, adica demonstratia...

[bDyds]

Subprogramul ordoneaza crescator vectorul a. Variabila n este numarul de elemente din vector.

[Nytro]

for(int i=0;i<n/2;i++){

for(int j=i+1;j<n;j++){

Edit: Scuze, nu e ok, primul "for" merge doar pana la n/2.

Avem: (n-1)+(n-2)+...+(n-n/2). Adica mult mai putin.

De ce?

La i == 0 avem (n-1) pasi

La i == 1 avem (n-2) pasi

...

La i == n/2 - 1 avem (n - n/2) pasi

Rezultatul e suma acestor adunari.

Mai exact: n(n-1)/2 - ( n/2 * (n/2 + 1) )/2

Adica suma lui Gauss de la 1 la n-1 din care scadem suma lui Gauss de la 1 la n/2.

Cred ca rezultatul final e:

3n(n-2) / 8.

Sper ca nu m-am incurcat pe acolo: http://i.imgur.com/ebAxHOO.jpg

Edited September 17, 2013 by Nytro

[TheTime]

Nytro, ma tem ca te inseli. Nu poti avea complexitate O(n^2) in al 2-lea for, el se repeta de cel mult n ori ( j=i+1;j<n;j++, i >= 0), deci are complexitate O(n).

Cred ca silvian0 are dreptate si complexitatea finala este O(n^2). Ca performanta seamana putin cu selection sort, care are si el complexitate O(n^2). Singura diferenta majora este ca in primul for se parcurge pana la n-1, nu pana la n/2, dar aceasta diferenta nu va afecta complexitatea finala.

[Nytro]

Da, m-am corectat

[nikel1992]

Multumesc