Algoritma Analizi

Karşılaşılan problemlere çözüm veya çözümler üretirken birtakım aşamalardan geçmek gereklidir. Bu aşamalar; problemin farkına varılması, problemin anlaşılması/tanımlanması, problem için farklı çözüm yollarının üretilmesi, çözüm yollarının test edilmesi, en uygun çözümün belirlenmesi, çözümün uygulanması, elde edilen sonuçların değerlendirilmesi ve çözümün iyileştirilmesi şeklinde sıralanabilir. Problemlerin çözümünde algoritmik ve sezgisel yaklaşımlar kullanılabilmektedir.

Genel olarak baktığımızda sonucu doğru üreten algoritmalar arasında mantıken az yer kaplayan ve daha hızlı çalışan algoritmayı seçmemiz gerekmektedir. Bu noktada algoritma tasarımları arasındaki milisaniyelik farklar bile önem kazanmaktadır. Çünkü sunulan algoritmik çözüm defalarca kullanılabilmektedir. Görüldüğü üzere algoritma tasarımının seçimi, en az üretimi kadar önemli ve kritik bir konudur.

Algoritma kelimesi, dokuzuncu yüzyılın önemli İslam bilim adamlarından matematikçi Muhammed bin Musa Al-Harezmi’nin adından gelmektedir. Algoritma günümüzde, bir sorunun çözümü için, sonlu sayıda adım biçiminde iyi tanımlanmış, sonlu kurallar kümesi olarak tanımlanmaktadır (TDK, 2022). Bu tanım çerçevesinde algoritmanın sahip olması gereken birtakım özellikler de bulunmaktadır. Bunlar etkinlik, kesinlik, doğruluk, sonluluk, verimlilik, genellenebilirilik ve girdi/çıktı içerme şeklinde sıralanabilir. Bunlara ek olarak algoritmanın performansının da değerlendirilebilir olması gerekmektedir.

Algoritma tasarımında öncelikle problemin analiz edilmesi gerekmektedir. Problem analizinde elde var olan veriler, istenen sonuç, değişkenler ve çözüm için geçilmesi gereken ara basamaklar / alt problemler belirlenmelidir.

Algoritma Analizi, çözüm için geliştirilen algoritmaların veya programların kaynak (bellek, bant genişliği vb.) kullanımı ve performansı üzerine yapılan çalışmalar olarak tanımlanabilir.

Algoritma analizi, bilgisayarın gücünden, özel durumlardan ve veriden bağımsız olarak hesaplanmalıdır. Algoritma analizi, özellikle veriye bağımlı olmamalıdır çünkü algoritmanın performansı verinin büyüklüğü ile değişiklik göstermektedir.

Algoritmaları karşılaştırmak için gerçekleştirdiğimiz algoritmanın zorluk derecesi ölçümüne “hesaplama karmaşıklığı (Computational Complexity)” denmektedir. Hesaplama karmaşıklığı algoritmanın gerçekleşebilmesi için gerekli olan maliyet olarak da tanımlanabilir.

Algoritma analizinde temel kavramlar, yürütme zamanı / zaman karmaşıklığı, alan karmaşıklığı, en iyi, ortalama, en kötü durumlar olarak karşımıza çıkmaktadır.

Geliştirilen bir algoritmanın problemi çözmek için harcadığı süreye “yürütme zamanı” ismi verilmektedir. Fakat bu noktada direk olarak süre karşılaştırılması, algoritmanın üzerinde çalıştığı bilgisayarın işlem gücü ile direk olarak bağlantılı olacaktır. Bu nedenle yürütme zamanı hesaplanırken algoritmanın çalıştığı süre boyunca kaç komut işlediği bilgisi kullanılmaktadır. Bir başka deyişle, algoritmanın çözüme ulaşabilmesi için, temel kabul edilen işlemlerden kaç adet yürütülmesi gerektiğini veren bir bağıntıdır. Burada temel işlem olarak kastedilen karşılaştırma, döngü çevrimi, aritmetik işlem gibi işlemlerdir

Algoritma analizi genel olarak iki önemli maliyet bulunmaktadır. Bunlardan ilki algoritmanın kullandığı bellek alanıdır ve “alan karmaşıklığı” olarak isimlendirilir. Diğer maliyet ise çalışma zamanıdır ve “zaman karmaşıklığı” şeklinde ifade edilmektedir.
Günümüz teknolojisi göz önünde bulundurulduğunda, eğer problemin boyutu çok küçük ise algoritmanın hesaplama karmaşıklığının hesaplanması çok gerekli olmamaktadır. Algoritma seçiminde genel olarak zaman karmaşıklığı göz önünde bulundurulsa da zaman ve bellek gereksinimleri arasındaki dengeyi her zaman göz önünde bulundurmalıyız.

