سلام به همه
من یه سوال واسم پیش اومده بود و اون اینکه یه رابطه به فرم[tex]T(n) = 2T(\frac{n}{2}) \frac{n}{log n}[/tex] میتونیم با قضیه مستر حل کنیم؟
و سوال دون اینکه ما میتونیم این رابطه رو با قضیه مستر حل کنیم؟ [tex]T(n) = 4T(\frac{n}{2}) n^{2}log^{2}\ n[/tex]، اگه جواب به این سوال مثبته، پس چرا اینو نمیشه حل کرد؟ [tex]T(n) = 2T(\frac{n}{2}) nlog \ n[/tex]
(۱۸ شهریور ۱۳۹۲ ۰۱:۲۵ ق.ظ)SnowBlind نوشته شده توسط: سلام به همه
من یه سوال واسم پیش اومده بود و اون اینکه یه رابطه به فرم[tex]T(n) = 2T(\frac{n}{2}) \frac{n}{log n}[/tex] میتونیم با قضیه مستر حل کنیم؟
و سوال دون اینکه ما میتونیم این رابطه رو با قضیه مستر حل کنیم؟ [tex]T(n) = 4T(\frac{n}{2}) n^{2}log^{2}\ n[/tex]، اگه جواب به این سوال مثبته، پس چرا اینو نمیشه حل کرد؟ [tex]T(n) = 2T(\frac{n}{2}) nlog \ n[/tex]
با سلام خدمت شما دوست عزیز
در پاسخ کلی به سوالتون فکر میکنم خودتون هم فهمیدید با قضیه مستر نمیشه مرتبه زمانی هر تابع بازگشتی رو بدست آورد ولی اینکه کجا نمیشه ازش استفاده کرد رو میشه به راحتی متوجه شد قضیه مستر بین حالتهای ۱و۲ و ۲و۳ دارای ۲ شکاف که وقتی تابعی تو یکی از این شکافها افتاد دیگه از مستر نمیشه استفاده کرد روش فهمیدنش به این شکله که اگر تابع بازگشت به فرم [tex]T(n)=aT(n/b) f(n)[/tex] باشه و وقتی [tex]n^\log _{b}^{a}\textrm{}[/tex] رو تشکیل دادی و از [tex]f(n)[/tex] کوچیکتر شد نمیتوند بگید قطعا حالت ۳ اتفاق افتاده بلکه باید بصورت چند جمله ای [tex]f(n)[/tex] از [tex]n^\log _{b}^{a}\textrm{}[/tex] بزرگتر باشه یعنی اگر [tex]f(n)/n^\log _{b}^{a}\textrm{}[/tex] رو بدست بیاری باید حاصلش بشه [tex]n^\xi[/tex] مشروط به اینکه [tex]\xi > 0[/tex]اگه چنین چیزی برقرار نباشه شما تو شکاف بین حالت ۲ و ۳ مستر گیر کردی و نمیتونی از مستر استفاده کنی همین حالت هم واسه شکاف بین ۱و۲ منتهی اون کسری که حاصلش [tex]n^\xi[/tex] رو باید برعکس بسازی و بررسی کنی
تمام مثالهای که تو سوالت مطرح کردی طبق چیزی که گفتم بین شکاف ۲و۳ گیر میکنه و نمیشه از مستر استفاده کرد البته یه تبصره کوچیک برای توابع خاصی که [tex]f(n)[/tex] اونا لگاریتمی و توی شکاف ۲ و ۳ گیر میکنن وجود داره که بازم میشه از مستر استفاده کرد به عنوان نمونه بجز مثال اولی که گفتید یعنی [tex]T(n)=2T(n/2) \frac{n}{log n}[/tex] اون دوتای دیگه رو با اینکه بین شکاف ۲و ۳ میفتن میشه با اون تبصره که گفتم حل کرد
توضیحات بیشتر رو میتونید تو کتاب ساختمان داده یا طراحی پوران یا کتاب کورمن مطالعه بفرمایید
جناب amin222 درست میگن . همه رو میشه با استفاده از تعمیم قضیه اصلی حل کرد . توضیحش هم ساده است .
یه نکته هم بد نیست ، سعی کنید علاوه بر روش قضیه اصلی و تعمیمش ، با درخت بازگشت هم کار کنید یعنی مرتبه زمانی پیدا کنید ، عمق ش رو بررسی کنید تعداد برگاش رو بدونید و چیزای اینطوری