NTP

3. Osnovne klase slozenosti:
   Konstantna, tj. O(1)
   void Razmeni(int[]a, int i, int j) {
   int b;
   b = a[i];
   a[i] = a[j];
   a[j] = b;
   }
   
   Logaritamska slozenost, tj. O(log(n))
   Binarna pretraga
   
   Korenska slozenost, O(sqrt(n))
   Provera da li je broj n prost broj
   
   boolean jesteProst(int n) {
   if (n == 1)
   return false;
   int d;
   d = 2;
   while (d < n) {
   if (n % d == 0)
   return false;
   d = d + 1;
   }
   return true;
   }
   
   boolean jesteProst(int n) {
   if (n == 1)
   return false;
   int d;
   d = 2;
   while (d <= n / 2) {
   if (n % d == 0)
   return false;
   d = d + 1;
   }
   return true;
   }
   
   Ako n ima (netrivijalnog) delioca (tj. delioca razlicitog od 1 i od n,
   onda ima delioca d koji je manji ili jednak od sqrt(n).
   
   Ako je d delilac broja n, onda je n / d ceo broj, odnosno i (n / d) je delilac broja n.
   d * (n / d) = n
   
   boolean jesteProst(int n) {
   if (n == 1)
   return false;
   int d;
   d = 2;
   while (d * d <= n) {
   if (n % d == 0)
   return false;
   d = d + 1;
   }
   return true;
   }
   
   Linearna slozenost, O(n)
   Odredjivanje minimalnog (maksimalnog) elementa niza
   Loglinearna O(n * log(n))
   napredni postupci sortiranja niza: merge sort, heap sort, quick sort
   
   O(n * sqrt(n))
   Kvadratna O(n^2)
   neefikasni postupci sortiranja: selection sort, insertion sort, itd.
   
   Eksponencijalna (O(a^n)), a > 1, npr. a = 2, 3, 4, ….
   Bektrek, npr. rasporedjivanja kraljica na sahovsku tablu tako da se ne napadaju obilazak sahovske table skakacem