با سلام خدمت همه دوستان
من نمیدونم چطوری مرتبه زمانی روابط بازگشتی چند پارامتری رو بدست بیارم
مثلا این رابطه :
[tex]T\left ( n,k \right )=T\left ( \frac{n}{2},k \right ) T\left ( n,\frac{k}{4} \right ) kn[/tex]
این چنین روابط چطور قابل حل هستند؟مرتبه زمانی رو چطوری باید بدست آورد؟
ممنون میشم راهنمایی کنید
(۱۷ آبان ۱۳۹۲ ۰۶:۰۹ ق.ظ)Arteta نوشته شده توسط: سلام
این سوال با درخت به راحتی قابل حل می باشد
در هر مرحله اول nk داریم
در مرحله دوم nk/2 +nk/4 داریم =۳nk/4
در نتیجه در هر مرحله نسبت تناسب ما ۳/۴ می باشد برای بدست اوردن تصاعد هندسی برای d های کوچکتر از یک داریم a/1-d
==> O(nk)
(عمق درخت هم از جنس log میشه ولی اهمیتی نداره )
ممنون از پاسختون
پس همه این جور روابط رو با استفاده ار درخت بازگشتی باید بدست آورد؟
میشه بگید عمق درختش چطور بدست میاد؟
ممنونم
این سوال مشابه سوال کامیپوتر کنکور سال ۹۰ هست . البته اونجا فقط بیشترین ارتفاع را میخواست
این جور سوالها را باید به روش درخت حل کرد
بیشترین ارتفاع درخت شاخه های راست یا چپ نیستند. بلکه مربوط به شاخه های داخلی هستند
درختش شبیه به این میشه و فکر نکنم اشتباهی کرده باشم. اگر هم جایی اشتباه هست به دل نگیرید، ولی در کل باید به این شکل اینگونه سوال ها را حل کنی
اون آخر باید مجموع (به اندازه ارتفاع درخت) مقادیری که در مجموع گره های یک سطح هست را جمع کنی
چند تا مثال حل کنی متوجه میشی. منم اولش خیلی تو این موارد گیج میزدم.
![[تصویر: 225106_6353222.jpg]](https://img.manesht.ir/225106_6353222.jpg)
(۱۹ آبان ۱۳۹۲ ۰۴:۲۷ ب.ظ)zimenswall نوشته شده توسط: این سوال مشابه سوال کامیپوتر کنکور سال ۹۰ هست . البته اونجا فقط بیشترین ارتفاع را میخواست
این جور سوالها را باید به روش درخت حل کرد
بیشترین ارتفاع درخت شاخه های راست یا چپ نیستند. بلکه مربوط به شاخه های داخلی هستند
درختش شبیه به این میشه و فکر نکنم اشتباهی کرده باشم. اگر هم جایی اشتباه هست به دل نگیرید، ولی در کل باید به این شکل اینگونه سوال ها را حل کنی
اون آخر باید مجموع (به اندازه ارتفاع درخت) مقادیری که در مجموع گره های یک سطح هست را جمع کنی
چند تا مثال حل کنی متوجه میشی. منم اولش خیلی تو این موارد گیج میزدم.
ممنون از زاهنماییتون
واسه عمق درخت قکر کنم باید زیاد تمرین کنم
این جواب درسته؟
(۲۳ آبان ۱۳۹۲ ۱۲:۴۷ ق.ظ)nina69 نوشته شده توسط: این جواب درسته؟
به احتمال ۹۰ درصد درسته.
خیلی در جزییات دقت نکردم . فقط خواستم به دوستمون کلیت حل اینگونه مسائل را گفته باشم.
میشه بگین عمق درختو چطور بدست اوردین؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