İçeriğe geç

Big-O Notasyonu (Büyük-O gösterimi) Ve Hız sıralaması

  1. Big-O Gösterimi (notasyonu)

n elemanlı bir listedeki elemanların toplamını bulmak için n-1 toplama işlemi yapmak gerekir diye genelleştirme yapmıştık. Yapılan işi, girdi boyutunun bir fonksiyonu olarak ele almış olduk. Bu fonksiyon yaklaşımını matematiksel gösterim kullanarak ifade edebiliriz : Big-O (O harfi, 0 sayısı değil) gösterimi veya büyüklük derecesi (order of magnitude). Büyüklük derecesini problemin boyutuna balı olarak fonksiyonda en hızlı artı gösteren terim belirler. Örnek olarak :
f(n) = n^4 + 100n^2 + 10^n + 50 = O(n^4)

fonksiyonunda n’in derecesi n^4’tür yani n’in büyük değerleri için fonksiyonu en fazla n^4 etkiler. Peki daha düük dereceli deyimlere ne olmaktadır? n’in çok büyük değerleri için n^4, 100n^2’den, 10n’den ve 50’den çok büyük olacağından daha düşük dereceli terimler dikkate alınmayabilir. Bu diğer terimlerin, işlem süresini etkilemedikleri anlamına gelmez; bu yaklaşım yapıldığında n’in çok büyük değerlerinde önem taşımadıkları anlamına gelir.

n, problemin boyutudur. Yııt, liste, kuyruk, aaç gibi veri yapılarında eleman sayılarıdır. n elemanlı bir dizi gibi …

Bir listedeki tüm elemanların dosyaya yazılması için ne kadar i yapılır : Cevap, listedeki eleman sayısına balıdır.

Algoritma

OPEN (Rewrite) the file WHILE more elements in list DO Print the next element

İşlemi yapmak için geçen süre : (n*(Bir elemanın dosyaya yazılması için geçen süre))+dosyanın açılması sırasında geçen süre

Algoritma O(n)’dir (Algoritmanın zaman karmaşıklığı O(n)’dir) . Çünkü, n tane işlem + sadece dosya açılması işlemi vardır. Yüzlerce elemanın dosyaya kaydedildiği düşünülürse, dosya açılması sırasında geçen süre miktarı rahatlıkla ihmal edilebilir. Ama az sayıda eleman varsa dosya açılması sırasında geçen süre miktarı önem taşıyabilir ve toplam süreye katılımı daha fazla olur.

Bir algoritmanın büyüklük derecesi, bilgisayarda işletildiğinde sonucun ne kadar sürede alınacağını belirtmez. Bazen de bu tür bir bilgiye gereksinim duyulur. Örnek olarak bir kelime işlemcinin 50 sayfalık bir yazı üzerinde yazım denetimi yapma süresinin birkaç saniye düzeyinden fazla olmaması istenir. Böyle bir bilgi istendiğinde, Big-O analizi yerine diğer ölçümler kullanılmalıdır. Program değişik yöntemlere göre kodlanır ve karşılaştırma yapılır. Programın çalıştırılmasından önce ve sonra bilgisayarın saati kaydedilir. ki saat arasındaki fark alınarak geçen süre bulunur. Bu tür bir “Benchmark” testi, işlemlerin belirli bir bilgisayarda belirli bir işlemci ve belirli kaynaklar kullanılarak ne kadar sürdüğünü gösterir.

Bilgisayarın yaptığı iin programın boyutu ile, örnek olarak satır sayısı ile ilgili olması gerekmez. N elemanlı bir diziyi 0’layan iki program da O(n) olduğu halde kaynak kodlarının satır sayıları oldukça farklıdır :

1’den n’e kadar olan sayıların toplamını hesaplayan iki kısa programı düşünelim :

Program 1, O(n)’dir. n=50 olursa programın çalışması sırasında n=5 için harcanan sürenin yaklaşık 10 katı süre harcanacaktır. Program 2 ise O(1)’dir. n=1 de olsa n=50’de olsa program aynı sürede biter.

Artı Oranı Fonksiyonları :

Fonksiyonların Büyüme Hızları

Fonksiyonların büyüme hızları küçükten büyüğe aşağıdaki gibi sıralanmaktadır. (n sayısını eleman sayısı olarak düşünebilirsiniz.)

O(1) : Sabit zaman

Örnek : n elemanlı bir dizinin i. elemanına bir değer atanması O(1)’dir. Çünkü bir elemana indisinden doğrudan erişilmektedir.

O(n) : Doğrusal zaman

Örnek : n elemanlı bir dizinin tüm elemanlarının ekrana yazdırılması O(n)’dir.

Örnek : sıralı olmayan bir dizideki (listedeki) elemanlardan birinin aranması O(n)’dir (en kötü durumda da, ortalama durumda da).

O(log2n) : O(1)’den fazla O(n)’den azdır.

Örnek : Sıralı bir listenin elemanları içinde ikili arama (binary search) uygulanarak belirli bir değerin aranması O(log2n)’dir.

O(n^2) : kinci dereceli zaman

Örnek : Basit sıralama algoritmalarının birçoğu (selection sort gibi) O(n^2)’dir.

O(n log2n) : Bazı hızlı sıralama algoritmaları O(n log2n)’dir.

O(n^3) : Kübik zaman

Örnek : Üç boyutlu bir tamsayı tablosundaki her elemanın değerini artıran algoritma.

O(2^n) : Üstel zaman, çok büyük değerlere ulaşır.

 

En Hızlı Fonksiyondan En Yavaş Fonksiyona

1 -> logn -> n -> n.logn -> n2 -> n3 -> 2n -> n!

Tarih:Algoritmalar

Tek Yorum

  1. Cok saolun cok guzel açıklamışsınız cok teşekkür ederim

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir