Algoritma Analizi

ALGORİTMA ANALİZİ

Algoritma Nedir?

Algoritma, belli bir problemi çözmek veya belirli bir amaca ulaşmak için tasarlanan yol. Matematikte ve bilgisayar biliminde bir işi yapmak için tanımlanan, bir başlangıç durumundan başladığında, açıkça belirlenmiş bir son durumunda sonlanan, sonlu işlemler kümesidir.

Algoritma Analizi

Algoritma analizinin amacı; bir problem karşısında mevcut algoritmalar içerisinden en uygun olan algoritmanın seçilmesidir. Buradaki “en uygun” ifadesi kullanıcıdan kullanıcıya, sahip olunan kaynak ve ihtiyaca göre değişmektedir. Algoritma analizinde zaman ve alan olmak üzere 2 temel kriter bulunmaktadır. Kullanıcılar için algoritmanın kısa sürede çalışmasını tamamlaması çok önemli fakat alan kullanımı önemli değilse, süre bazında en hızlı algoritma tespit edilmekte ve kullanılmaktadır. Kullanıcının sahip olduğu sistemler üzerindeki alanlar (ki bu bellek oluyor) kısıtlı, fakat zaman tüketimi sorun değil ise, en az bellek harcayan algoritmaların tespit edilip kullanılması gerekmektedir. İşte algoritma analizi bu noktada önem kazanmaktadır. Kullanıcı açısından bu iki kavramdan hangisi daha önemli ise, söz konusu kavramlar açısından mevcut algoritmalar analiz edilmekte ve en uygun algoritma seçilerek kullanılmaktadır.

Asimtotik Notasyonlar

1.Büyük O Notasyonu

Çalışma zamanının üst sınırı olan, en kötü durumdaki zamanın belirlenmesinde büyük O notasyonu kullanılır. Yunanca büyük “omikron” harfi ile ifade edilen bu notasyonun matematiksel tanımı aşağıdaki gibidir.            

 f(n) = O(g(n)) olması için, tüm [n ≥ k] için [0 ≤ f(n) ≤ cg(n)] olacak şekilde pozitif “c” ve “k” sabitleri tanımlıysa bu fonksiyon büyük O notasyonuyla gösterilebilir. “c” ve “k” değerleri “f” fonksiyonuna bağlı, “n”den bağımsız sabitler olmalıdır.

2.Omega Notasyonu

Bu notasyon, algoritmaların en iyi durumdaki çalışma zamanını ifade etmek için kullanılır. Giriş değerleri analiz edildikten sonra en iyi giriş için algoritmanın O notasyonuyla ifadesi Ω notasyonu olarak adlandırılır. Küçük dereceden terimler ve sabitler atılır. Best-case çalışma süresi veya lower bound tanımlamasında kullanılır.

 3.Büyük Teta Notasyonu

“Big-Theta” Q İfadesi ile gösterilir. f(n) = Q(g(n)), eğer sabit c1, c1 ve n0 değerleri için c1 g(n) £ f(n) £ c2 g(n) bütün n ³ n0 değerleri için doğruysa.  Çalışma sürelerinin karşılaştırılması için kullanılır. Eğer f(n)=o(g(n)), ise g(n), f(n) fonksiyonundan daha ağırlıklıdır.

Özyineli Algoritmalar

Bütündeki çözüm mantığı alt problemlerde de geçerli ise özyinelemeli algoritmalar kullanılabilir. Fonksiyonlar kendi kendilerini çağırabilecekleri gibi, çağırdıkları bir fonksiyon tarafından da çağrılabilirler. Özyineli algoritmalar hem güçlü algoritmalardır, hem de karmaşık yapıları daha rahat açıklayabilirler.

Tümevarım: Tümevarım, gözlenen tek tek olgulardan yola çıkarak genel yargılara ulaşmaktır. Başa bir deyişle tümevarım özelden genele giden bir akıl yürütme türüdür. 

Tümdengelim: Tümdengelim, gerek akıl gerekse gözlem ve deney yoluyla elde edilmiş genel bir ifadeyle ayrı ayrı olaylara uygulamaktır. Başka bir deyişle özelin bilgisini genel yargılardan çıkarmaktır. 

Böl ve Yönet Yaklaşımlı Algoritmalar

Hem birleştirmeli sıralama, hem de hızlı sıralama, özyinelemeye dayanan ortak bir algoritmik paradigma kullanırlar. Bu paradigma, böl ve yönet, bir problemi orijinal problemlere benzer alt problemlere ayırır, alt problemleri özyinelemeli olarak çözer ve sonunda alt problemlerin çözümleri birleştirerek orijinal problemi çözmüş olur. Böl-ve-yönet alt problemleri özyinelemeli olarak çözmek için, her alt problem orijinal problemden daha küçük olmalıdır ve alt problemler için bir temel durum bulunmalıdır. Bir böl-ve-yönet algoritmasının üç parçalı olduğunu düşünmelisiniz:

