Algoritma Analizi (Analysis of Algorithms)

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, bilgisayar bilimlerinin temelini oluşturan, algoritma analizini açıklamaktır. Genelde lisans seviyesinde bir dönemlik ders olarak okutulmaktadır. Bu ders hakkında çok sayıda kitap da yazılmıştır. Dolayısıyla bu yazıda sadece konu hakkında bilgi verilecektir.

Bilgisayar bilimlerinde temel olarak iki önemli kaynak bulunur:

  • Yer ( Hafıza )
  • Zaman ( Hız )

Buna göre bir bilgisayar programı, ne kadar fazla yer kaplıyor ve ne kadar yavaş çalışıyorsa o kadar kötü demektir. Tersine, hızlı çalışan ve az yer kaplayan program ise daha iyi olarak düşünülebilir.

Elbette bu kıyaslama benzer amaçlı programlar için yapılmalıdır. Örneğin üniversite sınavına giren yaklaşık bir milyon öğrencinin alfabetik olarak sıralanması istensin. Bu sıralama işlemini yapan 10 farklı yöntem varsa, bu yöntemlerden hangisini tercih etmemiz gerektiğini bulurken hız ve hafıza kullanımlarına bakmamız gerekir. Örneğin bir milyon kişiyi iki ayda sıralayan bir algoritma ile iki dakikada sıralayan bir algoritmadan hızlı olanını tercih etmek çok daha makul olacaktır.

Elbette, zaman kısıtlaması dışında kısıtlar da bulunur. Örneğin 2 dakikada bir milyon kişiyi sıralayacak algoritma, şu anda teknolojik olarak mümkün olmayan bir hafızaya (RAM) ihtiyaç duyarsa, bu algoritmayı kullanamayız.

Öyleyse algoritmayı tercih ederken elimizdeki hafıza ve zaman kısıtlarına göre en verimli seçimi yapmak zorundayız.

Burada önemli bir soru, bir algoritmanın ne kadar zamanda çalışıp biteceğinin nasıl bulunacağıdır.

Kısaca, bir algoritmanın çalışma süresini bulmanın en kolay yolu, algoritmayı çalıştırmaktır. Örneğimize dönecek olursak, bir milyon kişiyi sıralayan 10 farklı yol varsa, bunların hepsini deneyip sonra seçim yapmak çok doğru bir yol olmaz. Zaten ilk denemeden sonra sıralanmış olacağından diğer denemeler anlamsız olur.

Öyleyse tek bir sıralama işlemi yapacağız ama elimizdeki yollardan en iyisini kullanarak. Tam bu noktada devreye algoritma analizi girer.

Algoritma analizi, bilgisayar mühendislerine, bir algoritmayı çalıştırmadan, ne kadar sürede çalışacağını, veya en azından diğer alternatiflerine göre nasıl davranacağını (daha hızlı, daha yavaş, yakın hızda, daha az yer kaplayacak şekilde vb.) söyler.

Bu açıdan, algoritma analizi, bilgisayar mühendisliğinin (bilimlerinin) en önemli matematiksel dayanağını oluşturur. Matematik bilimindeki karmaşıklık teoreminin (complexity theory) bir uygulama alanı olan algoritma analizi, matematiksel yöntemlerle, bir algoritmanın performansı hakkında bilgi verir.

Günümüzde, özellikle Türkiye’de, yazılım sektöründe çalışan bilgisayar mühendislerinin, algoritma analizi konusunda donanımlı olmaları gerekmektedir. Bunun sebebi, bir programı yazmanın onlarca yolu olmasına karşılık en iyi yolun kullanılmaması durumunda, programın çalışırken ödenen büyük maliyetlerdir.

Örneğin, günümüzde pek çok firmada veri tabanı işlemleri yapılmaktadır. Bir veri tabanına bağlanılarak, verinin alınması için 100ms harcanması yerine 200ms harcanması aslında sadece 100 mili saniye gecikme olarak görülebilir. Ancak gün içinde milyonlarca kere çalışan bu kod, sonuçta daha fazla donanım ihtiyacı (ve dolayısıyla donanım maliyeti) ve takılan ekranlar, yavaş programlar gibi sonuçlar doğurabilir.

Algoritma Analizi ve Karmaşıklık Teoremi

Algoritma analizi çalışmalarının dayandığı karmaşıklık teoremi genel olarak bir bilgisayar programının veya algoritmasının asimptotik değerini bulmayı hedefler. Buradaki amaç, algoritmanın ulaşabileceği en kötü veya en iyi durumu matematiksel olarak modellemektir.

