تحلیل الگوریتم ها

[Salar Ashgi]

سلام به همه عزیزان ، میدونیم که طبق Master Theorem ، رابطه بازگشتی

T(n) = aT(n/b)+cn^k قابل حله ، حال سوال اینه آیا یه روش کلی برای وقتی که به جای

cn^k هر تابع دلخواهی باشد ، وجود دارد؟! ، البته به کتاب CLRS یه نگاهی کردم ، ولی

بیشتر ابتکاری حل کرده بود تا یک روش کلی !!!


ممنون از راهنمایی شما !!!

[newamir]

چیزی که CLRS گفته اصلا ابتکاری نیست، برای رابطه بازگشتی

T(n) = a*T(n/b)+f(n)

سه حالت متفاوت در نظر گرفته و به صورت کلی میشه گفت سعی کرده

f(n)

رو با

n^(log a/log b)

رو از لحاظ order با هم مقایسه بکنه و بعد جواب رو میده. البته اینها تمام فضای حالات رو پوشش نمیدن. یعنی بین سه حالت در نظر گرفته شده خلا وجود داره. ولی رده بسیار وسیعی از مسائل با این قضیه به راحتی حل میشن. اگه حالت بندی CLRS برات نامفهومه بگو برات توضیح بدم.

[pesar irooni]

طبق گفته دوستمون CLRS همه چی رو توضیح داده و به راحتی میشه با نگاه به a*T(n/b ومقایسه با F(n جواب رو بدست آورد. اما باید دید با بلاهایی که سر عبارت a*T(n/b میارند جواب چطوری میشه. مثل سوال اول ساختمان داده ها امسال کارشناسی ارشد که همه رو سر در گم کرده بود.