Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Big O notacija programa

[es] :: C/C++ programiranje :: C/C++ za početnike :: Big O notacija programa

[ Pregleda: 2406 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

azzpoz

Član broj: 300637
Poruke: 96



+1 Profil

icon Big O notacija programa21.04.2013. u 22:02 - pre 133 meseci
Code:
int n = 100;
    int j = 20;

    for (int i = 0; i < n; i++)
    {

        for (int x = 0; x < n; x++)
        {
            
        }
n/=2;
    }


Interesuje me koja je Big O notacija za ovaj algoritam.
Zbunjuje me n/=2.

Da li je ovo eksponencijalno izvršavanje, tj. x^a

P.S. Mislim da na ovom forumu mogu dobiti pravi odgovor!
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249



+96 Profil

icon Re: Big O notacija programa22.04.2013. u 10:09 - pre 133 meseci
Da nema ovog n = n / 2 algoritam bi se izvršavao n+n+n+...+n (n puta) = n*n puta. Kad dodamo n = n / 2 i uzmemo da je k broj iteracija spoljne petlje algoritam se izvršava n + n/2 + n/4 + ... + n/(2^(k-1)) puta (ima k sabiraka). U svakoj iteraciji spoljne petlje broj iteracija unutrašnje petlje se prepolovljuje. Pitanje je samo kako doći do k. k je rešenje jednačine n/(2^k)=k (mesto preseka dve linije, jedna linija je eksponencijalna funkcija, a druga je prava linija). To je tačka u kojoj brojač i konačno postaje veći od "stalno prepolovljujućeg" n.

Probaj sam da dođeš do k kad je dato n, a zatim da uvrstiš to u početnu sumu, i pretpostavljajući da n teži beskonačnosti tu sumu svedeš na nešto jednostavnije.
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: Big O notacija programa

[ Pregleda: 2406 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.