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

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

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

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

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

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (acehreli):

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

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]