Big O je notacija za vremensku ili prostornu analizu nekog algoritma ili cijelog programa. Često služi da bismo mogli odprilike izračunati koliko će program trajati ili uzeti memorije. Big O notacija ne teži nekoj besmislenoj perfekciji. Više teži jednostavnosti izračuna, i uzimanja najgorih mogućih slučajeva. Time se osigurava da programer uvijek zna koliko će program zahtjevati u najgorem mogućem slućaju...
Big O nije baš neka mudrost.... evo, objasnit ću na primjerima:
for (i = 0; i < n; i++);
ova petlja se ponavlja n puta, zato kažemo da ima O(n).
for (i = 0; i < n; i++);
for (i = 0; i < m; i++);
ova se petlja ponavlja n puta, pa još m puta.... O(n+m);
for (i=0;i<n;i++) {
for(i=0; i<m;i++);
}
za petlje unutar petlje, množimo broj ponavljavljanja svake petlje. O(n*m);
To bi bilo to.... to su osnove... evo kompliciraniji primjer:
for (i = 0; i<n; i++) {
for (i=0; i<m;i++);
for (i=0;i<k;i++) {
for(i=0;i<n;i++);
}
}
for (i = 0; i<m;i++) {
for (i = 0; i < m; i++) {
for (i = 0; i<m;i++);
}
}
for (i = 0; i < 100; i++);
kompleksnost bi bila: O(n*(m+k*n)+m^3)
zadnju for petlju zanemarujemo.... kompjuter napravi 100 operacija u nanosekundi....
Postoji još mudrost oko binarnih stabla, grafova, i pojedinih algoritma, ali njihovu ću kompleksnost reći kada objašnjavam algoritam....
Šta se tiče vremena, ubično se uzima:
O(10000) -> program se definitivno izvrši u sekundi
O(100000) -> program će se vjerojatno izvrišit u sekundi (ovisi o kompleksnosti programa, i brzini procesora)
O(1000000) -> ~10 sekundi....
To vam se možda čini sporo.... jer moj procesor (Intel Pentium 4, 3.0) obavi oko milijun operacija u sekundi..... ali big O notacija uzima najgore slučajeve, zato raspon od 10000 - 100000 traje oko sekundu...