تالار گفتمان مانشت
یه سوال بازگشتی از قضیه اصلی - نسخه‌ی قابل چاپ

یه سوال بازگشتی از قضیه اصلی - پشتکار - ۲۷ مهر ۱۳۹۰ ۰۸:۰۶ ب.ظ

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

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


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

RE: یه سوال بازگشتی از قضیه اصلی - si.mozhgan - 27 مهر ۱۳۹۰ ۰۹:۳۳ ب.ظ

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

[attachment=1484]

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

RE: یه سوال بازگشتی از قضیه اصلی - پشتکار - ۲۹ مهر ۱۳۹۰ ۱۱:۵۱ ب.ظ

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



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

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

RE: یه سوال بازگشتی از قضیه اصلی - ahmadnouri - 30 مهر ۱۳۹۰ ۱۰:۴۳ ب.ظ

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

RE: یه سوال بازگشتی از قضیه اصلی - پشتکار - ۰۱ آبان ۱۳۹۰ ۰۹:۳۸ ب.ظ

ببینید مسئله من اینجاس که اگر قرار باشه [tex]\frac{n}{logn-i}[/tex] رو برابر یک قرار بدهیم.
پس i چطوری حساب میشه؟

یه سوال بازگشتی از قضیه اصلی - - rasool - - 01 آبان ۱۳۹۰ ۱۰:۰۷ ب.ظ

برای یافتن ارتفاع درخت شما باید عبارت داخل پرانتز جلوی T رو پس از i مرحله مساوی یک بگذارید.

یعنی [tex]\LARG \frac{n}{2^{i}}=1\rightarrow i=Log n[/tex]

(البته من سطح ریشه رو صفر فرض کردم)

--------------------------------------------------------------------------------------------
اون جوابی هم که دوستمون ahmadnouri داده اند در واقع همان جمع هزینه های سطوح درخت می باشد که هدف ما هم همینه.
و من هم تایید می کنم.

RE: یه سوال بازگشتی از قضیه اصلی - پشتکار - ۰۲ آبان ۱۳۹۰ ۰۹:۵۲ ب.ظ

متوجه شدم: Smile
ببینید داریم:

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

RE: یه سوال بازگشتی از قضیه اصلی - - rasool - - 02 آبان ۱۳۹۰ ۱۰:۳۰ ب.ظ

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

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

روی سیکما i از صفر شروع می شه نه از یک.( سطح ریشه صفره)

در مورد اون "منهای یک" که در Lgn -1 بالای سیکما هستش هم فکر می کنم باید دلیل بهتری (یک دلیل ساختمان داده ای) برای اومدنش داشته باشه.


چون بازه‌ی سیکما باید از i=0 (سطح صفرم) تا سطح آخر( یعنی i )باشه و i هم مساوی Log n هستش.

RE: یه سوال بازگشتی از قضیه اصلی - - rasool - - 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 هستش.


RE: یه سوال بازگشتی از قضیه اصلی - sasanlive - 03 آبان ۱۳۹۰ ۰۱:۳۶ ق.ظ

(۰۲ آبان ۱۳۹۰ ۱۱:۱۴ ب.ظ)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 گرفت.

RE: یه سوال بازگشتی از قضیه اصلی - پشتکار - ۰۴ آبان ۱۳۹۰ ۰۹:۴۹ ق.ظ

(۰۳ آبان ۱۳۹۰ ۰۱:۳۶ ق.ظ)sasanlive نوشته شده توسط:  دلیل مقدار بالای سیگما اینست که مجموع هزینه در سطح آخر برابر n است.

[tex]\frac{n}{logn-i}=n \Rightarrow logn-i=1 \Rightarrow i=logn-1[/tex]

برای همین مقدار بالای سیگما را تا logn-1 گرفت.

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

RE: یه سوال بازگشتی از قضیه اصلی - sasanlive - 09 آبان ۱۳۹۰ ۱۲:۱۲ ق.ظ

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

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

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