/* Introducere in Big O Notation
Cum calculam suma 1 + 2 + 3 + ... + n = ?
Varianta1: Big O(n^2) - complexitate patratica - 2 for Varianta2: Big O(n) - complexitate liniara - un for Varianta3: Big O(1) - complexitate constanta - 1 formula
n^k . unde k = 0,1,2,3,4,5.... n^0 = 1 k = 2 n^2 k = 3 n^3 cubica
P
n = 10
1 1 2 1 + 1 3 1 + 1 + 1 ........... 10: 1 1 1 1 1 1 1 1 1 1 */
public class BigNotation {
//varianta 1: O(n^2)
//De cate ori se executa codul? de aproximativ n x n
static int sumaPatratica(int n) {
int suma = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(j <= i) suma = suma + 1;//1;
}
}
return suma;
}
// varianta 2: Big O(n)
static int sumaLiniara(int n) {
int suma = 0;
for(int i = 1; i <= n; ++i) {
suma+=i;
}
return suma;
}
//varianta 3: Big O(1)
static int sumaConstanta(int n) {
return n * (n + 1) / 2;//rezolva instant
}
public static void main(String[] args) {
int n = 10;
System.out.println("n = " + n);
//O(n^2)
System.out.println("Big O(n^2)" + sumaPatratica(n));
//O(n)
System.out.println("Big O(n)" + sumaLiniara(n));
//O(1)
System.out.println("Big O(1)" + sumaConstanta(n));
}
};
//pentru N suficient de mare au loc inegalitatile:
// log(n) < n < n log(n) < n^2 < n^3 < 2^n <=>
// O( log(n) ) < O( n ) < O( n log(n) ) < O (n^2 ) < O (n^3) < O(2^n) <=>
//Prin complexitatea unui algoritm intelegem de fapt costul, masurat cu ajutorul unor anumiti //parametri (timp de executie, memoria necesara, numarul anumitor operatii).
/* Pentru a calcula complexitatea unui algoritm , avem nevoie sa decidem care sunt acesti parametri si sa gasim o functie de determinare a costului corespunzatoare.
- Big O Notation = Upper bound
- Big Omega Notation = Lower bound */
/* Clase de complexitati:
P - bubble sort O(n^2)
- insertion sort O(n^2)
- selection by min O(n^2)
- quicksort O(n log n)
- mergesort O(n log n)
- suma Gauss (O(1)) - complexitate constanta ; nu alegi complexitate liniara sau patratica
NP - reprezinta o clasa de problemele a caror solutie se verifica rapid in timp polinomial dar rezolvarea este mai grea
Subset Sum [1,2,3,4,5] S=10 => 2,3,5 = 2 + 3 + 5 = 10
NP-complete NP-hard
P = NP ? */