Back To Basics -> Big O Notasyonu

Bilgisayar mühendisliği bölümünü bitireli epey bir zaman geçtiği için bazen temel olarak aldığım ders konularını tamamen geride bırakmış, hatta zamanında onlara gereken değeri vermemiş olduğumu hissediyorum.

Öğrenciyken, “bu bilgi şimdi ne işimize yarayacak” sorusunu çok fazla sormuşluğum vardır. Kendi adıma konuşmam gerekirse bir konuyu (kavramı) pratikte kullanmadıkça o konu benim için bir teori olarak bilinçaltında bir yerde saklı kalıyor. Fakat çalıştığım ve birşeyler ürettiğimden beri mantalite olarak özellikle temel konulara çok fazla önem veriyorum ve bu konulara unuttukça geri dönmek (Back to Basics konsepti) çok hoşuma gidiyor. Mühendisliği hakkını vererek yapmanın, bu adımı da içerdiğini düşünüyorum.

Bu yazının konusu olan Big O kavramı da müfretada göre değişkenlik gösterecek şekilde, Veri yapıları, Algoritma, Programlamaya giriş veya Ayrık Matematik derslerinde anlatılıyor ve Bilgisayar Mühendisliğinin de en temel konularından bir tanesidir.

Tanım olarak Big O aslında yazdığımız algoritmaların performansını veya karmaşıklığını hesaplamada kullanılan bir yöntemdir. Bu notasyonu ele almaktaki amacımız bir çalışma süresinin büyümesini asimptotik olarak sınırlamaktır. Asimptotik darken neyi kastediyoruz, biraz bu kavramı detaylandıralım.

Asimptotik, matematikte fonksyonların limiti için kullanılan bir metottur. Mesela, f(n) gibi bir fonksiyonun n’in çok büyük değerleri için davranışıdır.

Asimptotik analiz, bir algoritmanın çalışma performansının (runtime performance) sınırlarını matematiksel olarak belirlemek için kullanılan bir yöntemdir. Algoritma adımlarının çalışması için gerekli sürenin (time complexity) alt ve üst sınırlarının matematiksel olarak ifade edilmesini sağlar.

Bir program çalıştığında küçük girdiler (n) için kaynak kullanımı kritik değildir. Genelde karmaşıklığın n’ler büyüdükçe (n sonsuza giderkenki) analizi ilgili programın asimptotik davranışıdır. Big O notasyonu ile de bu asipmptotik davranışı ve karmaşıklığı ifade ediyoruz.

Big O natasyonu, bize girdiler büyüdükçe bir algoritmanın complexity’sinin (time complexity, algorithmic complexity, asymptotic complexity) ne kadar büyüdüğü hakkında fikirler verir.

Big O mantığında da şu beklenti yer alır :

Bilgisayarın yapması gereken basit işlemlerin sayısı, n arttıkça c * f(n)’den az ise algoritmanın O (f(n)) bu fonksyonun Big O ‘sudur.

• f(n) linear fonksyon olabilir -> f(n) = n -> O(N)

• f(n) quadratic olabilir -> f(n) = n² -> O(N²)

• f(n) constant olabilir -> f(n) = 1 -> O(1)

O(f(n)) ile diyoruz ki; n büyüdükçe işlem sayısı ve harcadığ zaman da fonskyonun tipi doğrultusunda büyüyecektir .

Big-O gösterimi, verileri büyüdükçe kodun nasıl davrandığını anlamanın bir yoludur.

Notasyonda kullandığımız O harfi “order of” ’dan geliyor; yani çalışma zamanını bir şeyin "Sırasına göre" olarak tanımladığı için kullanılıyor. Bu, bir matematikçinin iki şeyin benzer şekilde büyüdüğünü söyleme şeklidir.

N; datanın büyüklüğünü ifade ediyor. O(N) (order of N) ise çalışma süresinin N doğrultusunda olduğu veya N'nin büyüdüğü şekilde büyüdüğü anlamına gelir.

Mesela bir algoritma O(N) ise bu, çalıştırılacak işlem sayısının N ile orantılı olduğu anlamına gelir. Yani 100 kat daha fazla veri verilirse çalışma zamanı 100 kat artacaktır.

Eğer O(N²) ise adım sayısı N² ile orantılı demektir. Yani 10 kat daha fazla veri üzerinde çalışması 100 kat daha uzun sürecektir.

