این رابطه بازگشتی رو کسی میتونه حل کنه؟
[tex]T(n)=2T(\frac{n}{2}) \frac{n}{logn}[/tex]
مسئله من زانی هست که درختشو رسم می کنم.
مسئله های دیگه راحت میشه تعیین کردن مقدار i یا بعبارتی ارتفاع درخت چنده.
اینو نمی دونم چطوری باید تعیین کنم
هر راه حلی هم که نگاه کردم همشون کپی هم بودن و من چیزی دستگیرم نشد...
(27 مهر 1390 09:33 ب.ظ)si.mozhgan نوشته شده توسط: [ -> ]بعد از کشیدن درخت برای بدست آوردن i
کجا مشکل دارین؟
مگه نباید کل رابطه رو برابر یک قرار بدیم؟
n رو در صورت هیچی در نظر نگیریم؟
من نمی دونم مشکلتون کجاست درخت رو کشیدم وضمیمه می کنم ارتفاع درخت هم lgn است
که از روی درخت روابط زیر رو داریم
[tex]\frac{n}{lgn} \frac{n}{lgn-1} \frac{n}{lgn-2} ...=n(\frac{1}{lgn} \frac{1}{lgn-1} \frac{1}{lgn-2} ...)=nlglgn[/tex]
ببینید مسئله من اینجاس که اگر قرار باشه [tex]\frac{n}{logn-i}[/tex] رو برابر یک قرار بدهیم.
پس i چطوری حساب میشه؟
برای یافتن ارتفاع درخت شما باید عبارت داخل پرانتز جلوی T رو پس از i مرحله مساوی یک بگذارید.
یعنی [tex]\LARG \frac{n}{2^{i}}=1\rightarrow i=Log n[/tex]
(البته من سطح ریشه رو صفر فرض کردم)
--------------------------------------------------------------------------------------------
اون جوابی هم که دوستمون ahmadnouri داده اند در واقع همان جمع هزینه های سطوح درخت می باشد که هدف ما هم همینه.
و من هم تایید می کنم.
متوجه شدم:
ببینید داریم:
[tex]\frac{n}{2^{i}}=1[/tex]
[tex]i = logn[/tex]
[tex]\sum_{i=0}^{logn-1}\frac{n}{logn-i}[/tex]
حالا علت اینکه سیگما تا logn-1 هستش اینه که اگه تا logn باشه مخرج کسر صفر میشه و کسر تعریف نشده خواهد بود
(02 آبان 1390 11:14 ب.ظ)yaali نوشته شده توسط: [ -> ] (02 آبان 1390 11:00 ب.ظ)sasanlive نوشته شده توسط: [ -> ] (02 آبان 1390 10:30 ب.ظ)yaali نوشته شده توسط: [ -> ] (02 آبان 1390 09:52 ب.ظ)پشتکار نوشته شده توسط: [ -> ]
دلیل [tex]logn-1[/tex] در بالای سیگما اینه که ارتفاع درخت [tex]log\frac{n}{2}[/tex] هستش که [tex]log\frac{n}{2}=logn log\frac{1}{2}=logn-1[/tex].
اینو سوال تو یه topic دیگه هم مطرح شده بود که البته قبلا واسه پیشگیری اونو تو topic زیر توضیح داده بودم . زیاد سوالو گندش نکنین.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
.
دوست عزیزم بحث بزرگ کردن سوال نیست . بحث فهمیدنه .
دلیل شما برای اون "منهای یک" قانع کننده نیست چون:
ارتفاع درخت i= Logn هستش.
بله ارتفاع logn هست . به دلیل اینکه سریع جواب میدم بعضی اوقات احتمال اشتباه هست.
دلیل مقدار بالای سیگما اینست که مجموع هزینه در سطح آخر برابر n است.
[tex]\frac{n}{logn-i}=n \Rightarrow logn-i=1 \Rightarrow i=logn-1[/tex]
برای همین مقدار بالای سیگما را تا logn-1 گرفت.
(03 آبان 1390 01:36 ق.ظ)sasanlive نوشته شده توسط: [ -> ]دلیل مقدار بالای سیگما اینست که مجموع هزینه در سطح آخر برابر n است.
[tex]\frac{n}{logn-i}=n \Rightarrow logn-i=1 \Rightarrow i=logn-1[/tex]
برای همین مقدار بالای سیگما را تا logn-1 گرفت.
این راه حل رو از کجا آوردید؟
مجموع هزینه در سطح آخر برابر n است. چطوری؟
(04 آبان 1390 09:49 ق.ظ)پشتکار نوشته شده توسط: [ -> ][quote='sasanlive' pid='50982' dateline='1319490371']
این راه حل رو از کجا آوردید؟
مجموع هزینه در سطح آخر برابر n است. چطوری؟
چون این رابطه بازگشتی یه درخت کامل رو تشکیل میده و چون سطح ریشه رو از صفر در نظر گرفتیم. پس در سطح آخر[tex]2^{i}[/tex] گره داره که هزینه هرکدومشون ۱ هست. و ارتفاع درخت هم [tex]i=logn[/tex] هست. پس مجموع هزینه سطح آخر میشه:
[tex]2^{i}*1=2^{logn}*1=n[/tex]