انجمنصفحه اولجستجوی انجمن

[پشتکار]

این رابطه بازگشتی رو کسی میتونه حل کنه؟

[tex]T(n)=2T(\frac{n}{2}) \frac{n}{logn}[/tex]


مسئله من زانی هست که درختشو رسم می کنم.
مسئله های دیگه راحت میشه تعیین کردن مقدار i یا بعبارتی ارتفاع درخت چنده.
اینو نمی دونم چطوری باید تعیین کنم
هر راه حلی هم که نگاه کردم همشون کپی هم بودن و من چیزی دستگیرم نشد...

[si.mozhgan]

بعد از کشیدن درخت برای بدست آوردن i




کجا مشکل دارین؟

[پشتکار]

(۲۷ مهر ۱۳۹۰ ۰۹:۳۳ ب.ظ)si.mozhgan نوشته شده توسط:  بعد از کشیدن درخت برای بدست آوردن i



کجا مشکل دارین؟

مگه نباید کل رابطه رو برابر یک قرار بدیم؟
n رو در صورت هیچی در نظر نگیریم؟

[ahmadnouri]

من نمی دونم مشکلتون کجاست درخت رو کشیدم وضمیمه می کنم ارتفاع درخت هم 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 چطوری حساب میشه؟

[- rasool -]

برای یافتن ارتفاع درخت شما باید عبارت داخل پرانتز جلوی 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 باشه مخرج کسر صفر میشه و کسر تعریف نشده خواهد بود

[- rasool -]

(۰۲ آبان ۱۳۹۰ ۰۹:۵۲ ب.ظ)پشتکار نوشته شده توسط:  متوجه شدم:
ببینید داریم:

[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 هستش.

[- rasool -]

(۰۲ آبان ۱۳۹۰ ۱۱:۰۰ ب.ظ)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 هستش.

[sasanlive]

(۰۲ آبان ۱۳۹۰ ۱۱:۱۴ ب.ظ)yaali نوشته شده توسط:  

(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 هستش.

بله ارتفاع 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 است. چطوری؟

[sasanlive]

(۰۴ آبان ۱۳۹۰ ۰۹:۴۹ ق.ظ)پشتکار نوشته شده توسط:  [quote='sasanlive' pid='50982' dateline='1319490371']

این راه حل رو از کجا آوردید؟
مجموع هزینه در سطح آخر برابر n است. چطوری؟

چون این رابطه بازگشتی یه درخت کامل رو تشکیل میده و چون سطح ریشه رو از صفر در نظر گرفتیم. پس در سطح آخر[tex]2^{i}[/tex] گره داره که هزینه هرکدومشون ۱ هست. و ارتفاع درخت هم [tex]i=logn[/tex] هست. پس مجموع هزینه سطح آخر میشه:

[tex]2^{i}*1=2^{logn}*1=n[/tex]