BigO Notasyonu ve Kısaca Algoritma Maliyet Hesabı

“Program yazmak zor değil, kaliteli ve basit program yazmak zor” diyerek konuya direk giriyorum. 😊
B️ir programda veya algoritmada en önemli şeylerden biridir zaman. En önemlisidir demiyorum çünkü ondan da önemli olan şeyler var. Örn. doğruluk gibi. Algoritma doğru sonucu vermezse isterse 1 saniyede çalışsın isterse 10 saniyede.

Bugün algoritma analizini herkesin anlayabileceği şekilde basit örnekler üzerinden anlatmaya çalışacağım. Öncelikle algoritma analizinde en çok kullanılan yöntem BigO notasyonu, bir diğer adıyla en kötü durum senaryosu.
En çok kullanılan BigO terimleri performans sırası ile;

  • O(1) -> Constant

Bugün bu terimlerden O(1),O(n),O(LogN),O(n²),O(n!) terimlerine değineceğim ancak bu terimlerin ne oldukları doğrudan anlatmak yerine örnekler üzerinden algoritma analizi nasıl hesaplanıyor, aynı algoritma nasıl daha performanslı çalışan bir terime çevirilebilir kısaca anlatacağım.

Öncelikle bir sayının üssünü alma fonksiyonu yazdığımızı düşünelim. Örneğin fonksiyona a ve b parametreleri verdiğimiz zaman fonksiyon bize a üssü b yi döndürsün.

Gördüğünüz gibi a sayısını b kere çarpan bir fonksiyon yazdık. Yani istediğimiz sonucu aldık. Peki bu fonksiyona 3.0000.000 , 10.000.000 gibi yüksek değerler versek zaman maliyeti ne kadar olur?

İşte algoritma analizi bunun için var, herhangi bir donanım veya başka bir teknolojiyi hesaba katmadan bize ne kadar zaman harcatıyor hesaplayabiliyoruz. Buradaki zaman saniye cinsinden değil işlem sayısı cinsindendir.

Şimdi bize yukarıda yazdığımız fonksiyonun maliyeti ne kadar onu hesaplayalım.

  • 2 Numaralı Satır : 1 (Sabit değerler hesaba katılmaz ancak anlamanız için yazıyorum)

Algoritma analizi yaparken sabit değerler hesaba katılmaz.
Buna göre sonuc bize b olarak geliyor. Bunun BigO notasyondaki karşılığı O(n) dir. O(n) demek n kadar maliyeti vardır demek. Örn. bir dizi düşünün [1,2,3] olarak gidiyor n e kadar. Bu dizinin tüm elemanlarını ekrana yazdırıyorsunuz. N tane işlem oluyor bu.

Şimdi bizim algoritmamızın maliyeti O(n) oldu. Biz bu algoritmayı daha hızlı hale getirebilmek için ya O(LogN) yada O(1) e çevirmemiz gerekiyor.

O(1) in sabit sayıda maliyeti vardır. Örn. bir dizi düşünün [1,2,3] olarak gidiyor n e kadar. Bu dizinin ilk elemanını ekrana yazdırıyorsunuz. 1 tane işlem olur, eleman sayısı ne kadar artarsa artsın bize maliyeti 1 dir.

O(LogN) ise problemi ikiyi böle böle gitme yöntemi gibi düşünebiliriz. Örn. bir dizi düşünün [1,2,3,4,5,6,7,8,9,10,…,20]. Bizden dizide bir eleman arayan bir algoritma yazmamız istenmiş olsun. Örn. 5 sayısını arayalım. İlk adım olarak diziyi ikiye bölelim. Elimizde sol ve sağ olarak iki dizi oluştu. Şimdi aradığımız sayı sol dizi de mi yoksa sağ dizide mi bakalım. Sol dizide olduğunu bulduktan sonra sağ diziyi kaldırdık. Aynı şekilde şimdi soldaki diziyi ikiye bölelim. Tekrar elimizde sol ve sağ olmak üzere iki yeni dizi oluştu. Bu şekilde 5 sayısını bulana kadar 2 ye bölme işlemine devam ederiz. Her adımda 2 ye bölerek maliyetimizi yarı azaltmış oluruz. Şimdi bunu bir de kod üzerinden anlatayım.
Yukarıdaki üs alma fonksiyonumuzu O(n) den O(LogN) e çevirelim.

Yukardaki işlemi matematiksel olarak size kısaca anlatayım.Diyelim ki bizim a değerimiz 2, b değerimiz 100 olsun. Bunun matematiksel karşılığı 2*2*2*…*2. Biz bunu ilk algoritmamızda zaten yaptık ve hızlandırmak istedik. Bunu hızlandırmak için yukarıdaki algoritmada öncelikle (2⁵⁰)*(2⁵⁰) olarak böldük. Daha sonra (2²⁵*2²⁵)*(2²⁵*2²⁵) olarak 2 ye parçalaya parçalaya devam ettik işlem sonuna kadar. İşlem tamamlandıktan sonra yeni algoritmamızın bize maliyeti O(LogN) oldu. Bu şekilde O(n) den O(LogN) e çevirerek bir performans artışı sağlamış olduk.

Diğer terimlere bakacak olursak.

O(n²) terimi girdi ne ise onun karesi kadar maliyeti vardır. Örneğin bir diziyi sıralama algoritması gibi. Kısaca içi içi for döngüsüde buna örnektir.
O(n!) terimi ise en kötü senaryolardan birisidir. Girdi ne olursa olsun maliyet girdinin faktöriyeli kadardır. Örn. 10 input ise maliyeti 3.628.800 dür.

Umarım herkes için faydalı bir içerik olmuştur. ️😊 😊

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store