نقل قول: تحلیل الگوریتم ها
چیزی که CLRS گفته اصلا ابتکاری نیست، برای رابطه بازگشتی
T(n) = a*T(n/b)+f(n)
سه حالت متفاوت در نظر گرفته و به صورت کلی میشه گفت سعی کرده f(n)
رو با n^(log a/log b)
رو از لحاظ order با هم مقایسه بکنه و بعد جواب رو میده. البته اینها تمام فضای حالات رو پوشش نمیدن. یعنی بین سه حالت در نظر گرفته شده خلا وجود داره. ولی رده بسیار وسیعی از مسائل با این قضیه به راحتی حل میشن. اگه حالت بندی CLRS برات نامفهومه بگو برات توضیح بدم.
نقل قول: تحلیل الگوریتم ها
طبق گفته دوستمون CLRS همه چی رو توضیح داده و به راحتی میشه با نگاه به a*T(n/b ومقایسه با F(n جواب رو بدست آورد. اما باید دید با بلاهایی که سر عبارت a*T(n/b میارند جواب چطوری میشه. مثل سوال اول ساختمان داده ها امسال کارشناسی ارشد که همه رو سر در گم کرده بود.