Performans
Algoritma Karmaşıklığı (Big-O)
Yazdığınız bir Algoritmanın karmaşıklık analizini yapıyor olmanız, veri yapılarınızdaki verinizin büyüdüğü, veya farklı farklı ortamlarda düşük güçlü veya bellekli makinalarda çalışırken oluşacak durumları daha önceden analiz edebilmenizi sağlar.
Algoritma sizin bir problemi çözmek, bir görevi yaptırmak için yazdığınız arka arkaya çalışan komutlar dizisidir. Bir problemi veya görevi farklı farklı algoritmalar yazarak çözebiliriz ama bu çözümlerin duruma göre avantajları ve dezavantajları olur. Örneğin hızlı çalışan bir algoritma yazabilmek için daha fazla belleğe ihtiyaç duyarız veya bellek alanımız az ise daha uzun zamanda işimizi görecek bir algoritmada yazabiliriz. Sonuçta yapılacak işleme göre en uygun algoritmayı yazmayı nasıl başaracağız bunun için kıstas nedir.
Algoritma karşılaştırmasında 2 temel kıstas üzerinden değerlendirme yapılır;
- Süre Karmaşıklığı
- Bellek Alan Karmaşıklığı
Zaman karmaşıklığı bir algoritmanın girdi ile çıktı arasında geçen zamanı hesaplarken , diğeride harcanan bellek alanını hesaplar. Veri büyüdükçe bu zaman ve belleğin nasıl değiştiğini analiz eder.
Bunu hesaplar biz yazılımcılar genelde en kötü duruma/senaryoya göre (Worst case) durumu değerlendiririz. Bu zaman karmaşıklığı ölçümü için Big-O gösterimi tercih edilir. Ortalama süre için Θ Theate Notasyonu, en iyi süre için Ω Omega notasyonu kullanılır.
Biz aşağıdaki Big-O Karmaşıklığını üzerinden durumu anlatmaya çalışacağız.
Problemleri çözmek için farklı veri yapılarına ihtiyaç duyarız. Örneğin (Array, LinkedList, Queue, Stack, Binary Tree, Graph). Veya aynı veri yapısı üzerinde Array üzerinde sıralama için farklı farklı algoritmalar çalıştırabilirsiniz Örneğin (Bubble Sort, Insertion Sort, Quick Sort, Heap Sort, Merge Sort) . tüm bu seçimlerimizin kodumuzun kalitesine, hızına, kullanışlılığına ve tükettiği kaynaklar yönünden sonuçları olur. Bundan dolayı yazılım geliştiricilerin bu konuyu iyi bir şekilde idrak etmesi önemlidir.
1. Constant Complexity (Sabit)
Aşağıdaki örnekte n 1 veya 1000 gelsede yapılan işlem sayısı sabittir.
Not: Yani O(1) .Dikkat ederseniz burada yapılan işlem sayı toplamı ile değilde girdi değişkeninin süre üzerindeki etkisini analiz ediyoruz
const constantOp=n=>console.log(n)2. Logarithmic Complexity
Girdi değer yani n değeri çok büyüsede algoritma giderek bu sayıya göre daha az sürede işlemi bitirdiği algoritma türlerine denir. Örneğin aşağıdaki örnekte 4 değeri için → 2 işlem yaparken , 32 için → 5, 1024 değeri için → 10 işlem yapacaktır. 1024 sayısına 100 eklesemde işlem sayısı çok artmayacaktır. O(log n)
const logarithmicOp=n => {for(let i=n;i>1;i/=2) console.log(i)}3. Linear Complexity
Girdi değerimiz ne kadar ise süre doğru orantılı olarak artar. O(n) 5 girdi için 10 işlem yapıyorsak , 15 girdi için 30 işlem yapılacaktır.
const linearOp=n=> {for(let i=0;i<n;i++) console.log(i)};4. Quadratic Complexity
Örneğin iç içe 2 tane for döngüsü olduğunu düşünelim. Bu durumda verdiğimiz n girdi için n*n karesi kadar işlem yapılacaktır. 3 girdi için → 9 işlem yapılırken, 5 olduğunda işlem sayısı → 25 olacaktır. O(n2)
const quadraticOp =n=> {for(let i=0;i<n;i++)
for(let j=0;j<n;j++) console.log(i) }5. Cubic Complexity
Bu iç içe döngüler 3'e çıktığında Cubic Complexity çıkmış olur. O(n3) Bu iç içe döngüleri ne kadar çok arttırsanız kodunuzun performansı o kadar kötü yönde ilerler. Bu tip karmaşıklıklara Polynomial denir.
const cubicOp =n=> {for(let i=0;i<n;i++)
for(let j=0;j<n;j++)
for(let k=0;k<n;k++) console.log(i) }6. Exponential Complexity
Logaritmanın tersi şekilde üstsel olarak işlem sayısı artan algoritmalar için kullanılır O(n^n). Bu konuyu bir hikaye ile anlatalım. Zamanında kendine güvenen bir bilginin karşısına gelmiş dile benden ne dilersen her şeyi yapabileceğini düşünen kral’a ders vermek isteyen bilge satranç tahtasının her bir karasine bir önceki karenin 2 katı buğday olacak şekilde bana buğday ver demiş. Kral ilk başta buna gülmüş ne var bundaki demiş ama her adımda buğday taneleri o kadar kastlamış ki daha satranç tahtasının ortasına gelemeden tüm stokları bitmiş.
İşte işlem açısından katlanarak artan bu tip fonksiyonlar işlem karmaşıklığı olarak sisteminizi tüketir. Olabildiğince bu tip hesaplamardan kaçmak girdi limitlerini iyi sınırlandırmak gerekir.
const exponentialOp = n => { let num = n; if (n === 0) return 1
for (let i = 0; i < n; i++)
num = n * exponentialOp(n - 1);
return num};
Okumaya Devam Et 😃
Bu yazının devamı veya yazı grubundaki diğer yazılara erişmek için bu linke tıklayabilirsiniz.
