Big O Notation Nedir? Büyük O Notasyou Nedir? | O(n) O(log n) O(1)

Big O notation, nam-ı diğer Büyük O notasyonu herhangi bir algoritmanın karmaşıklık düzeyini (time complexity / complexity level) açıklamamıza yardımcı olur. Bu sayede benzer algoritmaları zaman ve performans bakımından birbiriyle kıyaslayabilir ve projemiz için hangisinin daha maliyetli veya daha uygun olduğunu saptayabiliriz.

Big O gösterilirken O(x) tarzında yazılırak gösterilir. Aşağıdaki örneklerde x yerine neler yazıldığını ve yazılanların ne anlam ifade ettiğini göreceğiz.

Ek olarak bilinmesi gerekir, Big O gösterimi en kötü (worst case) senaryoyu temsil eder. Big O dışında Omega (best case) yani en iyi senaryo ve Theta (mid case) yani orta seviye senaryo gibi başlıkları inceleyebilirsiniz. Ayrıca bu gösterimlerden önce veri yapıları hakkında bilgi sahibi olmanızda da yarar vardır.

O(1) | Constant Time

Her çalıştığında aynı miktarda zaman alan kod parçaları O(1) şeklinde gösterilir. Kabaca, yapılacak işlem başka bir şeye bağlı olmadığında karmaşıklık düzeyi O(1) olur diyebiliriz.

Bağımlı durumların neler olduğunu bir sonraki başlıkta inceleyeceğiz. Ancak öncesinde bu başlığa örnekler verelim.

Örneğin bir değişkene değer atadığımızda karmaşıklık düzeyi O(1) olur, çünkü bu işlemin herhangi bir bağımlılığı yok.

Benzer şekilde elimizde bir dizi olsun ve bu diziden herhangi bir değere erişmek isteyelim. Bu da O(1) düzeyinde gerçekleşir.

Big O gösteriminde O(1) olası en iyi durumdur. 

O(n) | Linear time complexity

Bir kod parçacığının tamamlanma süresi ile girdi sayısının birbirine orantılı olma durumudur.

Kod parçacığı örneğinden önce elle tutulur bir örnek vermek istiyorum. Diyelimki elinize aldığınız sözlükte bir kelime arayacaksınız ve kuralımız şu (kural saçma gelmesin, array örneğinde bu kuralın nedenini anlayacaksınız); aradığınız kelime Z harfinde bile olsa ilgili kelimeyi aramaya en baştan başlamak zorundasınız. İşte böyle bir durumda, yani geçen süre ile aradığımız kelimenin uzaklığının birbirine orantılı olduğu durumlarda O(n) complexity söz konudur.

Peki bu nasıl olabilir? Örneğin aradığınız kelime A harfindeyse geçen süre 1 dakika olsun. Z harfindeyse geçen süre 29 dakika olsun. Bu tarz bir durumda linear bir durum gerçekleşir.

Şimdi bunu bir kod parçacığı üzerinde inceleyelim.

Bu örnek üzerinde de görebileceğiniz gibi kod parçacığının tamamlanma süresi farzımuhal 1 dakika da sürebilir 10 dakika da... Çünkü yukarıdaki örneğe göre aradığımız sayı array'in başında da olabilir sonunda da. Yani bu döngü içerisinde geçen süre aradığımız input'a göre her defasında değişebilir. Bu yüzden söz konusu complexity level O(n) dir.

Big O gösteriminde şu ana kadar incelidiğimiz başlıklar için complexity level aşağıdaki gibi sıralanır.

O(n) > O(1)

O(log n) | Logarithmic time complexity

Bir kod parçacığının tamamlanma süresi girdi sayısının logaritmasına bağlı olma durumudur.

En bilinen örneği binary search algoritmasıdır. Binary search algoritmasını kısaca açıklayacak olursak; sıralanmış bir dizide X elemanını ararken öncelikle dizinin ortasındaki elemana bakıyoruz. Eğer aradığımız eleman daha büyükse dizinin yarısını incelemiş oluyoruz. Artık sadece diğer yarısıyla ilgileniyoruz. Bu şekilde devam ederek istediğimiz elemana ulaşana kadar aynı işlemleri tekrarlıyoruz.

Örneğin sıralanmış 100 elemanlı dizide 64'üncü elemana erişmek istediğinizde tek tek 64 işlem de yapabilirsiniz ancak logaritmik karmaşıklık düzeyinde bu işlem sayısını 3'e de düşürebilirsiniz.

Linear olarak taradığımızda gerçekleşen işlem yukarıdaki gibi olur.

Logaritmik (binary search ile) taradığımızda gerçekleşen işlem yukarıdaki gibi olur.
Küçük not: ondalıklı sayıları yukarı yuvarladık.

Big O gösteriminde şu ana kadar incelidiğimiz başlıklar için complexity level aşağıdaki gibi sıralanır.

O(n) > O(log n) > O(1)

O(n2) | Quadratic time complexity

Bir kod parçacığının tamamlanma süresinin girdi sayısının karesiyle orantılı olma durumudur. En bilinen örneği iki for döngüsünün iç içe kullanılmasıdır.

Örneğin bir dizide tekrar eden sayılar var mı diye merak ettiniz. Bunun için de dizinin i'ninci elemanına bakarken bu elemanı dizinin geri kalan tüm elemanlarıyla karşılaştırdığınız durumda O(n2) karmaşılık düzeyi gerçekleşir.

Big O gösteriminde şu ana kadar incelidiğimiz başlıklar için complexity level aşağıdaki gibi sıralanır.

O(n2) > O(n) > O(log n) > O(1)

Elbette bu başlıklar dışında sayabileceğimiz bir çok Big O gösterimi var. O(n!) veya O(n log n) bunlardan bazıları.

Kaynak önerisi:

Veri yapıları ve algoritmalar ile birlikte Big O hakkında da bilgi edinebileceğiniz güzel bir oynatma listesi: YouTube - Uğurcan Çetin