Algoritmi

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...

Samo jedna mala primjedba na funkciju Zamijeni, umjesto da saljes referencu na niz, te dvije varijable, zasto nebi slao samo pontere na varijable koje zelis zamijeniti:

void Zamijeni ( int *a , int *b ){

    int tmp = *a;

    *a = *b;

    *b = tmp;

}

... i sad funkciju Zamijeni pozivas sa:

Zamijeni ( &niz[i] , &niz[j] );

ili

Zamijeni ( niz + i, niz + j );

Malo ubrzanje, gotovo neprimjetno , ali da spomenem, tek toliko :D...

Nego, u nekim slucajevima je dosta veliko ubrzanje kod bubble sorta imati jednu zastavicu koja govori jeli u unutarnjoj petlji doslo do zamjene ili nije. Jer ako nije mozemo prekinuti sortiranje i sigurni smo da je niz sortiran ...

O(n*n)
Najbrži osnovni algoritam za sortiranje: znaći brži od Selectiona, i Bubblea...
Najbrži je za datoteke koje su skoro sortirane... zato se često i koristi kao nadogradnja onima koji koriste rekurziju... ali o tome kasnije...


Insertion sort je nešto teži za objasniti... insertion sort nađe prvo mjesto koje nije u redu.... uzme ga i otfura na mjesto tako da bude u redu..... onda opet nađe prvo mjesto koje nije u redu.... i stavlja ga u red.... i tako sve dok više nema elementa koje nije u redu...

ali, postoji i poboljšanje Insertiona.... a to je da se dovede najmanji element na prvu poziciju...

template <class tip>
void cmpexc (tip *a, tip *b) {

    if (*a < *b) {
       tip temp = *a;
       *a = *b;
       *b = temp;
    }

}


template <class tip>
void insertion (tip niz, int velicina) {

    for (int i = velicina -1; i >= 1; i--) cmpexc (&niz[i], &niz[i-1]);   //dovodi prvi član na mjesto....

    for (int i = 1; i < velicina; i++) {

       int j = i;
       tip v = a[i];

       while (v < a[j-1]) a[j--] = a[j];    // premješta veće članove za mjesto gore...

       a[j] = v;  // stavlja element na mjesto.

    }

}

Eto, to je to.... ako nešto ne kužite, javite

Ovo nije bublesort. Ima više naziva za ovo sortiranje. Većina ga zovu jednostavno sortiranje zamjenom (exchange sort) ili soritanje svaki sa svakim.

Bit bubble sort metode jest da se mijenjaju SUSJEDNI elementi. Osim toga, on ima svojstvo po kojem se sortiranje može prekinuti i ranije. Naime, ako u jednom koraku vanjske petlje nema ni jedne zamjene, funkcija staje i polje je sortirano (vidi varijablu sorted).

Evo koda PRAVOG bubble sorta u programskom jeziku C++:

#include <iostream>
using namespace std;

void bubble(int a[], int n) {
    bool sorted=false;
    int i=0;
    do {
        sorted = true;
        for (int j=0; j<n-i-1; j++) {
            if (a[j]>a[j+1]) {
               swap(a[j],a[j+1]);
               sorted=false;
            }
        }
        i++;
    } while ((i<n-1) && !sorted);
}

int main () {
    int a[]={7,3,4,9,2,5,1,6,7};
    bubble(a,9);
    for (int i=0; i<9; i++) cout << a[i] << " ";
    cin.get();
    return 0;
}

Ne znam odakle ti ove definicije, no tu mnogo toga ne štima.

Ovo bi bio jedan primjer stabla....
Svaki element stabla ima svoj parent element (roditelj) i svoje childrene (djecu)....

Pa tako, uzmimo sa slike element pod brojem 6: parenti su mu 7, i 2. Childreni su mu 5 i 11. Root stabla je 2.

Prvo, element stabla se ne zove parent (roditelj, već čvor (node). Roditelj je onaj čvor koji ima dijete, i to samo tome djetetu. Logično, jel da?

Drugo, u stablu svaki čvor, osim korijena (korijen nema roditelja), ima točno jednog roditelja. Tako da se ne može reći da su 7 i 2 roditelji od 6. Oni su mu PRECI (predecessors), dok je on njima potomak (successor). Ako u strukturi neki čvor ima više od jednog roditelja, onda se ne radi o stablu već o pseudostablu.

Ordered (Poredano)   -   stablo kod kojeg se zna broj djece zvakog parenta..
       Binary, or N-ary - stablo koje na svakom parentu ima ili 2, ili N djece, ili 0..... Znaći isto kao ordered, ali neki parenti nemaju djece

Ovo zaista nema veze. Naime, kod uređenog stabla (ordered tree) bit je da se zna redoslijed djece, a ne da se zna broj djece. Nadalje, NIJE istina da u binarnom stablu svaki, hm... roditelj ima dvoje djece, već neki mogu imati jedno, a neki ni jedno. Naime, binarno stablo je uređeno stablo kod kojeg svaki čvor može imati NAJVIŠE dvoje djece. Također, čvorovi se kod stabla dijele na unutarnje čvorove i listove. Unutarnji su oni čvorovi koji imaju bar jedno dijete, a listovi su oni čvorovi koji nemaju djece. Ono što je važno jest da je binarno stablo uređeno, tj. ako čvor ima dvoje djece, zna se koje mu je prvo (lijevo), a koje drugo (desno) dijete. Sličbno je kod ternarnog ili općenito kod N-arnog stabla.

I još jedan termin: dubina stabla je broj parenta koje ima taj element.

I opet netočno. Ovo nije dubina stabla, već nivo stabla na kojem se dotični element nalazi. Dubina stabla je najveći nivo na kojem se nalazi neki element stabla.

meni je jako žao zbog mojih grešaka....

Zadnje šta želim je ljude naučiti krivo.

Eto, učio sam sa raznih tutoriala, i očito pokupio krivo, tj. površno znanje,
Hvala vam na reakcijama, ali bit će bolje da ovo jednostavno izbrišem, pa ako može neki mod to uklonit, bio bih zahvalan