Bu sınıfların detayı için karmaşıklık sınıfları (complexity classes) isimli yazıyı okuyabilirsiniz.

Bu bölümün amacı bir örnek üzerinden, bir algoritmanın karmaşıklığının nasıl hesaplandığı hakkında fikir vermektir.

Örneğin ekrana çarpım tablosunu bastıran basit bir kod üzerinden ilerleyelim:

A: int n=10;

B: for (int i = 1;i<n;i++){

C:     for(int j = 1;j<n;j++)

D:        printf(“%d “,i*j);

E:     printf(“n”);

F: }

Yukarıdaki kodda, iç içe iki döngü (nested loop) kullanılarak çarpım tablosu, n = 10 , yani ilk 10 sayı için ekrana bastırılmak istenmiştir. Kodun ekran çıktısı aşağıdaki şekildedir:

Bu kodu analiz ederken, amacımız en kötü durumda, kodun ne kadar zaman alacağını bulmak olsun. Bu analiz şekline, worst case analysis (en kötü durum analizi) big-oh veya growth rate isimleri de verilmektedir.

Kodun ilk satırı koşulsuz bir şekilde bir kere çalışacaktır ve “n” isimli değişkeni tanımlayıp, hafızada yer açacak ve değişkene atama yaparak satırı bitirecektir. Bu işlemin maliyetine a diyelim.

Ekrana basma işleminin olduğu D satırında çalışacaktır ancak bu satırın çalışması birden fazla kere tekrar edilecektir çünkü döngülerin içerisindedir.

D satırı iki döngü içerisindedir dolayısıyla iki döngünün değerinin çarpımı kadar çalışacaktır. Bu döngülerin dönüş miktarı 9’dur. O halde D satırı 81 kere çalışır.

E satırı ise sadece bir döngü içerisindedir ve dolayısıyla B döngüsünün miktarı kadar çalışır. Bu değer de 9’dur.

Hesabımızı tamamlarsak, yukarıdaki kodun çalışma maliyeti:

M= A + 9B + 81C + 81D + 9E

Olarak bulunacaktır.

Bu değerleri biraz daha geneller ve n cinsinden yazarsak (n=10 değil farklı bir sayı olabilir diye genelleme yapmak istiyoruz)

M= 1 + n + n2 + n2 + n

M = 2n2 + 2n + 1

Yukarıdaki bu yeni maliyet hesabında basit satırların çalışma değerini 1 kabul ettik ve sonuçta 2. Dereceden bir çokterimli (polinom) bulduk.

Karmaşıklık sınıflarından büyük-o (big-oh) sınıfına göre analiz yaptığımızı hatırlarsak (en kötü durum analizi yapıldığı için, asimptotik üst sınır (aysmptotic upper bound) alınır)

M = O(n2)

Olarak maliyeti bulunmuş olunur.

Yorumlar

  1. Emre

    Merhaba hocam, bir sorum var:
    aşağıdaki verilen algoritmanın n’ye bağlı “run time” ını (Theta) Notation’da belirleyiniz.

    a = 10000*x € {1,…10};
    solange a >0{
    für b = 1,….n/30{
    c = 2b;
    }
    a =[a/2];
    }

    Kendi çözümüme göre : Dıştaki döngünün n’ye bağlı olmadığını varsayarsam, buradan sadece iç döngüdeki n’nin 30’da biri kadar çalıştığını görüyorum ve bunun theta notasyonuyla yazmak istersem Theta(n) olarak çözümleyebiliyorum.

    Bir diğer başka sorum ise;
    i=1;
    j=0;
    c=0;
    solange i=i
    i = i+1;
    }
    i = 1;
    k=0;
    solange i<c{
    i = i+2k+1;
    k = k+1;
    }

    Çözümüme göre: İç döngü'ye her zaman girişimizde bir kez çalışacak(i++'dan ötürü) ve n'ye kadar devam edecek.Bunu da Theta(n) buldum.Ama alttaki diğer while(i<c) döngüsünü işin içine katmadım onu da bağımsız olarak algılamıştım ?

    Cevap için şimdiden teşekkürler!

  2. gorkem

    Hocam, n haneli iki tam sayıyı çarpmak için kullanılan pen and pencil algoritması nasıl çalışmaktadır.Bu algoritma nedir.Araştırdım ve karşıma paper and pencil algoritması geldi.Bu iki algoritma aynı mıdır?

caner için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir