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

سوال در مورد حل روابط بازگشتی چند پارامتری - tarane.68 - 16 آبان ۱۳۹۲ ۱۱:۴۹ ب.ظ

با سلام خدمت همه دوستان
من نمیدونم چطوری مرتبه زمانی روابط بازگشتی چند پارامتری رو بدست بیارم
مثلا این رابطه :
[tex]T\left ( n,k \right )=T\left ( \frac{n}{2},k \right ) T\left ( n,\frac{k}{4} \right ) kn[/tex]

این چنین روابط چطور قابل حل هستند؟مرتبه زمانی رو چطوری باید بدست آورد؟
ممنون میشم راهنمایی کنید

RE: سوال در مورد حل روابط بازگشتی چند پارامتری - tarane.68 - 17 آبان ۱۳۹۲ ۰۴:۴۶ ب.ظ

(۱۷ آبان ۱۳۹۲ ۰۶:۰۹ ق.ظ)Arteta نوشته شده توسط:  سلام
این سوال با درخت به راحتی قابل حل می باشد
در هر مرحله اول nk داریم
در مرحله دوم nk/2 +nk/4 داریم =۳nk/4
در نتیجه در هر مرحله نسبت تناسب ما ۳/۴ می باشد برای بدست اوردن تصاعد هندسی برای d های کوچکتر از یک داریم a/1-d
==> O(nk)
(عمق درخت هم از جنس log میشه ولی اهمیتی نداره )

ممنون از پاسختون
پس همه این جور روابط رو با استفاده ار درخت بازگشتی باید بدست آورد؟
میشه بگید عمق درختش چطور بدست میاد؟
ممنونم

RE: سوال در مورد حل روابط بازگشتی چند پارامتری - zimenswall - 19 آبان ۱۳۹۲ ۰۴:۲۷ ب.ظ

این سوال مشابه سوال کامیپوتر کنکور سال ۹۰ هست . البته اونجا فقط بیشترین ارتفاع را میخواست
این جور سوالها را باید به روش درخت حل کرد

بیشترین ارتفاع درخت شاخه های راست یا چپ نیستند. بلکه مربوط به شاخه های داخلی هستند
درختش شبیه به این میشه و فکر نکنم اشتباهی کرده باشم. اگر هم جایی اشتباه هست به دل نگیرید، ولی در کل باید به این شکل اینگونه سوال ها را حل کنی

اون آخر باید مجموع (به اندازه ارتفاع درخت) مقادیری که در مجموع گره های یک سطح هست را جمع کنی
چند تا مثال حل کنی متوجه میشی. منم اولش خیلی تو این موارد گیج میزدم.

[تصویر:  225106_6353222.jpg]

RE: سوال در مورد حل روابط بازگشتی چند پارامتری - tarane.68 - 22 آبان ۱۳۹۲ ۱۲:۲۳ ب.ظ

(۱۹ آبان ۱۳۹۲ ۰۴:۲۷ ب.ظ)zimenswall نوشته شده توسط:  این سوال مشابه سوال کامیپوتر کنکور سال ۹۰ هست . البته اونجا فقط بیشترین ارتفاع را میخواست
این جور سوالها را باید به روش درخت حل کرد

بیشترین ارتفاع درخت شاخه های راست یا چپ نیستند. بلکه مربوط به شاخه های داخلی هستند
درختش شبیه به این میشه و فکر نکنم اشتباهی کرده باشم. اگر هم جایی اشتباه هست به دل نگیرید، ولی در کل باید به این شکل اینگونه سوال ها را حل کنی

اون آخر باید مجموع (به اندازه ارتفاع درخت) مقادیری که در مجموع گره های یک سطح هست را جمع کنی
چند تا مثال حل کنی متوجه میشی. منم اولش خیلی تو این موارد گیج میزدم.

[تصویر:  225106_6353222.jpg]

ممنون از زاهنماییتون
واسه عمق درخت قکر کنم باید زیاد تمرین کنم

RE: سوال در مورد حل روابط بازگشتی چند پارامتری - nina69 - 23 آبان ۱۳۹۲ ۱۲:۴۷ ق.ظ

این جواب درسته؟

RE: سوال در مورد حل روابط بازگشتی چند پارامتری - zimenswall - 23 آبان ۱۳۹۲ ۱۲:۵۱ ق.ظ

(۲۳ آبان ۱۳۹۲ ۱۲:۴۷ ق.ظ)nina69 نوشته شده توسط:  این جواب درسته؟

به احتمال ۹۰ درصد درسته.
خیلی در جزییات دقت نکردم . فقط خواستم به دوستمون کلیت حل اینگونه مسائل را گفته باشم.

RE: سوال در مورد حل روابط بازگشتی چند پارامتری - ریحان - ۲۳ آبان ۱۳۹۲ ۰۸:۱۲ ب.ظ

میشه بگین عمق درختو چطور بدست اوردین؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