۰
subtitle
ارسال: #۱
سوال طراحی الگوریتم (Binary search)
در جستجوی دو دو یی ، اگر Sn و Pn به ترتیب میانگین مقایسات لازم در جستجوی موفق و ناموفق باشند آنگاه رابطه زیر برقرار است :
Sn=[(1+1/n)Pn]-1
چطور این رابطه اثبات می شود ؟؟؟؟؟؟؟
Sn=[(1+1/n)Pn]-1
چطور این رابطه اثبات می شود ؟؟؟؟؟؟؟
۲
ارسال: #۲
سوال طراحی الگوریتم (Binary search)
اگر جستجوی دودویی رو با یه درخت دودویی نمایش بدیم
گره‌های داخلی جستجوی موفق هستن
و گره‌های خارجی(برگ) جستجوی ناموفق
مسافت ریشه تا گره داخلی=I
مسافت ریشه تا برگ=E
که طبق فرمول زیر باهم رابطه دارن:E=I+2n
N:تعداد گره‌های داخلی
رابطه‌های زیر هم برقرار هست:
sn=I+N/n
en=E/N+1
که ساده کنی به فرمول اصلی میرسی
گره‌های داخلی جستجوی موفق هستن
و گره‌های خارجی(برگ) جستجوی ناموفق
مسافت ریشه تا گره داخلی=I
مسافت ریشه تا برگ=E
که طبق فرمول زیر باهم رابطه دارن:E=I+2n
N:تعداد گره‌های داخلی
رابطه‌های زیر هم برقرار هست:
sn=I+N/n
en=E/N+1
که ساده کنی به فرمول اصلی میرسی
۰
ارسال: #۳
RE: سوال طراحی الگوریتم (Binary search)
بین S و U رابطه زیر برقراره:
[tex]S(n)=\frac{(n 1)U(n)-n}{n}[/tex]
حالا اگر اینو ساده کنید به همون قرمولی که نوشتید می‌رسید.
اطلاعات بیشتر => The art of computer programming 3rd volume
[tex]S(n)=\frac{(n 1)U(n)-n}{n}[/tex]
حالا اگر اینو ساده کنید به همون قرمولی که نوشتید می‌رسید.
اطلاعات بیشتر => The art of computer programming 3rd volume
ارسال: #۴
RE: سوال طراحی الگوریتم (Binary search)
(۰۲ آذر ۱۳۹۱ ۰۸:۵۴ ب.ظ)mfXpert نوشته شده توسط: بین S و U رابطه زیر برقراره:
[tex]S(n)=\frac{(n 1)U(n)-n}{n}[/tex]
حالا اگر اینو ساده کنید به همون قرمولی که نوشتید می‌رسید.
اطلاعات بیشتر => The art of computer programming 3rd volume
ممنون از پاسخ شما . به نظرم فرمول ارائه شده توسط شما درواقع مرحله آخر اثبات رابطه ای هست که بنده اشاره کردم .
چیزی که مهم هست نحوه رسیدن به فرمول شماست تا در نهایت با ساده کردن به فرمول نهایی برسیم .
اینکه فرمول کلی برای Sn چیست ؟ فرمول کلی برای Un چیست ؟ و چه ارتباطی با یکدیگر دارند و در نهایت رسیدن به فرمول آخر .
درضمن خیلی به دنبال منبعی که شما معرفی کردید گشتم اما موفق به پیدا کردن نشدم .
لطف می کنید بهتر راهنمایی کنید و یا اینکه اثبات کامل رو برام بگید ؟
بینهایت متشکرم
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close