Home / Algoritmalar / Algoritma Analizi – Big O (Büyük O) Hesaplama

Algoritma Analizi – Big O (Büyük O) Hesaplama

Geçen yazımızda Big O nedir sorusunu yanıtlamaya çalışmıştık. Bu yazımızda Big O kavramını kullanarak bir programın algoritma analizini yapmaya başlayacağız.

Tabii ki bu analizi gerçekleştirirken bir önceki yazımızda anlattığımız formülü kullanmayacağız, çok basit bir şekilde algoritma analizini gerçekleştirebileceğiz. Tek yapmanız gereken kodun çalışma zamanını hesaplamak. Şimdi Big O değerlerine göre incelememizi yapalım.

O(1)

O(1) ile ifade edilen fonksiyonun büyüme sayısı 1’dir. Bunun kod olarak karşılığı döngü içermeyen, tek seferlik karar yapısı bulunan yazılımlardır. Yani if(n == 3) satırı tahmin edeceğiniz üzere 1 kere çalışır. Doğal olarak da Big O değeri O(1) olarak ifade edilir. Yine aynı mantıkla değişken atama, switch case gibi ifadelerde de O(1) geçerlidir. Ezber yapmanıza gerek yok bir kod parçacığına baktığınızda “burası kaç kere çalışır” diye bir soru sormanız yeterli.

O(n)

Big O değeri n olan ifadeler genelde döngülerdir. n nedir derseniz, n eleman sayısının karşılığıdır. Bir döngü n kere dönüyorsa o döngünün algoritma karşılığı O(n)’dir diyebiliriz.

   
   for (int i = 1; i <= n; i++) {  
        // herhangi bir atama işlemi
   }

Yukarıdaki döngü tahmin edeceğiniz üzere n kez döner. yani n kez işlem yapar. Burada dikkat etmeniz gereken nokta for döngüsünün içerisindeki işlemlerin sonucu değiştirebileceğidir. Biz döngü içerisinde başka döngülerin bulunmadığı durum için O(n) diyoruz.

O(nc)

Karmaşıklığı n üzeri c olan ifadeler iç içe döngülerin karmaşıklığıdır. n en içteki döngünün dönme sayısıdır. c ise üstteki döngünün dönme sayısıdır.

   for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
      
       }
   }

Yukarıdaki döngü O(n2) karmaşıklığa sahiptir. n^2 karmaşıklık matris işlemlerinde sıklıkla karşımıza çıkmaktadır.

O(Logn)

Eğer bir kodda sürekli olarak bir çarpım ya da bir bölüm işlemi yapılıyorsa bu durumda logn karmaşıklığı oluşur. Daha sonra bahsedeceğimiz divide and conqueror mantalitesine sahip fonksiyonlarda O(Logn) karmaaşıklığı görülmektedir.

   for (int i = 1; i <=n; i /= c) {
       
   }

Yukarıdaki kod parçacığında i’nin her döngüde c değerine bölündüğüne dikkat edin. Bu işlem adımını oldukça azaltan bir faktördür. (çarpıldığında tersi olur tabii)

Algoritma Karmaşıklığı ne kadar düşükse o kadar iyidir. Program hızlı çalışır demektir.

 

Birden Fazla döngü var ve iç içe değilse

Eğer bir yazılımda birden fazla döngü var ve bu döngüler iç içe değilse algoritma karmaşıklığını hesaplamak için bu döngülerin karmaşıklıkları toplanır.

.

   for (int i = 1; i <=m; i += c) {  
        
   }
   for (int i = 1; i <=n; i += c) {
        
   }

Yukarıdaki Döngülerin karmaşıklıkları O(m) + O(n)’dir yani O(m+n) olur. (döngülerin dönme sayısılarına dikkat edin.

3 comments

  1. Merhaba öncelikle verdiğiniz bilgiler çok açıklayıcı ve güzel olmuş bu bakımdan teşekkürlerimi belirtmek isterim.
    Ayrıca benim size sormak istediğim bir soru var?

    for(int i=1; i^2<=N;i=2*i)

    Hoca böyle bir soru verdi ama anlayamadım.Rica etmek siz de bi bakar mısınız?Merak ettim nasıl yapılabilir acaba?

    • algoritmauzmani

      soru derken for döngüsünün işleyişini mi anlamak istediniz? i = 1 için başlıycaz, ancak her adımda i = 2 üzeri i olacak, temel şart da i^2 değerinin N sayısından küçük olması yani
      i = 1 den sonra i = 2
      i = 2 den sonra i = 4
      i = 4’den sonra i = 8
      öylece gidiyor, tabii N değerimiz kaç onu bilmediğim için bu şekilde yazıyorum.

      Pardon 2 çarpı i imiş yanlış okumuşum. i leri tekrar güncelledim.

  2. Örnekler gayet güzel ama biraz daha komplex örnekler verirseniz daha da zenginleşir makaleniz . Logn üzerine bir kaç örnekde olsaydı güzel olurdu ama bu bilgiler bile gayet güzel .Teşekkürler

Harun için bir cevap yazın Cevabı iptal et

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