Big O

[eindoforat]

Arkadaslar algoritmada verimlilik ile ilgili bilgilere ihtiyacim var."Big O" diye bisey varmıs ve bu konuyla ilgiliymiş.Big O yada algoritmada verimlilik ile ilgili bana onerebileceginiz siteler yada mevcut dokumanlar var mi?

[Euclides]

Bir diznin büyüme hızı...
n = bir doğal sayı(sabit)
z = tam sayı (değişken)
Doğal sayılar < log(Z) < N*Z < Z^N < N^Z < Z^Z

Sonsuza ulaşma hızla böyle bir şeydi (sıralama yanlış olabilir.. ?? )

[Sabahi]

Big O matematikte fonksiyonlarin asymptotic davranislarini tanimlamak icin kullanilan bir notasyon sadece. Bilgisayar bilimindeki kullanim alani ise algoritmalarin analizi. Matematikten bir ornek verirsek diyelim ki f(x) = 3x^5 + 2x^2 ve g(x) = x^5 gibi iki polynomials olsun. Bu durumda f(x) has order O(g(x)) yada O(x^5) diyebiliriz. Nedeni x buyudukce f(x) in diger terimlerinin ve sabitlerin x^5 a oranla cok kucuk kalacaklari icin ihmal edilebilecek olmasi. Bunu algoritmalara uygularsak y = x + 1; gibi bir aritmetik islemin execute edilmesi icin gecen zamanin sabit olacagini kabul edebilir ve 1 zaman unit diyebiliriz. Big O notasyonu ile kisaca O(1). Eger
int y = 0;
int c = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j <n j++)
{
y = y + 1;
}
c = c + 1;
}
gibi bir donguyu ele alirsak y = y + 1; n^2 kere calisacak ve c = c+ 1; n kere calisacak demektir yani O(n^2 + n) fakat n ihmal edilebilecegi icin O(n^2). Burdanda T(n) E O(n^2) yani bu algoritmanin time kompleksligi n^2 dir diyebiliriz.
Tabii boyle bir analiz cok kesin bir olcum degil yinede diyelim ki yazdigim bir programda bir searching algoritmasi kullanmak istersem lineer search algortmasi gibi O(n) ile binary search gibi O(logN) iki algortma arasinda bir tercih yapmama oldukca yardimci olabilir.

[myavuzselim]

Fakat burada n'in ne ifade ettigini unutmamak gerek. Yukaridaki ornekte int n'deki n ile O(n^2)'daki n ayni degil. Sabahi algoritmanin n=10 oldugu bir durumunu ornek olarak vermis.

Eger oyle olmasaydi yukaridaki algoritmaya da sabit derdik, cunku her zaman ayni surede tamamlanirdi.
Biraz kafa karistirici oldu galiba, soyle yapalim:

PHP Kodu:

int oylesineBirsey(int n) {
    int x=0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            x++;
        }
     }
    return x;
} 


Yukaridaki algoritma verilen n degerine gore O(n^2).

PHP Kodu:

int baskaBirsey(int m, int n) {
    int x = 0;
    for(int i=0; i<m; i++) {
        for(int j=0; j<1000000; j++) {
            for(int k=0; k<n; k++) {
                x++;
            }
        }
    }
    return x;
} 


Yukaridaki algoritma O(m*n). Ortadaki dongunun karmasikliga bir etkisi yok, cunku her zaman ayni sayida isletilecek (Bu demek degildir ki bu algoritmamizi yavaslatmiyor. Aslinda algoritma yaklasik 1000000 defa yavasliyor)

[Sabahi]

@myss
haklisin n yerine 10 yazmak hataydi duzelttim tesekkurler.