Bir algoritmanın alan karmaşıklığı veya alan maliyeti, algoritmanın problemi çözmesi için gerekli bellek alanını veren bir değer veya fonksiyon olarak tanımlanmaktadır.

Bir algoritma tasarımının analizinde genellikle girilen verilere veya koşullu ifadelere bağlı olarak sonuç daha hızlı veya daha yavaş bir şekilde üretilebilmektedir. Bir algoritmanın bu durumlara göre en hızlı şekilde sonuca ulaşma durumuna en iyi durum (best case), en yavaş ulaşma durumuna ise en kötü durum (worst case) denmektedir. Bu algoritma bu iki durumdan daha hızlı veya yavaş çalıştırılamaz. Algoritmanın girdi seviyesinde tüm olasılıklar göz önünde bulundurularak hesaplanan durumuna ise ortalama durum (average case) denmektedir.

Esasen algoritma analizinde, t(zaman) ve n (girdi büyüklüğü) arasındaki ilişki için bir fonksiyon bulunmaya çalışılmaktadır. Ama genelde bu ilişki oldukça karışık ve çok terimli olabilmektedir. Bu nedenle fonksiyon içerisindeki katsayılar ve sabit sayılar atılarak fonksiyon daha basit hâle getirilebilir. Basitleştirilir ve gerçek fonksiyona göre yaklaşık bir fonksiyon sunulur. Bu basitleştirme işlemi ile elde edilen ölçüme asimptotik karmaşıklık denmektedir.

Big-O gösterimi zaman karmaşıklığında üst sınırı ifade etmektedir. Bir başka deyişle algoritmanın en kötü çalışma
zamanını gösterir.

Zaman karmaşıklığı fonksiyonunu sadeleştirirken farklı yaklaşımlar uygulanabilmektedir. Bu yaklaşımlara bağlı olarak farklı asimptotik gösterimler ortaya çıkmıştır. Bunlar Big-O (O(n)), Big-tetha (Θ(n)) ve Big-omega (Ω(n)) asimptotik gösterimleridir. Bu gösterimler dışında çok kullanılmadıklarından dolayı bölümün kapsamına alınmayan little-o ve little-omega gösterimleri de mevcuttur

f ve g reel sayılarda tanımlı iki fonksiyon olsun.
f(x) fonksiyonu için
c ve k sabit olmak üzere O(g(x)) fonksiyonu aşağıdaki gibi tanımlanmaktadır.
O(g(x)) = c. |g(x)| + k olmak üzere;
|f(x)| ≤ c. |g(x)| + k
Zaman fonksiyonu negatif olamayacağı için burada f(x) ve g(x) fonksiyonları her zaman pozitif kabul
edilmektedir.

Big-Omega gösterimi Big-O gösteriminin tam tersi olarak görülebilir. Yani Big Omega gösterimi zaman karmaşıklığında alt sınırı göstermektedir. Bir başka deyişle Big-Omega ile ölçülen değerden daha iyi daha hızlı bir değer bulunamaz.

Big theta gösterimi big-O gösterimi ile big-Omega gösterimi arasında ortalama bir karmaşıklığı ifade eder. Bir başka deyişle algoritmanın ortalama çalışma zamanını göstermektedir.
Matematiksel olarak ifade etmek gerekirse;
Bir f(x) fonksiyonu için her durumda
c1.g(x) <=f(x) <=c2.g(x) koşullarını sağlayan pozitif, sabit c1, c2 değerleri bulunabiliyorsa
f(x)= Θ(g(x))
şeklinde ifade edilebilir.
Bunlara ek olarak big-tetha fonksiyonunu aşağıdaki şekilde ifade etmekte mümkündür.
Θ(g(n)) = O(g(n)) ∩ Ω (g(x))

f ve g reel sayılarda tanımlı iki fonksiyon olsun.
f(x) fonksiyonu için
c ve k sabit olmak üzere Ω (g(x)) fonksiyonu aşağıdaki gibi tanımlanmaktadır.
Ω (g(x)) = c. |g(x)| + k olmak üzere;
c. |g(x)| + k ≤ |f(x)|
Zaman fonksiyonu negatif olamayacağı için burada da f(x) ve g(x) fonksiyonları her zaman pozitif
kabul edilmektedir.

Bir f(x) fonksiyonu için her durumda
c1.g(x) <=f(x) <=c2.g(x) koşullarını sağlayan pozitif, sabit c1, c2 değerleri bulunabiliyorsa
f(x)= Θ(g(x))
şeklinde ifade edilebilir. Bunlara ek olarak big-tetha fonksiyonunu aşağıdaki şekilde ifade etmekte mümkündür.
Θ(g(n)) = O(g(n)) ∩ Ω (g(x))