Algoritmaların Karmaşıklığı ve Büyük O Notasyonu

bazinga

Konu Sahibi
Admin
Katılım
1 Şubat 2007
Mesajlar
93,001
Reaksiyon puanı
49,676
Puanı
1,060
Konum
İstanbul
Web Sitesi
izleryazar.com
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
bigO_eleman.jpg
ş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:


bigO.jpg




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.


[FONT=&quot] //aşağıdaki if-else ifadesi O(n)'dir[/FONT]
[FONT=&quot] if (ifade)[/FONT]
[FONT=&quot] {[/FONT]
[FONT=&quot] //birinci ifade O(1) olsun[/FONT]
[FONT=&quot] }[/FONT]
[FONT=&quot] else[/FONT]
[FONT=&quot] {[/FONT]
[FONT=&quot] //ikinci ifade O(n) olsun[/FONT]
[FONT=&quot] }[/FONT]



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



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





  • İç 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.

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





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.

 

bazinga

Konu Sahibi
Admin
Katılım
1 Şubat 2007
Mesajlar
93,001
Reaksiyon puanı
49,676
Puanı
1,060
Konum
İstanbul
Web Sitesi
izleryazar.com