O(1) ise çalışma süresinin N’e bağlı olmadığı anlamına gelir. Ne kadar veri olursa olsun çalışma süresi sabittir.

Biraz daha somut olabilecek örnekler üzerinden devam edelim.

Diyelim ki bir metot geliştireceğiz ve birden fazla algoritma seçeneğimiz olsun. Hangisinin daha iyi olduğunu nasıl anlayacağız?

Hatta bu sorudan önce neden böyle bir karşılaştırmaya gerek duyarız, onun cevabını alalım :

• Farklı yaklaşımlardaki trade-off’ları gözlemleyebiliriz.

• Kodumuz belli bir noktadan sonra yavaşladığnda veya bozulduğunda efektif olmayan kısımları tespit etmek gerekecektir.

Metot geliştirme aşamasına geri dönecek olursak, örneğin 1’den n’e kadar olan sayıların toplamını hesaplayıp döndüren metodu 2 farklı algoritma yaklaşımı ile geliştiriyor olalım.

Yaklaşım 1 :

Yaklaşım 2 :

Şimdi hangi yaklaşımın daha iyi olduğunu araştıralım. Burada “iyi” den kasıt tam olarak nedir peki?

• Daha hızlı çalışması (Time complexity konusu)

• Daha az memory harcaması (Space complexity konusu)

Daha hızlı çalışması açısına odaklanacak olursak eğer hesaplamamız gereken şey bilgisayarın kaç adet işlem yapacağıdır. Time complexity dediğimiz kavram da bu aslında.

Yukarıdaki 2 yaklaşımı bu yönden karşılaştıracak olursak, 2. yaklaşımın daha yalın olduğunu söyleyebiliriz. Oradaki kodda sırasıyla 1 çarpma , 1 toplama bir de bölme işlemi olduğunu görüyoruz. n’in ne kadar büyüklükte bir veri olduğunun hiç bir önemi yok.

n 100000000 de olsa, 10 da olsa 2. yaklaşımda bilgisayara 3 adet işlem yaptırıyoruz.

Fakat 1. Yaklaşıma baktığımızda bir adet for döngüsü var ve bu döngü n’in değerine bağlı olarak karmaşıklık seviyesini artıracaktır.

2. kod bloğunda n ne kadar büyük olursa olsun hep 3 adet işlem vardı. Dolayısıyla bu durum O(1) dir.

Fakat 1. kod bloğunda n’e göre durum değişmekteydi. Bu durumu da O(N) olarak belirliyoruz.

Bir örnek kod bloğu daha yapalım;

Bu algoritmada iç içe döngü olduğunu görüyoruz. Yani O(n) içinde O(n) işlem var. O zaman bu algoritmanın Big O notasyonunu da O(N²) dir.

Bir algoritmanın time complexity’sine karar verirken bazı kurallar vardır :

- Sabitler önemli değildir. Örneğin;

O(2N) aslında O(N) dir. O(200) -> O(1) dir. O(50N²)->O(N²) dir.

- Küçük terimler önemli değildir ;

O(N+50) -> O(N) dir. O(100N+20) -> O(N) dir.

Big O notasyona direkt karar verbileceğimiz kısa yollar da vardır :

• Aritmetik işlemler sabittir. Bu işlemlerde n’in ne olduğu önemli olmadığı için direkt O(1) diyebiliriz.

• Değişken atamaları da sabittir.

• Dizi – koleksiyon elemanlarına (index veya key ile)erişim işlemleri de sabittir.

• Eğer bir döngü söz konusu ise döngünün içerisinde ne yapılıyor olursa olsun, karmaşıklık n e bağlıdır. (O(N)).

Diğer çok karşılaşılan Big O notasyonları karşmaşıklık seviyesi düşükten yükseğe doğru şu şekilde ;

O(1) – O(logN) – O(N) – O(n.logn) - O(N²) – O(N³) – O(N!)

Özetle, aslında yaptığımız işlem, bir algoritmanın en kötü senaryoyu hesaplayarak ne kadar işlemden geçeceğini hesaplamaktır.

Hangi algoritmayı seçeceğimize karar verirken mesela n=10 iken A algoritması daha iyi olabilir fakat n=10000 iken olmayabilir. Big O mantığında her zaman sonsuza giden sayılar dahilinde sorgulama yapmalıyız.

Yani bizim için önemli olan kriter çok büyük sayılar olmalıdır.