• Anasayfa
  • Eğitimler
    • JavaScript Eğitimi
    • Angular 2 Eğitimi
    • React.js Eğitimi
    • Java 8 Eğitimi
    • Java EE 7 Eğitimi
    • Spring Framework Eğitimi
    • Git Eğitimi
  • Online Eğitimler
    • Online React.js Eğitimi
    • Online Angular 2 Eğitimi
    • Online Spring Boot Eğitimi
  • Referanslar
  • Hakkında
  • İletişim
KodEdu
  • Anasayfa
  • Eğitimler
    • JavaScript Eğitimi
    • Angular 2 Eğitimi
    • React.js Eğitimi
    • Java 8 Eğitimi
    • Java EE 7 Eğitimi
    • Spring Framework Eğitimi
    • Git Eğitimi
  • Online Eğitimler
    • Online React.js Eğitimi
    • Online Angular 2 Eğitimi
    • Online Spring Boot Eğitimi
  • Referanslar
  • Hakkında
  • İletişim

Java Collection API ve Big O Notasyonu

  • Posted by Kodedu
  • Categories backend, Genel, Uncategorized, Verimlilik, Yazılım
  • Date 19 Ağustos 2014

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(n2) : 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(n2) sonucuna varılır. Yine, iç içe üç döngü için zaman kompleksitesi  O(n3) olacaktır, çünkü n*n*n’ bağlıdır, gibi..

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

O(n2) ‘den daha ağır durumlar da olabilir, O(n!) ve O(cn) 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…

  • Share:
author avatar
Kodedu

Previous post

Zencoding (Emmet) ile Hızlı kod yazın
19 Ağustos 2014

Next post

YAML Nedir? Neden YAML Kullanmalıyız?
31 Ağustos 2014

You may also like

api-logo
Swagger Nedir? Neden kullanılır?
10 Ekim, 2018
spring-cli-logo
Spring CLI ile Spring Boot Projeleri Hazırlamak
21 Ağustos, 2017
eureka_architecture
Spring Cloud Netflix ve Eureka Service Discovery
3 Temmuz, 2017

Leave A Reply Cevabı iptal et

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

E-posta listesine kayıt olun!






Gözde yazılar

Netmera ile Röportaj
18Haz2012
Spring CLI ile Spring Boot Projeleri Hazırlamak
21Ağu2017
Performans, Yük ve Stres Testleri
26Ağu2012
CDI – @Produces, @New ve @PostConstruct Notasyonları
22Tem2013

Son Yazılar

  • Java’da Record’lar 27 Ocak 2020
  • Swagger Nedir? Neden kullanılır? 10 Ekim 2018
  • Spring CLI ile Spring Boot Projeleri Hazırlamak 21 Ağustos 2017
  • Spring Cloud Netflix ve Eureka Service Discovery 3 Temmuz 2017
  • Online React.js Eğitimi ardından (15-25 Mayıs 2017) 31 Mayıs 2017

Son Yorumlar

  • Coupling ve Cohesion Kavramları Nedir? için Hilal
  • Naïve Bayes Sınıflandırma Algoritması için Rahman Usta
  • Naïve Bayes Sınıflandırma Algoritması için Mete
  • YAML Nedir? Neden YAML Kullanmalıyız? için kara
  • JWT (JSON Web Tokens) Nedir? Ne işe yarar? için Furkan

Get Java Software

Arşivler

Bizi takip edin

React.js Eğitimi Başlıyor
11-22 Eylül, 2017
Eğitmen
Rahman Usta
İletişim

merhaba@kodedu.com

  • Hakkında
  • Gizlilik Politikası
  • İletişim
  • Referanslar
Kodedu Bilişim Danışmanlık
Cemil Meriç mah. Çelebi sok.
No:16/3 Ümraniye/İSTANBUL
Tel: 0850 885 38 65
Alemdağ V.D.: 8960484815

KODEDU © Tüm hakları saklıdır.