Forum: Ders Arası RSS
The Algorithm Design Manual, problem 2-45
Kaç kere tmp = A[i] atama işlemi
acehreli (Moderatör) #1
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: The Algorithm Design Manual, problem 2-45
Aşağıdaki algoritma A[0,...,N] dizisindeki elemanların en küçüğünü bulmaktadır. En küçük değeri saklayacak olan tmp adında bir değişken tanımlayın. A[0]'dan başlayın ve tmp'i sırayla A[1], A[2], ..., ve A[N] ile karşılaştırın. A[i] < tmp olduğunda tmp = A[i] yapın. Kaç kere tmp = A[i] atama işlemi yapılacağı beklenmelidir?

Ali
acehreli (Moderatör) #2
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
A dizisindeki sayılar zaten sıralı olduklarında tmp değişkenini hiç değiştirmemiz gerekmez çünkü A[0] en küçük değerdir ve tmp onunla ilklenmiştir.

En kötü durum A dizisinin büyükten küçüğe doğru sıralı olduğu durumdur. O zaman tmp değişkeninin değeri N-1 kere değiştirilir çünkü hep geri kalan sayılardan daha büyük değerdedir.

Ortalamada ise log(N) kere değiştiğini hem daha önce benzer algoritmalar için duyduğumdan biliyorum hem de aşağıdaki deneyden görüyorum ama henüz ;) nedenini açıklayamıyorum. Program, farklı uzunluktaki rasgele sıralanmış sayılarla deneyler yapıyor ve tmp'in log(N) kere değiştiğini gösteriyor:
/* Sayıların en küçük olanını döndürür. Bu işlem sırasında aday sayıyı kaç
 * kere değiştirdiği bilgisini de üretir. */
int enKüçüğü(int[] sayılar, ref size_t sayaç)
{
    int tmp = sayılar[0];
    sayılar = sayılar[1..$];
 
    foreach (sayı; sayılar) {
        if (sayı < tmp) {
            tmp = sayı;
            ++sayaç;
        }
    }
 
    return tmp;
}
 
import std.stdio;
import std.range;
import std.random;
import std.math;
 
void main()
{
    enum üsSınırı = 20;
    enum deneyAdedi = 30;
 
    /* En küçüğü bulunacak olan sayıların adetlerine karşılık bu işlem
     * sırasında kaç kere fikir değiştirildiğini tutar. */
    double[size_t] histogram;
 
    foreach (üs; 0 .. üsSınırı + 1) {
        const adet = 2^^üs;
 
        writef("üs: %s, adet: %s, ortalama değişim: ?", üs, adet);
        stdout.flush();
 
        /* Bunu sonra deney adedine bölerek bu uzunluk için ortalama sayaç
         * belirleyeceğiz. */
        double toplamSayaç = 0;
 
        foreach (deney; 0 .. deneyAdedi) {
            auto sayılar = iota(adet).array;
            randomShuffle(sayılar);
 
            size_t sayaç = 0;
            enKüçüğü(sayılar, sayaç);
 
            toplamSayaç += sayaç;
        }
 
        const ortalamaSayaç = toplamSayaç / deneyAdedi;
        histogram[adet] = ortalamaSayaç;
 
        writefln("\rüs: %s, adet: %s, ortalama değişim: %s",
                 üs, adet, ortalamaSayaç);
    }
 
    writeln("\nSonuçlar:");
    writefln("\n%10s%20s%20s",
             "sayı adedi"d, "deney ortalaması"d, "log(adet)"d);
    foreach (adet; histogram.keys.sort) {
        writefln("%10s%20.2f%20.2f", adet, histogram[adet], log(adet));
    }
}
Bir çıktısı:

...
sayı adedi    deney ortalaması           log(adet)
         1                0.00                0.00
         2                0.37                0.69
         4                1.33                1.39
         8                1.83                2.08
        16                2.07                2.77
        32                3.23                3.47
        64                3.40                4.16
       128                4.70                4.85
       256                4.73                5.55
       512                5.83                6.24
      1024                6.03                6.93
      2048                6.77                7.62
      4096                7.93                8.32
      8192                9.83                9.01
     16384                8.83                9.70
     32768               10.03               10.40
     65536               10.73               11.09
    131072               11.50               11.78
    262144               11.83               12.48
    524288               12.00               13.17
   1048576               12.53               13.86

Ali
acehreli (Moderatör) #3
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Ortalamada neden log(N) olduğu açıkmış; biraz düşününce buldum. :)

İlk sayının en küçük olduğunu varsayarak başlıyoruz. İkinci sayıda tmp'in değerini değiştirme olasılığı 1/2'dir çünkü bu ikinci sayı ya birinciden küçüktür ya da değildir. Üçüncü sayıya geldiğimizde tmp'i değiştirme olasılığı 1/3'tür çünkü o ana kadar 3 sayıya bakmış durumdayız; içlerinden en küçüğünün üçüncü olması 1/3... Aynı biçimde, son elemana geldiğimizde tmp'i değiştirme olasılığı 1/N'dir çünkü en küçük sayını en sonda olma olasılığı 1/N'dir.

tmp'i toplam değiştirme adedi o olasılıkların toplamıdır: 1/2 + 1/3 + ... 1/N. O da logaritmanın seri açılımından başka bir şey değil.

Ali
acehreli (Moderatör) #4
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
acehreli:
1/2 + 1/3 + ... 1/N. O da logaritmanın seri açılımından başka bir şey değil.

Söylediğim şey tamamen uydurma. :)

Aslında yukarıdaki (H(N) - 1)'dir çünkü N'inci harmonik sayı şudur: 1/1 + 1/2 + 1/3 + ... 1/N.

Ama olsun, açıklamamda bir değişiklik olmuyor çünkü (H(N) - 1) değeri de yaklaşık olarak log(N)'dir.

Ali
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Forum: Ders Arası RSS
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-21, 11:20:39 (UTC -08:00)