1. Bir problemi, bu problemin daha küçük örneği olan birkaç alt probleme bölün.

2. Alt problemleri özyinelemeli olarak çözerek yönetin. Yeterince küçük iseler, alt problemleri temel durumlar olarak çözün.

3. Alt problemlerin çözümlerini birleştirerek orijinal problemin çözümüzü elde edin.

Hızlı Sıralama

Hızlı sıralama algoritması performans olarak iyi derecede sayılacak bir sıralama algoritmasıdır. Hızlı sıralama algoritması her adımda işlenecek olan dizinin boyutu kadar karşılaştırma yapar.

Merge Sıralama

Merge Sort (Birleştirme Sıralaması), diziyi ardışık olarak en küçük alt dizilerine kadar yarılayan sonra da onları sıraya koyarak birleştiren özyineli bir algoritmadır. Yarılama işlemi en büyük alt dizi en çok iki öğeli olana kadar sürer. Sonra "Merge (Birleştirme)" işlemiyle alt diziler ikişer ikişer bölünüş sırasıyla sıralı olarak bir üst dizide birleşir. Süreç sonunda en üstte sıralı diziye ulaşılır.

Algoritmanın çalışması kavramsal olarak şöyledir:

1.       Sıralı olmayan diziyi ortadan eşit olarak iki alt diziye ayırır.

2.       Bu ayırma işlemi, alt diziler en çok iki elemanlı olana kadar devam eder.

3.       Alt dizileri kendi içinde sıralar.

4.       Sıralı iki alt diziyi tek bir sıralı dizi olacak şekilde birleştirir.

                                      

Merge Sort algoritması ile Heap Sort algoritması aynı zaman aralığına sahip olmalarına rağmen Heap Sort algoritması bellekte Merge Sort algoritmasına göre daha az yer tutar ve bu algoritmalar gerçekleştiğinde Heap Sort algoritması daha hızlı çalışır. Quick Sort algoritması da bellek tabanlı dizilerde Merge Sort'a göre daha hızlı çalışmaktadır. Ancak bağlı liste sıralamasında seçilebilecek en performanslı algoritma Merge Sort algoritmasıdır. Çünkü bağlı listelerin yapısı gereği mergesort bellekte fazladan sadece 1 birim yer tutar ve bağlı listelerin yavaş ve rastgele erişim performansı nedeniyle quicksort gibi diğer algoritmaların çalışma performansı düşer, Heap Sort gibi algoritmalar için ise imkânsızdır.

Heap Sıralama

Heap Sort, özel ağaç yapısı ile eleman kümesindeki değerlerin kümeleme işlemi yapılmasıyla ortaya çıkan sıralama algoritmasıdır. Türkçeleştirildiğinde ‘yığınlama sıralaması’, ‘kümeleme sıralama’, ‘öbek sıralama’ gibi isimlerle karşımıza çıkmaktadır. Heap sort algoritması, recursive fonksiyon içermediği için merge sort algoritmasından daha hızlı, ancak birçok makine de pratikte quick sort algoritmasından daha yavaştır. Bu algoritmada büyük olan sayı daima ağacın üst bölümünde yer alır. Kendinden küçük sayılar bu ağacın dallarını oluşturmaktadırlar.

Durum performansı O(n) ile O(n²) arasındadır. En kötü durum performansı (worst case performance) ise O(n log n)‘dir.

Dinamik Programlama

Dinamik programlama, yöneylem araştırmasında kullanılan optimizasyon yöntemlerinden birisidir. Optimizasyonda amaç, mevcut kısıtlayıcı koşullar altında, eldeki sorunla ilgili en iyi karara varmaktır. Biri diğerini izleyen ve karşılıklı etkileri olan bir dizi kararın bütünüyle ele alındığı problemler için geliştirilen karar modelleri ve bunların çözümleri “Dinamik Programlama” başlığı altında incelenir. Öte yandan incelenen problemin biri diğeriyle ilişkili alt problemlere ayrılabilme özelliğini taşıması ya da bir problem için geliştirilen karar modelinin, birbirine bağlı karar modelleri haline dönüştürülmesi, dinamik programlama uygulaması için yeterli olmaktadır. Bazı ekonomik değişme ve gelişmeler, gelecek dönem için önceden yapılan planları geçersiz kılabilir. Bu durumda yeni bir planlamaya gereksinim vardır ya da önceki plan güncelleştirilmelidir. Koşullar bir zaman sürecinde değişiyorsa ve bunların alınan kararlara etkisi önemli ise, dinamik programlama modellerine gereksinim vardır.

