BİL204U-ALGORİTMALAR
Ünite 5: Algoritma Analizi
Giriş
İnsanoğlu hayatının birçok döneminde çok farklı problemler ile karşı karşıya kalmaktadır. Genel olarak problem “hedefe ulaşırken istenmeyen veya aşılması gereken bir durum” olarak nitelendirilse de farklı disiplinlerde kavramın anlamı farklılaşabilmektedir. Hangi anlamda kullanılırsa kullanılsın problem için bir veya birden fazla çözüm üretilmesi söz konusudur. 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.
Günlük yaşamımızda sezgisel yöntemler çok sık kullanılmasına rağmen bilgisayar ile gerçekleştirilen problem çözümlerinde genellikle algoritmik yaklaşım kullanılmaktadır. Ancak algoritmik yaklaşım ile çözülemeyen problemler için sezgisel (heuristic) yaklaşım tercih edilmektedir. Sezgisel yaklaşımda çözüm her zaman doğru olmayabilir veya doğruluğu her zaman ispat edilemeyebilir. Ayrıca sezgisel yöntemle üretilen çözümlerin performansı da farklılık göstermektedir.
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. 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 geliştirme tamamen bir tasarım işidir ve birçok kaynakta bu süreç için “algoritma tasarımı” ifadesi kullanılmaktadır. 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. Değişken, veriyi saklamak ve kullanmak için oluşturulan karakter veya karakter topluluklarıdır. Örneğin; bir öğrencinin geçme notu hesaplanma probleminde, ihtiyacımız olan vize ve final verilerini saklayabilecek değişkenlere ihtiyaç duyulmaktadır. Ardından bu veriler ile hesaplama yapılıp çıktı olarak sunulmalıdır. Daha önceki bölümlerde bahsedildiği gibi Algoritmanın tasarlanırken sözde-kod (pseudo-code), akış diyagramları vb. farklı gösterim türlerinden yararlanılabilmektedir. Günümüzde bilgisayar ağları, kriptografi, bilgisayar Grafiği, Veritabanı, hesapsal biyoloji/geometri/işlem, tıp, uzay ve havacılık, doğal dil
işleme vb. birçok alanda farklı algoritmalar geliştirilmiştir. Alanyazında, sıralama, arama, En-kısa-yol problemi, süreç planlama, bellek yönetimi, benzerlik, paketleme, çizge, genetik, optimizasyon, veri sıkıştırma vb. gibi problemlere yönelik birçok algoritma bulunmaktadır.
Bir problemin çözümü için birden fazla algoritma tasarımı yapılabilmektedir. Bu noktada hangi çözümün uygulanacağı bir yeni bir problem olarak karşımıza çıkmaktadır. Bunun çözümü için ise algoritma tasarımlarının performanslarının karşılaştırması gerekmektedir. Herhangi bir algoritmanın performansını yani ne kadar hızlı çalıştığını veya ne kadar sürede çalıştığını hesaplamak için o algoritmayı analiz etmemiz gerekmektedir. 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 tasarımı gerçekleştikten sonra ise herhangi bir programlama dilinde algoritmanın gerçekleştirilmesi sürecine geçilmelidir.
Bu bölümde algoritma analizinin tanımı, çalışma zamanı, en iyi en kötü, ortalama zaman ve asimptotik gösterimlerden bahsedilecektir.
Algoritma Analizi
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. 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. Bu kavramlar alt başlıklar hâlinde incelenecektir.
Yürütme Zamanı/Zaman Karmaşıklığı
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.
Alan Karmaşıklığı
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. Alan karmaşıklığı temel olarak program kodu ve verisi için gerekli tüm alanları kapsamaktadır. Eğer programın kodu için gerekli alan küçük ise hesaplamaya dahil edilmemektedir. Alan karmaşıklığı hesabında algoritma içerisinde kullanılan bellek alanları göz önünde bulundurularak hesaplamalar gerçekleştirilir. Örneğin, içerisinde n adet tamsayı (2 byte) bulunduran bir algoritma için alan karmaşıklığı 2n olarak hesaplanır. Alan karmaşıklığı fonksiyonu S(n) şeklinde gösterilmektedir. Eğer algoritma girdisi küçük ise alan karmaşıklığı göz ardı edilebilmektedir. Ancak yüksek girdilerde bu zaman karmaşıklığının yanında bu analize de ihtiyaç bulunmaktadır.
En İyi, En Kötü ve Ortalama Durumlar
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.
Asimptotik Gösterim
Bir önceki başlık altında, zaman karmaşıklığı hesaplamalarında, girdi sayısı olan bir algoritma için “n” değişkenini kullanarak zaman karmaşıklığı fonksiyonu yani T(n)’i hesaplaması hakkında bilgiler sunulmuştu. Bu başlık altında ise eleman sayısı n’nin sonsuza gitmesi durumunda algoritmanın, benzer işi yapan algoritmalarla karşılaştırmak için kullanılan asimptotik gösterim hakkında bilgiler sunulacaktır.
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.
Örneğin zaman karmaşıklığı T(n)=80n2+3n+74 olan bir
algoritmayı ele alalım. Bu fonksiyon içerisindeki katsayılar ve sabitleri göz ardı ettiğimizde 80n2 gibi bir fonksiyon elde
edebiliriz.
Big-O Gösterimi (O(n))
Big-O gösterimi ilk olarak Paul Bachman ve Edmund Landau tarafından ortaya atılmıştır. 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.
Big-O gösterimi diğer asimptotik gösterimlerde de olduğu gibi birçok ifadeyi sadeleştirerek elde edilir. Örneğin çalışma zamanı T(n)=n4+n2+2n+8 olan bir algoritma için Big-O gösterimi O(n4) şeklinde olacaktır. Bu işlem bir
fonksiyonun büyümesi şeklinde de tanımlanmaktadır.
Big Omega Gösterimi (Ω(n))
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-Omega gösterimi big-O gösterimlerde de olduğu gibi birçok ifadeyi sadeleştirerek elde edilir. Örneğin çalışma zamanı T(n)= 8n2logn+ 5n2+ n olan bir algoritma için Big-Omega gösterimi O(n2logn) şeklinde olacaktır.
Big Theta Gösterimi (Θ(n))
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.
Bilgisayarların artık hayatımızın her alanına girdiği bizim için kararlar aldığı, süreçleri yönettiği bir zamanda yaşamaktayız. Bu işlemlerin daha hızlı ve iyi gerçekleşebilmesi için güçlü bilgisayarlar ve iyi tasarlanmış ve kodlanmış yazılımlara ihtiyaç duyulmaktadır. Yazılımlar genelde bir problemin otomatik çözülmesi ve hayatımızı kolaylaştırmak için geliştirilmektedir. Yazılım geliştirme süreçleri bir problem ile başlamaktadır. Bu problemin çözümü için ise birden fazla çözüm yolu üretilebilir. Bir başka deyişle, aynı problemi çözen birden çok algoritma geliştirilebilmektedir. Bu noktada hangi algoritmanın seçileceği önem kazanmaktadır. Algoritmaları karşılaştırmak için onların çalışma zamanı ve kullandıkları bellek alanı açısından analiz edilmeleri gerekmektedir. Bu analiz sonuçlarına göre ise bir karar verilebilir. Genel olarak karar verirken algoritmaların çalışma zamanı göz önünde bulundurulmasına rağmen kullanılan bellek alanı da muhakkak göz önünde bulundurulmalıdır. Algoritma analizi sonucu girdi miktarına (n) bağlı bir fonksiyon (T(n)) ile ifade edilmektedir. Bu fonksiyon genel olarak çok çok fazla detay içermektedir. Bu nedenle yüksek miktarda girdi alan algoritmaların analizinde asimptotik gösterimlerden yararlanılmaktadır. Asimptotik gösterimler temelde zaman karmaşıklığı fonksiyonunun sadeleştirilmiş hâlidir. Asimptotik gösterimler, Big-O, Big-Omega ve Big-Tetha olarak isimlendirilmektedir. Big-O gösterimi algoritmanın olabilecek en kötü durumu üzerinden hesaplanırken, Big-Omega ise en iyi durum üzerinden hesaplanmaktadır. Big-tetha ise algoritmanın ortalama çalışma süresini göstermektedir. Asimptotik gösterimler ile algoritmaları karşılaştırmak oldukça kolay bir hâl almaktadır.