تالار گفتمان مانشت

در جستجوی دو دو یی ، اگر Sn و Pn به ترتیب میانگین مقایسات لازم در جستجوی موفق و ناموفق باشند آنگاه رابطه زیر برقرار است :

Sn=[(1+1/n)Pn]-1

چطور این رابطه اثبات می شود ؟؟؟؟؟؟؟

بین S و U رابطه زیر برقراره:
[tex]S(n)=\frac{(n 1)U(n)-n}{n}[/tex]
حالا اگر اینو ساده کنید به همون قرمولی که نوشتید می‌رسید.

اطلاعات بیشتر => The art of computer programming 3rd volume

(02 آذر 1391 08:54 ب.ظ)mfXpert نوشته شده توسط: [ -> ]بین S و U رابطه زیر برقراره:
[tex]S(n)=\frac{(n 1)U(n)-n}{n}[/tex]
حالا اگر اینو ساده کنید به همون قرمولی که نوشتید می‌رسید.

اطلاعات بیشتر => The art of computer programming 3rd volume

ممنون از پاسخ شما . به نظرم فرمول ارائه شده توسط شما درواقع مرحله آخر اثبات رابطه ای هست که بنده اشاره کردم .
چیزی که مهم هست نحوه رسیدن به فرمول شماست تا در نهایت با ساده کردن به فرمول نهایی برسیم .
اینکه فرمول کلی برای Sn چیست ؟ فرمول کلی برای Un چیست ؟ و چه ارتباطی با یکدیگر دارند و در نهایت رسیدن به فرمول آخر .

درضمن خیلی به دنبال منبعی که شما معرفی کردید گشتم اما موفق به پیدا کردن نشدم .

لطف می کنید بهتر راهنمایی کنید و یا اینکه اثبات کامل رو برام بگید ؟

بینهایت متشکرم

(03 آذر 1391 12:39 ق.ظ)mahdibml83 نوشته شده توسط: [ -> ]

(02 آذر 1391 08:54 ب.ظ)mfXpert نوشته شده توسط: [ -> ]بین S و U رابطه زیر برقراره:
[tex]S(n)=\frac{(n 1)U(n)-n}{n}[/tex]
حالا اگر اینو ساده کنید به همون قرمولی که نوشتید می‌رسید.

اطلاعات بیشتر => The art of computer programming 3rd volume

ممنون از پاسخ شما . به نظرم فرمول ارائه شده توسط شما درواقع مرحله آخر اثبات رابطه ای هست که بنده اشاره کردم .
چیزی که مهم هست نحوه رسیدن به فرمول شماست تا در نهایت با ساده کردن به فرمول نهایی برسیم .
اینکه فرمول کلی برای Sn چیست ؟ فرمول کلی برای Un چیست ؟ و چه ارتباطی با یکدیگر دارند و در نهایت رسیدن به فرمول آخر .

درضمن خیلی به دنبال منبعی که شما معرفی کردید گشتم اما موفق به پیدا کردن نشدم .

لطف می کنید بهتر راهنمایی کنید و یا اینکه اثبات کامل رو برام بگید ؟

بینهایت متشکرم

سلام اصل این اثبات در کتاب طراحی الگوریتم هورویتز آمده ولی میتونی تو کتاب طراحی هادی یوسفی پیداش کنی
خودم اینترنتم داره قطع میشه وگرنه برات توضیح میدادم. (انشالله صبح توضیح میدم)

اگر جستجوی دودویی رو با یه درخت دودویی نمایش بدیم
گره‌های داخلی جستجوی موفق هستن
و گره‌های خارجی(برگ) جستجوی ناموفق

مسافت ریشه تا گره داخلی=I
مسافت ریشه تا برگ=E
که طبق فرمول زیر باهم رابطه دارن:E=I+2n
N:تعداد گره‌های داخلی

رابطه‌های زیر هم برقرار هست:
sn=I+N/n
en=E/N+1
که ساده کنی به فرمول اصلی میرسی