تالار گفتمان مانشت
حل رابطه بازگشتی(رادیکالی) - نسخه‌ی قابل چاپ
حل رابطه بازگشتی(رادیکالی) - sepid - 07 دى ۱۳۸۹ ۱۱:۴۵ ب.ظ

دوستان میشه این رابطه رو حل کنید.
T(n)=√n T(√n)+n

RE: حل رابطه بازگشتی - ۵۴m4n3h - 08 دى ۱۳۸۹ ۰۲:۱۰ ب.ظ

طرفین رابطه رو بر n تقسیم کنید، تبدیل میشه به [تصویر: gif.download?\frac{T(n)}{n}=\frac{T(\sqr...sqrt{n}}+1]
تغییر متغیر [تصویر: gif.download?\frac{T(n)}{n}=h(n)] رو بدید بعد هم تغییر متغیر n=2^m بدید، دیگه بقیه ش راحت حل میشه!

RE: حل رابطه بازگشتی - لهمشد - ۰۸ دى ۱۳۸۹ ۰۲:۵۸ ب.ظ

حالا یه سوال اگه سوال این طوری باشه چی ؟

حل رابطه بازگشتی - arshad90 - 09 دى ۱۳۸۹ ۱۲:۴۲ ق.ظ

فکر می کنم اینم مثل بالایی حل شه. یه رابطه مشابه این تو CLRS بود گمونم این بود: T(n)= T (n/2 - 17) + n

نتیجه گرفته بود چون رشد ۱۷ ثابته تاثیری رو رابطه نداره و با همون مستر متد ساده حله رابطه.

گمونم این رابطه شما هم همین تحلیل رو بشه براش به کار برد.

RE: حل رابطه بازگشتی - لهمشد - ۲۵ دى ۱۳۸۹ ۰۶:۰۶ ب.ظ

البته مطمئن نیستم ولی جواب این سوال رو من اوردم loglogn نمی دونم درسته یانه البته نه با تغییر متغییر ۲^k با این تغییر متغیر
کد:
۲^۲^k

اگه درست بود راه حلم رو می گذارم

RE: حل رابطه بازگشتی - لهمشد - ۲۶ دى ۱۳۸۹ ۰۳:۰۸ ق.ظ

با سلام:
جواب سوالی که اقا / خانم sepid مطرح کردن ایا همون loglogn میشه ؟

حل رابطه بازگشتی - ۱۲۸qwi - 26 دى ۱۳۸۹ ۰۳:۵۶ ق.ظ

فکر میکنم بشه n log log n به خاطر تغییر متغیر اول باید جوابتون در n ضرب بشه!

RE: حل رابطه بازگشتی - لهمشد - ۲۷ دى ۱۳۸۹ ۰۲:۰۶ ق.ظ

درسته حق با شماست بله یه n هم ضرب میشه