SORU:
İlk N doğal sayının saklanması (işaretsiz olarak) kaç bit harcayacaktır? örn. 5 101 olarak 3, 77 ise 1001101 olarak 7 bit kullanacaktır.YANIT:
Aslında bu Σ_{i=1}^{N}{\ceil{\log i}} toplamını bulma sorusu (0'ı dahil edip etmeyeceğimize göre 1 eklenebilir), öyleyse bunu özel bir durum olan N=2^k vaziyeti için inceleyelim.Bu durumda 1'den k'a kadar olan sayıları topluyoruz, öyle ki bu sayılardan toplam N adet var. Dağılımı da i sayısından 2^(i-1) ve 2^i arasındaki kadar olacak şekilde: yani 2^(i-1). Dolayısıyla toplam farklı bir ifade kazandı:
S(k) = Σ_{i=1}^{k}{i2^(i-1)}
Ancak bu da bir çırpıda çözülebilir bir toplam gibi görünmedi. O noktada, \int xe^x dx = (x-1)e olmasından yola çıkarak benzer bir şekilde F(k)=Σ_{i=1}^{k}{i2^i} için Ak+B2^k+Ck2^k+D şeklinde bir gösterim olup olmayacağını merak ettim. Olduğunu varsayıp F(k+1)-F(k) farkını inceledim ve bunu (k+1)2^(k+1)'e eşitlemeye çalıştım. Dikkat edilmesi gereken noktalardan biri bu sırada D için hiç bir şey söyleyemeyeceğimiz. Bunun sonunda çıkan eşitlik:
A + (B+C)2^k + C(k+1)2^k = (k+1)2^(k+1)
ve bu her k için geçerli olacak, ve k ve 2^k terimleri lineer bağımsız, yani sonunda
- A = 0
- B+C = 0
- C = 2
sonucuna ulaştık. Buradan F(k) = (k-1)2^(k+1)+D ve F(1)=2 kullanılarak D=2 bulunur ve ufak manipülasyonlarla S(k) = (k-1)2^k+1 bulunur, son olarak da k sayısını N=2^k olacak şekilde hatırlayarak bunun (logN-1)N+1 olduğu görülür. Bir sonraki adım, hafıza gereksiniminin O(NlogN) olduğunu söylemek. (Bu adım biraz havada, kabul ediyorum, lineer bağımsızlık argümanı gibi)
Alternatif yol
Bu yazıyı yazarken F(k)'i hesaplamak için hiç bir varsayıma ihtiyaç duymayan başka bir yol fark ettim, ekliyorum:
- İlk olarak fark edilmeli ki her k için F(k)=2S(k)
- Ancak indis değiştirip toplamı ayırırsak, S(k) = Σi2^(-1)
= Σ(i-1)2^(i-1) + Σ2^(i-1) = Σi2^i + Σ2^i
= F(k-1) + 2^k -1 - Bunun bize söylediği şey, F(k) = 2F(k-1) + 2^(k+1) -1,
- ve ayrıca biliyoruz ki F(k) = F(k-1) + k2^k
- Buradan F(k-1) sadeleştirildiğinde F(k-1) = (k-2)2^k+2 çıkıyor, ki bu da aradığımız şeydi.
