Java Collection API ve Big O Notasyonu

Big O notasyonu, programlama dünyasında, algoritma ve program parçalarının kıyaslanması amacıyla tanımlanan bir zaman kompleksliği açıklama biçimidir.

Big O ile, kendi yazdığınız kod parçaları, sık kullanılan algoritmalar (Örn: merge sort, heap sort ) veya çeşitli veriyapılarına dair işlevsel operasyonlar (Örn: LinkedList,ArrayList, HashMap … gibi veri yapısına veri ekleme, silme, bulma) Big O notasyonu üzerinden kıyaslanabilmektedir.

Big O ile gösterim yapılırken, koşturulacak iş veya iş kümesinin girdi sayısına göre (bu “n” olarak temsil edilir) bağımlılığı göze alınmaktadır. “n” sayısına göre aldığı zaman göze alınarak bir değerlendirme yapılmaktadır.

O(1) : Sabit zaman / Constant time

Girdi sayısına yani “n” ‘ e bağlı olmayan işlerdir. Sabit zamanlı gösterim izah edilirken genel olarak atama operasyonları ile örneklenmektedir.

String mesaj = "kodedu.com";

Yukarıdaki atama operasyonu örneğin, Big O çerçevesinde O(1) olarak değerlendirilir. O(1) Big O çerçevesinde olası en iyi kıyas birimidir. Çünkü en az zamanı o alır.

O(n) : Lineer

Koşturulacak operasyonun alacağı zaman eğer girdi sayısına bağlı olarak lineer olarak değişecekse, bu O(n) olarak değerlendirilir. Bunun meali, operasyonun alacağı zaman n’e bağlıdır olacaktır. O(n) değerlendirmesine örnek için, döngü yapısı biçilmiş kaftandır.

for(int i = 0; i < n ; n++ ){

  mesaj = "Mesaj " + i;

}

Burada döngü içerisindeki atama operasyonun alacağı zaman O(1) dir. Fakat bu operasyon döngüdeki girdi sayısına bağlı olarak n kere tekrar edeceği için, alacağı zaman n’e bağlıdır denir. Bu yüzden zaman kompleksliği burada O(n) dir. O(n) > O(1) dir çünkü girdi boyutuna bağlı olduğu için daha fazla zaman alacağı kabul edilir.

O(log n) : Logaritmik

Burada girdi ve alacağı zaman logaritmik olarak ilerler. O(n)’e göre daha az zaman alacağı kabul edilir. Örnek olarak girdi sayısı olarak n = 100 düşünülürse, O(n) için zaman kompleksliği 100’e bağlı olacaktır.  log 100 = 2 olacağı için , O (log n) burada 2’ye bağlı olacaktır. Bu sebeple O(n) > O(log n) > O(1)’ dir.

O(log n) için ideal örnek binary search algoritmasıdır. binary search algoritmasında dizi elemanları sıralı olduğu için, arama operasyonu her denemede kalan eleman sayısının yarısı kadar elenecektir. Bu sebeple binary search için O (log n) denilebilir.

O(n log n) : Doğrusal Logaritmik

Bir önceki örnek üzerinden girdi sayısı olarak n = 100 düşünülürse, O(n) için zaman kompleksliği 100’e bağlı olacaktır.  log 100 = 2 olacağı için , O (n log n) burada 100* 2 = 200’e bağlı olacaktır. Bu sebeple O(n log n) > O (n) > O(log n) > O(1) dir.

O(n²) : Karesel

Operasyon/ algoritma’ nın zaman kompleksliği n*n’e bağlı olan durumlarda geçerlidir. Örneğin iç içe iki döngü operasyonun alacağı zaman n kere n kadardır. yani n*n’e bağlıdır. Bu yüzden O(n²) sonucuna varılır. Yine, iç içe üç döngü için zaman kompleksitesi  O(n³) olacaktır, çünkü n*n*n’ bağlıdır, gibi..

Yeni kıyaslama şu biçimdedir. O(n²) > O(n log n) > O(n) > O(log n) > O(1)

O(n²) ‘den daha ağır durumlar da olabilir, O(n!) ve O(cⁿ) gibi.

Big O ve Eleme

Bir kod parçasının Big O analizi yapılırken tek tek Big O çıktıları hesaplanır ve en son sadeleştirmeye gidilir. Çünkü Big O çerçevesinde zaman kompleksliği olarak en büyük çıktı sonuç olarak kabul edilir. Katsayılardan ve diğer küçük Big O çıktılarından feragat edilir.

Örneğin;

3*O(n) + O(1) denktir O(n)

O(n) + 6*O(1) denktir O(n)

2*O(n log n) + 9*O(n) + 5*O(1) denktir O (n log n)

O(n log n) + 999*O(n) + 545*O(1) denktir  O (n log n)

Analizini Yapalım

Aşağıda yer alan kod parçasının Big O gösterimi ise, O(n)’dir. Ara sonuçlar matematiksel olarak birbirine eklenir ve eleme yapılarak sonuca ulaşılır.

for(i = 0 ; i< 10 ; i++ ){

 mesaj = "Merhaba" + i; // n kere O(1)

}

// Ara sonuç:  O(n)

mesaj = "Merhaba Uranüs"; // O(1)
int x = 10; // O(1)

// Ara sonuç: O(n) + 2*O(1)
 
for(i = 0 ; i< 25 ; i++ ){

 mesaj = "Merhaba"; // O(1)
 mesaj = "dünyalı" + i; // O(1)

 // n kere 2*O(1)

}

// Ara sonuç: O(n) + 2*O(1) + 2*O(n)
// Ara sonuç: 3*O(n) + 2*O(1)
// Sonuç: O(n)

Big O’ya ne zaman ihtiyaç duyabiliriz?

Hemen hemen her programlama dilinde çeşitli veri yapıları yer almaktadır. Bu veri yapıları üzerindeki operasyonlarda Big O ile yapılan kıyaslamaları incelemek, hangi durumda hangi veri yapısının tercih edileceği hususunda geliştiricilere fayda sağlamaktadır.

Big O ve Java Collection API

Java ekosisteminde Collection ve Map arayüzünden türeyen veri yapıları kısaca Collection API olarak değerlendirilmektedir. İyi bir Java geliştiricisi,  bu veri yapılarını, davranışlarını, birbirleri arasındaki kıyası iyi bilmelidir. Kıyasların yer aldığı tabloya buradan erişebilirsiniz.

Referanslar

[1] http://bigocheatsheet.com

[2] http://javadevelopersenior.com/blog/wp-content/uploads/2013/05/java_collections.pdf

[3] http://www.javacodegeeks.com/2011/04/simple-big-o-notation-post.html

[4] http://tr.wikipedia.org/wiki/B%C3%BCy%C3%BCk_O_g%C3%B6sterimi

Tekrar görüşmek dileğiyle…