Amortisman Analizi

Bir firmada bir yıldan fazla kullanılacağı düşünülen ve herhangi bir biçimde değerden düşmesi söz konusu olan ekonomik değerlerde oluşacak değerlerin bir yıl içinde uğradıkları değer kayıplarının üretilen malların maliyet tutarlarına eklenmesi veya söz konusu kayıpların o yılın giderleri arasına yazılması amortismanın konusunu oluşturur. Amortisman ayrılması yolu ile sabit değerlerin zamanla işletme sermayesi haline dönüşmesi. Maddi sabit kıymetlere aktarılan fonların yani yapılan yatırım harcamalarının, dönem içerisinde amortisman ayrılarak şirkete geri dönüşünü sağlar. Ayrıca gider yazılarak vergi matrahını azaltıcı bir etkisi olduğu için daha az vergi ödenmesini sağlar.

Hash Tabloları

Hash tablosu, veriye bir anahtar yardımı ile erişilen basit bir dizi üzerine bina edilmiştir. Anahtar kullanılarak bir indeks üretilir ve bu indeks ile dizideki istenen veriye ulaşılır. Anahtar tekildir yani bir başka kayıtta aynı anahtar olamaz. Ancak veri aynı olabilir. Bir sınıftaki öğrenciler buna çok iyi bir örnektir. Her öğrencinin sadece kendine ait bir numarası vardır. Ancak aynı isme sahip iki öğrenci olması muhtemeldir. Burada öğrenci numarası anahtardır; öğrenci ismi ise, bu anahtara ait veridir. Hash tablosu, en hızlı aramayı sunan veri yapılarından biridir. O(1) ile ifade edilebilecek sabit bir zaman diliminde arama yapılır. En kötü durumda ki aşağıda bahsedilen çakışma durumudur bu değer O(n) olabilmektedir. Eğer hash fonksiyonu, iki farklı anahtar için aynı hash kodunu üretmiyorsa hash tablosu doğrudan adreslidir denir. Hash tablosunun pratikte kullanılabileceği bir uygulama vekil sunucularıdır. Daha önce ziyaret edilen sayfalar diske saklanır ve sonraki erişim istekleri yerel diskten karşılanır. Diskteki web içeriğine ulaşmak için vekil sunucu istenilen adresi anahtar olarak kullanarak bir hash değeri üretir. Ve bu hash değeri ile istenen sayfaya ulaşılır. Doğru veriye ulaşmak için, içerik daha önceden aynı fonksiyonun ürettiği indekse saklanmış olmalıdır.

Doğrusal Programlama

Matematik biliminde, özellikle yöneylem araştırması uygulamalı dalında, doğrusal programlama problemleri bir doğrusal amaç fonksiyonun doğrusal eşitlikler ve eşitsizlikler kısıtlamaları ile optimizasyon yapılmasıdır. Doğrusal programlama, belli doğrusal eşitsizliklerin kısıtlayıcı koşullar altında doğrusal bir amaç fonksiyonunu optimumlaştırmak biçiminde tanımlanabilir. Buradaki optimumlaştırma, belli bir amaca en düşük maliyetle ulaşmak ya da belli kaynaklarla en yüksek kârı sağlamak anlamındadır.

Paralel Programlama Algoritmaları

Bugünün çoğu algoritmaları ardışık şekilde işler diğer bir ifade ile seri programlama mantığındadır, yani, her basamağın tek bir işlemden oluştuğu bir dizi adımı belirtirler. Bu algoritmalar temel olarak ardışık bir biçimde işlemleri yürüten bugünün bilgisayarlarına uyumludur. Araştırmacılar “paralel” bilgisayarlarda ve/veya işlemcilerde bir adımda çoklu işlemleri yürüten bilgisayarlar ve programlar geliştirerek daha uygun maliyetli, daha hızlı ve verimli gelişmeler hedefliyorlar. Paralel bir makinede ya da işlemcide bir işlemi etkili bir şekilde çözebilmek için, her adımda çoklu işlemleri belirleyebilen bir algoritma tasarlamak gereklidir. Örneğin, n elemanlı bir A dizisinin toplamını hesaplamayı ele alalım. Standart algoritma, toplamı dizinin ilk elemanından son elemanına kadar tek bir geçiş yaparak, o zamana kadar görülen sayıları işleyen bir toplamı tutarak hesaplama işlemini gerçekleştirir. Buna karşın paralel olarak çok sayıda işlemi yürüten toplamı hesaplamak için bir algoritma tasarlamak zor değildir.