Big O notation Nedir ve Örnekler

Big O notation, bilgisayar bilimlerinde algoritmanın performans ve karmaşıklık düzeyini tanımlar. Big O özellikle bir algoritma için olabilecek en kötü senaryo da çalışması için gerekli süre veya kullanılan space(ramde veya diskte)’i tanımlar.

O(1)

Yazılan algoritmanın her zaman için aynı sürede çalıştırılacağını(veya space kullanacağını) ve gönderilen input parametresinden çalışma süresi(veya space kulanımı) bakımından etkilenmediğini belirtmektedir.Aşağıda belirtilmiş olan algoritmanın karmaşıklığı O(1)dir.

bool IsFirstElementNull(IList<string> elements)
{
return elements[0] == null;
}

O(N)

Yazılan algoritmanın performansı lineer olarak veya direkt olarak input olarak verilen değişkene bağlı olduğu anlamına gelmektedir.Aşağıdaki kod örneğine bakılacak olunursa eğer aranan eleman listenin ilk elemanı ise en iyi durum ortaya çıkacaktır yani listenin sadece 1 elemanı karşılaştırılarak eleman bulunmuştur fakat Big O Notation en kötü duruma göre değerlendirme yapmaktadır.Aradığımız eleman listedeki son eleman olabilir ve bütün listeyi karşılaştırmamız gerekmektedir.Listenin uzunluğunu N olarak düşünürsek N’nin büyüklüğüne göre algoritma mızın çalışma hızı değişecektir ve en kötü durumda N kadar elemanı karşılaştırma yapması gerekmektedir.

bool ContainsValue(IList<string> elements, string value)
{
foreach (var element in elements)
{
if (element == value) return true;
}

return false;
}

O(N²)

O(N²) Yazılan algoritmanın karmaşıklık ve performans olarak verilen input’un karesine bağlı olduğunu anlamını taşımaktadır.Bu algoritma karşılıklılığı örneği genellikle iç içe verilmiş iteration'(döngü)’lerde görülmektedir.İç içe daha fazla iteration(döngü) yazılır ise bize sonuç olarak O(N³), O(N⁴)’ leri vermektedir. Aşağıda iç içe 2 tane for kullanılarak yazılmış O(N²) için verilen örneği görmektesiniz:Eğer iç içe 3 tane for yazarsanız yine bahsedildiği üzere  O(N³) ortaya çıkacaktır.

bool ContainsDuplicates(IList<string> elements)
{
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

 

O(2^N)

O(N²) Algoritmanın her bir ekleme ile  algoritma karşılıklılığı iki katı kadar büyüyen algoritmalar dır. Bu tür algoritmaların inputlarındaki eleman sayısı sığ olarak başlar ve üstel olarak yükselmektedir.Rekürsif Fibonacci sayılarının hesaplanması buna uymaktadır.

int Fibonacci(int number)
{
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

O(log N)

Logaritmik algoritma karmaşıklığından birisidir buna en iyi örnek binary search’dür. Eğer input’daki elaman sayınız 10 ve çalışma süresi 1 saniye ise buradan yola çıkarak eleman sayınız 100 olduğunda çalışma süresi 2, eleman sayınız 1000 olduğunda ise çalışma süresi 3 olmaktadır, ikiye katlamak bu algoritmada çok hız farkı yarat masada üstel artışlar ancak gözle görülür farklar yaratmaktadır.

Kaynak https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/