Big O Notation SumBigONotation.cpp

SumBigONotation.cpp

/*
Complexitatea Algoritmilor
-------------------------


Prin complexitatea unui algoritm intelegem de fapt costul, masurat cu ajutorul unor anumiti parametri
(timp de executie, memoria necesara, numarul de operatii). PEntru a calcula complexitatea unui algoritm , avem nevoie sa decidem
care sunt acesti parametri si sa gasim o functie determinare a costului corespunzatoare.

Notatii Teta 0, O, Omega

Big O Notation  upper bound
---------------------------

n = infinit;
n = 100000000000000

cum calculam Suma = 1 + 2 + 3 + ... + n = ?

Varianta 1: O(n) - complexitate liniara

int sum = 0;

for(int i = 1; i <= n; ++i) sum += i

Varianta 2: O(n^2) - complexitate patratica

int sum = 0;

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

cout<<sum;

/*
i=1 -> j: 1
i=2 -> j: 1 1
i=3 -> j: 1 1 1
i=4 -> J: 1 1 1 1
..........
i=10; j:1 1 1 1 1 1 1 1 1 1 

Varianta 3: Divide et impera O( n ) - liniara

int sum(int li, int ls) {

	if(li == ls) return li;

	else 

	return sum(li, (li + ls)/2)  + sum((li+ls)/2+1, ls);
	
}

int main() {
	
	int n = 10;

	cout<<sum(1, n);

	return 0;
}

sum = 1 + 2 + 3 + 4 +....+10;
  
                        [1,10]

               [1,5]                [6,10]
 
            [1,3] [4,5]          [6,8]  [9,10]

          [1,2] [3,3] [4,4] [5,5]  [6,7][7,8] [9,9] [10,10]
        1 + 2 + 3 + 4 + 5 +6 + 7 + 8 + 9  + 10           
              


        

*/


#include <iostream>

using namespace std;

//Complexitate O(n)
int sum_liniara(int n) {

    int sum = 0;

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

	return sum;
}


//Complexitate O(n^2)
int sum2(int n) {

int sum = 0;

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

return sum;

}

//Complexitate O(n) divide et impera
int sum(int li, int ls) {

	if(li == ls) return li;

	else 

	return sum(li, (li + ls)/2)  + sum((li+ls)/2+1, ls);
	
}


//Formula lui Carl FRiedrich Gauss O(1) 

int Gauss(int n) {

    int sum = n * (n + 1) / 2; 

    return sum;
}

int main() {
	
	int n = 10;

	cout<<"Complexitate liniara O(n)"<<sum(1, n)<<endl;
	cout<<"Complexitate patratica polinomiala: "<<sum2( n )<<endl;
	cout<<"Complexitate liniara O(n): "<<sum_liniara( n )<<endl;
    cout<<"Complexitate constantaO(1): "<<Gauss( n )<<endl;

	return 0;
}


/*

n       O(n^2)   O(n)    O(1)

10      100      10        1


100     10000     100      1

1000  1 000 000   1000      1

Raspunsul corect: O(1) cand n este foarte mare


            Pentru n suficient de mare au loc inegalitatile:

            log(n) < n < n log (n) < n^2 < n^3 < 2^n 

            ceea ce implica 

            O(1) < O(log(n)) < O(n) < O(n log (n)) < O(n^2) < O(n^3) < O(2^n)


*/