bilgiz.org

1. Algoritmaların Karşılaştırılması

  • 2. Algoritmalarda Zaman Karmaşıklı ğı Analizi 2.1. İşletim Zamanı
  • Şekil 2.
  • Birim Zaman Frekans Toplam Zaman



  • Tarih01.10.2017
    Büyüklüğü97.9 Kb.

    Indir 97.9 Kb.

    1. Algoritmaların Karşılaştırılması

    Algoritma bir problemi çözmek için adım adım uygulanan kurallar dizisidir. Algoritma işlenmemiş veriden belirli bir bilgi oluşturur. Dolayısıyla her algoritma herhangi bir giriş verisine karşılık mutlaka bir çıkış bilgisi oluşturur.

    Bir algoritmanın performansı genellikle onun işletimi için gerekli olan bilgisayar zamanı ve belleği ile belirlenir. Bir algoritmanın zaman karmaşıklığı (time complexity) programın işletim süresidir, buna hesaplama karmaşıklığı (computational complexity) da denilir. Bir algoritmanın yer karmaşıklığı (space complexity) onun işletildiği sürece gerekli olan yer (bellek) miktarıdır. Bir problemin çözümünde, kullanılabilecek olan algoritmalardan en etkin olanı seçilmelidir. En kısa sürede çözüme ulaşan veya en az işlem yapan algoritma tercih edilmelidir. Burada bilgisayarın yaptığı iş önemlidir. Bazı durumlarda da en az bellek harcayan algoritmanın tercih edilmesi gerekebilir. Ayrıca, programcının yaptığı iş açısından veya algoritmaların anlaşılır olmaları bakımından da algoritmalar karşılaştırılabilir. Daha kısa sürede biten bir algoritma yazmak için daha çok kod yazmak veya daha çok bellek kullanmak gerekebilir.

    Aynı işi yapan algoritmaları yaptıkları iş açısından karşılaştırmak için her algoritmaya uygulanabilecek somut ölçüler tanımlanmalıdır. Rakip algoritmalardan daha az işlemde sonuca ulaşanın (hızlı olanın) belirlenmesi, yani daha genel olarak algoritma analizi teorik bilgisayar bilimlerinin önemli bir alanıdır.

    Yazılımcılar, iki farklı algoritmanın yaptıkları işi ölçüp karşılaştırmak için çeşitli yöntemler denemişlerdir. İlk çözüm, algoritmaları bir programlama dilinde kodlayıp her iki programı da çalıştırarak işletim sürelerini karşılaştırmaktır. Bu yöntemde işletim süreleri belirli bir bilgisayara bağlıdır, yani farklı bir bilgisayarda sonuç farklı çıkabilir. Daha genel bir ölçüm yapabilmek için olası tüm bilgisayarlar üzerinde algoritmanın çalıştırılması gerekir. İkinci çözüm, işletilen komut ve deyimlerin sayısını bulmakla gerçekleştirilir. Fakat bu ölçüm kullanılan programlama diline göre ve programcıların stiline göre değişim gösterir. Bunun yerine algoritmadaki kritik geçişlerin sayısı hesaplanabilir. Her tekrar için sabit bir iş yapılıyor ve sabit bir süre geçiyorsa, bu ölçü anlamlı hale gelir.

    Buradan, algoritmanın temelinde yatan bir işlemi ayırarak, bu işlemin kaç kere tekrarlandığını bulma düşüncesi doğmuştur. Örnek olarak bir tamsayı dizisindeki tüm elemanların toplamını hesaplama işleminde gerekli olan iş miktarını ölçmek için tamsayı toplama işlemlerinin sayısı bulunabilir. 100 elemanlı bir dizideki elemanların toplamını bulmak için 99 toplama işlemi yapmak gerekir. n elemanlı bir listedeki elemanların toplamını bulmak için n–1 toplama işlemi yapmak gerekir diye genelleştirme yapabiliriz. Böylece algoritmaları karşılaştırırken belirli bir dizi boyutu ile sınırlı kalınmaz.

    İki gerçel matrisin çarpımında kullanılan algoritmaların karşılaştırılması istendiğinde, matris çarpımı için gereken gerçel sayı çarpma ve toplama işlemlerinin karışımı bir ölçü olacaktır. Bu örnekten ilginç bir sonuca ulaşılır: Bazı işlemlerin ağırlığı diğerlerine göre fazladır. Birçok bilgisayarda bilgisayar zamanı cinsinden gerçel sayı çarpımı gerçel sayı toplamından çok daha uzun sürer. Dolayısıyla matrislerin çarpımı düşünüldüğünde toplama işlemlerinin performans üzerindeki etkisi az olacağından ihmal edilebilir ve sadece çarpma işlemlerinin sayısı dikkate alınabilir. Algoritma analizinde genelde algoritmada egemen olan bir işlem bulunur ve bu işlem diğerlerini gürültü (noise) düzeyine indirger.

    Bir diğer algoritma karşılaştırma yöntemi ise “multi-thread” adı verilen bir programın kendini eş zamanlı çalıştırılan birden fazla iş parçasına ayırabilmesini sağlayan yapıyı kullanmaktır. Karşılaştırılmak istenen algoritmalar iş parçaları olarak programa verildiğinde, ilk önce sonuç üreten algoritmanın daha hızlı olduğu sonucuna varılır. Multi-thread yapısı her iş parçasına aynı miktar kaynak ayrılmasını sağladığından, bu program farklı bilgisayar sistemlerinde çalıştırılsa da sonuç değişmez.

    Algoritmaların hesaplama süresini değiştirebilecek bir diğer faktör ise kullandıkları verilerdir. Örneğin hızlı sıralama (quicksort) ve kabarcık sıralaması (bubble sort) karşılaştırıldığında, rastgele sırada verilerden oluşan bir diziyi hızlı sıralamanın (quicksort) daha hızlı sıraladığı, neredeyse sıralı (sadece birkaç elemanın yeri yanlış olan) verilerden oluşan diziyi ise kabarcık sıralamasının (bubble sort) daha hızlı sıraladığı görülecektir. Yani, sadece bu iki örnek incelenirse hangi sıralama algoritmasının daha hızlı olduğu konusunda bir fikir sahibi olabilmek mümkün değildir. Böyle durumlarla, tüm diğerlerinden üstün bir algoritmanın mevcut olmadığı zamanlarda karşılaşılmaktadır ve bir yerine birçok algoritmanın kullanıldığı görülmektedir. Uygun algoritmanın seçimi ise çokça karşılaşılan veriler ve algoritmaların bu veriler için kullandığı süreleri incelenerek yapılmaktadır.

    2. Algoritmalarda Zaman Karmaşıklığı Analizi

    2.1. İşletim Zamanı

    İşletim zamanını (running time) girdi boyutunun bir fonksiyonu olarak ele almak, tüm geçerli girdileri tek değere indirger. Bu da değişik algoritmaları karşılaştırmayı kolaylaştırır. En yaygın karmaşıklık ölçüleri “en iyi durum işletim süresi” (best–case running time), “en kötü durum işletim süresi” (worst–case running time) ve “ortalama durum işletim süresi” (average-case running time)’dir.



    a. En İyi Durum İşletim Süresi: Bir algoritma için, maliyet veya karmaşıklık hesaplamalarında en iyi sonucun elde edildiği durumdaki yürütme zamanına denir. Örneğin bir dizide yapılan aramanın en iyi durumu, aranan elemanın dizinin ilk elemanı olmasıdır.

    b. En Kötü Durum İşletim Süresi: Bir algoritma için, maliyet veya karmaşıklık hesaplamalarında tüm olumsuz koşulların oluştuğu durumdaki yürütme zamanına denir. Örneğin, n elemanlı bir listede sıralı arama en kötü ihtimalle (aranan bulunamazsa) n karşılaştırma gerektirecektir. Burada en kötü durum işletim süresi T(n) = n’dir. Sadece en kötü girdi durumu dikkate alındığı için en kötü durum işletim süresi değerini hesaplamak göreceli olarak kolaydır.

    c. Ortalama Durum İşletim Süresi: Bir algoritma için, maliyet veya karmaşıklık hesaplamalarında tüm mümkün girdi değerlerine göre hesaplanan ortalama yürütme zamanına denir. Örneğin, n elemanın herbirinin aranma olasılığının eşit olduğu ve liste dışından başka bir elemanın aranmayacağı varsayıldığında ortalama işletim süresi (n+1)/2’dir. Aranan elemanların listede olmama ihtimali de hesaba katıldığında ortalama işletim süresi [(n+1)/2, n] aralığında olacaktır. Ortalama durum analizi basit varsayımlar yapıldığında bile zordur ve varsayımlar da gerçek performansın iyi tahmin edilememesine neden olabilir.

    2.2. Asimptotik Analiz

    Algoritmaların karşılaştırılmasında girdi boyutu sonsuza yaklaşırken işlem süresinin artışı da dikkate alınabilir. Bunlara asimptotik analiz denilmektedir. Asimptotik analizin en önemli elemanı Büyük-O (Big-O) gösterimidir. Büyük-O gösterimi, fonksiyonların artış oranının üst sınırını belirler. O(f(n)), f(n) fonksiyonundan daha hızlı artmayan fonksiyonlar kümesini gösterir.



    a. Büyük-O Gösterimi

    Büyüklük derecesi (order of magnitude) anlamında kullanılan Büyük-O gösterimi problemin boyutuna bağlı olarak fonksiyonda en hızlı artış gösteren terimi belirler. Örnek olarak:



    f(n) = n4 + 100n2 + 10n + 50 = O(n4)

    fonksiyonunda n’in derecesi n4'tür, yani n’in büyük değerleri için fonksiyonu en fazla n4 etkiler. n’in çok büyük değerleri için n4, 100n2’den, 10n’den ve 50’den çok büyük olacağından daha düşük dereceli terimler dikkate alınmayabilir. Bu diğer terimlerin, işlem süresini etkilemedikleri anlamına gelmez; bu yaklaşım yapıldığında n’in çok büyük değerlerinde önem taşımadıkları anlamına gelir. n, problemin boyutudur. Dizi, yığın, liste, kuyruk, ağaç gibi veri yapılarında eleman sayılarıdır.

    Bir listedeki tüm elemanların dosyaya yazılması için önce dosyanın açılması, sonra elemanların tek tek dosyaya eklenmesi işlemleri yapılır. Bu işlemin süresi listedeki eleman sayısına (n) bağlıdır. İşlemi yapmak için geçen süre n * (bir elemanın dosyaya yazılması için geçen süre) ve dosyanın açılması sırasında geçen sürenin toplamıdır. Algoritmanın zaman karmaşıklığı O(n)’dir. Çünkü, n tane işlem + sadece dosya açılması işlemi vardır. Yüzlerce elemanın dosyaya kaydedildiği düşünülürse, dosya açılması sırasında geçen süre miktarı rahatlıkla ihmal edilebilir. Ama az sayıda eleman varsa dosya açılması sırasında geçen süre miktarı önem taşıyabilir ve toplam süreye katılımındaki yüzdesi daha fazla olur. Büyük-O gösterimi n sayısı büyük değerler alabilen algoritmaların analizinde kullanılır, genelde n sayısının küçük değerlerinde günümüz bilgisayarında işlemler 1 saniyeden daha az sürmektedir.

    Büyük-O gösterimi, algoritmadaki eleman sayısı arttığında sürenin nasıl artacağı hakkında bilgi verir. Algoritma bilgisayarda işletildiğinde sonucun ne kadar sürede alınacağını belirtmez. Bazen de bu tür bir bilgiye gereksinim duyulur. Örnek olarak bir kelime işlemcinin 50 sayfalık bir yazı üzerinde yazım denetimi yapma süresinin birkaç saniye düzeyinden fazla olmaması istenir. Böyle bir bilgi istendiğinde, Büyük-O analizi yerine diğer ölçümler kullanılmalıdır. Program değişik yöntemlere göre kodlanır ve karşılaştırma yapılır. Programın çalıştırılmasından önce ve sonra bilgisayarın saati kaydedilir. İki saat arasındaki fark alınarak geçen süre bulunur. Bu tür bir “Benchmark” testi, işlemlerin belirli bir bilgisayarda belirli bir işlemci ve belirli kaynaklar kullanılarak ne kadar sürdüğünü gösterir.

    Bilgisayarın yaptığı işin programın boyutu ile, örnek olarak satır sayısı ile ilgili olması gerekmez. n elemanlı bir dizideki tüm elemanlara 0 değerini atayan iki program da O(n) olduğu halde kaynak kodlarının satır sayıları oldukça farklıdır:

    Program 1:
    dizi[0] = 0;

    dizi[1] = 0;

    dizi[2] = 0;

    dizi[3] = 0;

    ...

    dizi[n-1] = 0;




    Program 2:
    for (int i=0; i

    dizi[i] = 0;



    1’den n’e kadar olan sayıların toplamını hesaplayan iki kısa program incelenecek olursa:



    Program 1:
    toplam = 0;

    for (int i=0; i

    toplam = toplam + i;


    Program 2:
    toplam = n*(n+1)/2;

    Program 1’in zaman karmaşıklığı O(n)’dir. n=50 olursa programın çalışması sırasında n=5 için harcanan sürenin yaklaşık 10 katı süre harcanacaktır. Program 2’nin zaman karmaşıklığı ise O(1)’dir. n=1 de olsa n=50’de olsa program aynı sürede biter.



    using System;

    namespace ZamanKarma

    {

    class Program

    {

    static void Main()

    {

    double toplam = 0, n=999999999;

    DateTime baslangic, bitis;

    baslangic = DateTime.Now;

    for (double i = 0; i < n; ++i)

    toplam = toplam + i;

    //toplam = n * (n + 1) / 2;

    bitis = DateTime.Now;

    Console.WriteLine(baslangic);

    Console.WriteLine(bitis);

    Console.Write(toplam);

    Console.ReadLine();

    }

    }

    }

    b. Artış Oranı Fonksiyonları

    Yaygın olarak kullanılan bazı artış oranı fonksiyonları Tablo 1’de gösterilmektedir.



    Fonksiyon

    İsim

    1

    Sabit

    log n

    Logaritmik

    n

    Doğrusal

    n log n

    Doğrusal Logaritmik (Linearitmik)

    n2

    Karesel

    nc, c>1

    Çokterimli (Cebirsel)

    cn

    Üssel

    n!

    Faktöriyel


    Tablo 1. Yaygın artış oranları

    O(1) sabit zamanı temsil etmektedir. Örnek olarak n elemanlı bir dizinin i. elemanına bir değer atanması O(1)’dir. Çünkü sadece 1 elemana indisinden doğrudan erişilmektedir.

    O(n) doğrusal zamanı temsil etmektedir. Örneğin n elemanlı bir dizinin tüm elemanlarının ekrana yazdırılması O(n)’dir.

    O(log n) logaritmik zamanı temsil etmektedir. O(1)’den fazla O(n)’den azdır. Örneğin sıralı bir listenin elemanları içinde ikili arama (binary search) uygulanarak belirli bir değerin aranması log2 n sayıda işlem gerektirdiğinden O(log n)’dir.

    O(n log n) doğrusal logaritmik (linearitmik) zamanı temsil etmektedir. O(n)’den fazla O(n2)’den azdır. Bunlara sözde doğrusal veya üst doğrusal zaman da denilmektedir. Bazı hızlı sıralama algoritmaları n.log2 n sayıda işlem gerektirdiğinden O(n log n)’dir.

    O(n2) karesel (ikinci dereceli) zamanı temsil etmektedir. Basit sıralama algoritmalarının birçoğu (seçerek sıralama, kabarcık sıralaması gibi) O(n2)’dir.

    O(nc) çokterimli (cebirsel) zamanı temsil etmektedir. Burada c>1 olan sabit bir sayıdır. Örneğin üç boyutlu bir dizideki her elemanın değerini artıran algoritma O(n3)’tür.

    O(cn) üssel (geometrik), O(n!) ise faktöriyel zamanı temsil etmektedir, bunlar hızlıca çok büyük değerlere ulaşırlar.



    c. Pratikte Karmaşıklık

    Değişik artış fonksiyonlarının aldıkları değerlere göre sonuçları Tablo 2’de gösterilmiştir.



    n

    log2 n

    n.log2 n

    n2

    n3

    2n

    1

    0

    0

    1

    1

    2

    2

    1

    2

    4

    8

    4

    3

    1,58

    4,75

    9

    27

    8

    4

    2

    8

    16

    64

    16

    5

    2,32

    11,61

    25

    125

    32

    6

    2,58

    15,51

    36

    216

    64

    7

    2,81

    19,65

    49

    343

    128

    8

    3

    24

    64

    512

    256

    9

    3,17

    28,53

    81

    729

    512

    10

    3,32

    33,22

    100

    1000

    1024

    11

    3,46

    38,05

    121

    1331

    2048

    12

    3,58

    43,02

    144

    1728

    4096

    13

    3,7

    48,11

    169

    2197

    8192

    14

    3,81

    53,3

    196

    2744

    16384

    15

    3,91

    58,6

    225

    3375

    32768

    16

    4

    64

    256

    4096

    65536

    Tablo 2. Değişik f(n) fonksiyonların değişik n girdi boyutlarına göre değerleri

    Bir programın işletimi n3 adım sürüyorsa ve n=1000 ise, program 10003 adım sürecek demektir. Yani 1 000 000 000 (bir milyar) adım. Kullanılan bilgisayar saniyede 1 000 000 000 adımı gerçekleştirebilecek kadar hızlı ise bu program tam 1 saniye sürecektir.

    Tablo 2’deki fonksiyonlardan elde edilmiş bir grafik Şekil 1 ve Şekil 2’de görülmektedir.



    Şekil 1. 2n, n3, n2, n.log2 n, n, log2 n fonksiyonların grafikleri


    Şekil 2. n, log2 n ve n.log2 n fonksiyonların grafikleri

    2.3. Algoritma Analizi

    Bir algoritmanın çalışma süresini hesaplamak için yapılan araştırmaya algoritma analizi denir. Aşağıdaki örnek üzerinde çalışma zamanı algoritma analizi ile hesaplanmıştır.


    Tablo 3’te 1’den 10’a kadar olan tamsayıların toplamını hesaplayan algoritmada, herbir komutun kaç birim zaman aldığı, frekansı (kaç kere çalıştığı) ve harcadığı toplam zaman belirtilmiştir. Yapılan işlemlerin sonunda harcanan toplam zaman 53 birim olarak bulunmuştur.





    Birim Zaman

    Frekans

    Toplam Zaman

    toplam = 0;

    1

    1

    1

    i = 1;

    1

    1

    1

    while (i £ 10) {

    1

    11

    11

    toplam=toplam+i;

    2

    10

    20

    i=i+1;

    2

    10

    20

    }







    53


    Tablo 3.
    1’den 10’a kadar olan tamsayıları toplayan algoritmanın çalışma zamanı
    1’den n’e kadar olan tamsayıların toplamı için çalışma zamanı da Tablo 4’te hesaplamıştır.




    Birim Zaman

    Frekans

    Toplam Zaman

    toplam = 0;

    1

    1

    1

    i = 1;

    1

    1

    1

    while (i £ n) {

    1

    n+1

    n+1

    toplam=toplam+i;

    2

    n

    2n

    i=i+1;

    2

    n

    2n

    }







    5n+3


    Tablo 4.
    1’den n’e kadar tamsayıyı toplayan algoritmanın çalışma zamanı

    Algoritmaların analizinde karmaşıklığı Büyük-O gösteriminde bulmak için bazı kurallar uygulanmaktadır. Bunlar;

    Bir döngü için yürütme zamanı döngünün içindeki (test dahil) deyimlerin sayısı ile döngünün tekrarlanma sayısının çarpımı kadardır.


    f(n)
    f(n) . g(n)

    İç içe döngülerde toplam yürütme zamanını bulmak için gereken analiz içten dışa doğru yapılır. Önce en içteki döngünün toplam yürütme zamanı bulunur. Bir dış döngü yürütme zamanına katıldığında, iç döngülerin yürütme zamanı ile eklenen dış döngünün boyutu çarpılır.

    f
    O(n3)
    or (i=0; i<n; i++)

    f
    O(n2)

    or (j=0; j<n*n; j++)

    k=k+1; à O(1)

    Ardışık deyimlerin toplam yürütme zamanını bulabilmek için toplama yapılır ve en büyük katsayılı değer alınır. Aşağıdaki örnekte de görüldüğü gibi O(1) + O(n) + O(n2) toplamı yerine sadece O(n2) alınmıştır, diğerleri ihmal edilmiştir.

    f
    O(1)
    or (i=0; i<n; i++) {

    k=0;


    O(n2)

    for (j=0; j<n*n; j++)


    O(n2)



    O(n3)
    k=k+1;

    O(n)
    for (l=0; l<n; l++)

    t=5;

    }


    Eğer/Değilse (if/else) gibi deyimlerde toplam yürütme zamanı koşulun hem kabul hem de ret bölümüne girdiği kabul edilerek hesaplanır, yani kabul ve ret süreleri toplanır ve sonuç olarak durumun maksimum olduğu değer alınmış olur.
    if (koşul) {


    T1(n)


    ………..

    ……….


    ……….

    }


    T1(n) + T2(n) = maksimum{T1(n), T2(n)}

    else {



    T2(n)
    ………..

    ……….


    ……….

    }

    Yapısı maksimum n = 2k işlem içeren (sürekli ortadan ikiye bölünen) döngü ya da tekrarlamalı (rekürsif) fonksiyondan oluşan algoritmalarda zaman karmaşıklığı O(log n)’dir. Bu duruma örnek olarak aşağıda ikili arama algoritması verilmiştir.



    int ikili_arama(A, aranan, n) {

    int kucuk = 0, orta, buyuk = n - 1; ¾¾¾¾¾¾¾¾® O(1)



    while (kucuk £ buyuk) {

    orta = (kucuk + buyuk) / 2; ¾¾® O(1)

    if (A[orta] < aranan) ¾¾¾¾® O(1)


    O(1)

    O(log n)

    O(log n)
    kucuk = orta + 1;

    if (A[orta] > aranan) ¾¾¾¾® O(1)



    buyuk = orta - 1;

    if (A[orta] == aranan) ¾¾¾® O(1)

    return orta;

    }

    return -1; // bulunamadı ¾¾¾¾¾¾¾¾¾¾¾¾® O(1)



    }









        Ana sayfa


    1. Algoritmaların Karşılaştırılması

    Indir 97.9 Kb.