4 Mayıs 2011 Çarşamba

Algoritma Karmaşıklığı ve Büyük O Gösterimi (Big O Notation)

Yazdığımız bir algoritmanın doğru çalıştığından emin olmakla birlikte bu algoritmayı, daha önce yazılmış ve aynı sonucu veren başka algoritmalarla karşılaştırmak isteyebilirsiniz. Burada teknik olarak değerlendirilecek başlıca iki başlık söz konusudur. Birincisi algoritmaların bellek kullanım miktarı, ikincisi ise algoritmaların hesaplama yapmak için harcadığı süredir. Mesela yazdığınız bir algoritma aynı işi yapan diğer bir algoritmadan daha hızlı çalışmasına rağmen çoğu bilgisayar için bellek aşımı gerçekleştiriyorsa bu pek uygun olmayacaktır.



Elbette diğer algoritmalarla karşılaştırma yapmak yerine,  yazdığınız bir algoritmanın tek başına analizini yapmak da isteyebilirsiniz. Bunun için yazdığınız algoritmaları ve varsa karşılaştıracağınız algoritmaları tek tek çalıştırıp hız ve bellek testi yapabilirsiniz. Ama bu tahmin edebileceğiniz gibi hem zaman açısından sıkıntı yaratır hem de elde edeceğiniz veriler donanımsal ve sistemsel değişikliklerden dolayı bilimsel olmaz.(Bu gibi işlemleri performans testi olarak da düşünebiliriz) . Bu durumda matematiksel olarak ifade edebileceğimiz, donanımsal ve sistemsel bağımlılığı olmayan bir yönteme ihtiyacımız olacaktır. Bu yöntemle algoritmamıza girdi olarak verilen verilerin miktarına bağlı olarak sonuçlar üretiriz.  İşte elde edilen bu sonuçlar ilgili algoritmanın karmaşıklığı olarak tanımlanır. Bir algoritmanın karmaşıklığı performansını etkiler ama karmaşıklık ile performans farklı kavramlardır görüldüğü gibi. Karmaşıklık hesabı yapacağımız asimptotik notasyonlardan en çok kullanılanını açıklamaya çalışayım.

Büyük O Notasyonu (Big O Notation):

O notasyonu ilk olarak 1894 yılında Alman matematikçi Bachmann tarafından kullanılmış ve Landau tarafından da yaygınlaştırılmıştır. Bu yüzden adına Landau notasyonu veya  Bachmann–Landau notasyonu da denmektedir. Algoritmanın en kötü durum analizini yapmak için kullanılan notasyondur.  Matematiksel olarak şöyle tanımlanır:

f(x) ve g(x) reel sayılarda tanımlı iki fonksiyon olmak üzere, x > k olacak şekilde bir k vardır öyle ki,
|f(x)| < C*|g(x)| dir ve şeklinde gösterilir. Burada C ve k sabit sayılardır ve x’ten bağımsızdırlar.

Bu tanımı bir örnekle daha açık hale getirmeye çalışayım:



Burada k = 1 (x’in 1’den büyük olduğu tüm durumlarda) ve C = 10 olarak alınmıştır. 



Aşağıda O fonksiyonu ile karmaşıklık hesaplamadaki bazı ana konuları madde madde açıklamaya çalışayım:

  • Sabit zamanlı ifadeler O(1) ile gösterilirler. Örnek, atama işlemleri.

  •  if - else  ifadelerinde, ifadenin if veya else bloğundaki hangi ifade karmaşıklık olarak daha büyükse O fonksiyonu o değeri döndürür. (Çünkü biliyorsunuz ki O fonksiyonu her zaman en kötü durumu analiz eder) Yani bunu şöyle ifade edebiliriz:

           Maks (if ifadesinin çalışma zamanı, else ifadesinin çalışma zamanı)

Örneğin if bloğu içi O(1) else bloğunun içi O(n) ise if – else bloğu O(n) olarak ele alınır.

            //aşağıdaki if-else ifadesi O(n)'dir
            if (ifade)
            {
                //birinci ifade O(1) olsun
            }
            else
            {
                //ikinci ifade O(n) olsun
            }

  •  Bir döngü ifadesinin içindeki bir ifade, döngünün dönme sayısı kadar çalışacağı için, eğer döngü N kez dönüyorsa ve döngü içindeki ifadenin çalışma zamanı C ise, toplam çalışma zamanı N*C’dır.

            //aşağıdaki for döngüsü O(C.N)'dir.
            for (int i = 0; i < N; i++)
            {
                //buradaki ifade C zamanda çalışsın
            }


  • İç içe döngülerde içteki döngü N kez, dıştaki döngü ise K kez dönüyorsa ve iç döngünün içindeki ifadenin çalışma zamanı C ise, toplam çalışma zamanı N*K*C’dir.
            //aşağıdaki for döngüsü O(C.N.K)'dir.
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < K; j++)
                {
                    //buradaki ifade C zamanda çalışsın
                }
            }



Notasyon
İsim
Açıklama
O(1)
Sabit
Algoritmadaki icra sayısı belliyse sabit bir değerle gösterlir. Örneğin, bir sayının tek mi çift mi olduğunun bulunması.
O(logn)
Logaritmik
n değerinin büyüyen değerlerine karşın algoritmanız çok daha az yavaşlıyorsa logaritmik bir durum söz konusudur. Örneğin, binary search ile sıralı bir dizide değer aramak.
O(n)
Lineer
n değerinin büyümesine karşılık algoritmanın lineer bir şekilde yavaşlaması söz konusudur. Örnek, sırasız bir listeden bir değeri bulmak.
O(n logn)
Loglineer
Bir problemi alt problemlere bölüp bağımsız olarak çözen, daha sonra bu sonuçları birleştiren algoritmalarda görülür. Örnek, birliştirmeli sıralama (merge sort) algoritması.
O(n^2)
Karesel
İç-içe döngüler ile verileri ikişerli şekilde inceleyen algoritmalarda görülür. Örnek, seçmeli sıralama (selection sort)
O(2^n)
Üstel
Girilen veriye göre iki kat yavaşlama görülen bu algoritmalar hiç pratik değildir. Örnek, seyyar satıcı problemi.

7 yorum:

  1. Güzel bir yazı olmuş ellerinize sağlık.Devamını bekliyoruz...İyi çalışmalar

    YanıtlaSil
  2. Çok güzel basitçe açıklayan bir yazı olmuş.

    YanıtlaSil
  3. evet güzel bir yazı olmuş.peki f(x)=2 fonksiyonu için O nedir?

    YanıtlaSil
  4. teşekkürler, sade ve güzel anlatım için

    YanıtlaSil
  5. teşekkürler gerçekten açıklayıcı olmuş 'küçük o ,büyük (omega),küçük omega, ve teta' yı da böyle açıklamalı nerden bulabilirim ?

    YanıtlaSil