این رابطه بازگشتی رو کسی میتونه حل کنه؟
[tex]T(n)=2T(\frac{n}{2}) \frac{n}{logn}[/tex]
مسئله من زانی هست که درختشو رسم می کنم.
مسئله های دیگه راحت میشه تعیین کردن مقدار i یا بعبارتی ارتفاع درخت چنده.
اینو نمی دونم چطوری باید تعیین کنم
هر راه حلی هم که نگاه کردم همشون کپی هم بودن و من چیزی دستگیرم نشد...
بعد از کشیدن درخت برای بدست آوردن i
[attachment=1484]
کجا مشکل دارین؟
(۲۷ مهر ۱۳۹۰ ۰۹:۳۳ ب.ظ)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 باشه مخرج کسر صفر میشه و کسر تعریف نشده خواهد بود
(۰۲ آبان ۱۳۹۰ ۰۹:۵۲ ب.ظ)پشتکار نوشته شده توسط: متوجه شدم:
ببینید داریم:
[tex]\frac{n}{2^{i}}=1[/tex]
[tex]i = logn[/tex]
[tex]\sum_{i=1}^{logn-1}\frac{n}{logn-i}[/tex]
حالا علت اینکه سیگما تا logn-1 هستش اینه که اگه تا logn باشه مخرج کسر صفر میشه و کسر تعریف نشده خواهد بود
روی سیکما i از صفر شروع می شه نه از یک.( سطح ریشه صفره)
در مورد اون "منهای یک" که در Lgn -1 بالای سیکما هستش هم فکر می کنم باید دلیل بهتری (یک دلیل ساختمان داده ای) برای اومدنش داشته باشه.
چون بازه‌ی سیکما باید از i=0 (سطح صفرم) تا سطح آخر( یعنی i )باشه و i هم مساوی Log n هستش.
(۰۲ آبان ۱۳۹۰ ۱۱:۰۰ ب.ظ)sasanlive نوشته شده توسط:(02 آبان ۱۳۹۰ ۱۰:۳۰ ب.ظ)yaali نوشته شده توسط:(02 آبان ۱۳۹۰ ۰۹:۵۲ ب.ظ)پشتکار نوشته شده توسط:
دلیل [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 هستش.
(۰۲ آبان ۱۳۹۰ ۱۱:۱۴ ب.ظ)yaali نوشته شده توسط:بله ارتفاع logn هست . به دلیل اینکه سریع جواب میدم بعضی اوقات احتمال اشتباه هست.(02 آبان ۱۳۹۰ ۱۱:۰۰ ب.ظ)sasanlive نوشته شده توسط:(02 آبان ۱۳۹۰ ۱۰:۳۰ ب.ظ)yaali نوشته شده توسط:(02 آبان ۱۳۹۰ ۰۹:۵۲ ب.ظ)پشتکار نوشته شده توسط:
دلیل [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 هستش.
دلیل مقدار بالای سیگما اینست که مجموع هزینه در سطح آخر برابر n است.
[tex]\frac{n}{logn-i}=n \Rightarrow logn-i=1 \Rightarrow i=logn-1[/tex]
برای همین مقدار بالای سیگما را تا logn-1 گرفت.
(۰۳ آبان ۱۳۹۰ ۰۱:۳۶ ق.ظ)sasanlive نوشته شده توسط: دلیل مقدار بالای سیگما اینست که مجموع هزینه در سطح آخر برابر n است.
[tex]\frac{n}{logn-i}=n \Rightarrow logn-i=1 \Rightarrow i=logn-1[/tex]
برای همین مقدار بالای سیگما را تا logn-1 گرفت.
این راه حل رو از کجا آوردید؟
مجموع هزینه در سطح آخر برابر n است. چطوری؟
(۰۴ آبان ۱۳۹۰ ۰۹:۴۹ ق.ظ)پشتکار نوشته شده توسط: [quote='sasanlive' pid='50982' dateline='1319490371']چون این رابطه بازگشتی یه درخت کامل رو تشکیل میده و چون سطح ریشه رو از صفر در نظر گرفتیم. پس در سطح آخر[tex]2^{i}[/tex] گره داره که هزینه هرکدومشون ۱ هست. و ارتفاع درخت هم [tex]i=logn[/tex] هست. پس مجموع هزینه سطح آخر میشه:
این راه حل رو از کجا آوردید؟
مجموع هزینه در سطح آخر برابر n است. چطوری؟
[tex]2^{i}*1=2^{logn}*1=n[/tex]