در مثال زیر نمیشه از قضیه اصلی استفاده کرد.
T(n) = 2T(n/2) + nlgn
گفته چون f(n) بصورت چند جمله ای از n بزرگتر نیست نمی توان از قضیه اصلی استفاده کرد.
۱- یعنی چی بصورت چند جمله ای بزرگتر نیست؟ (به صورت چندجمله ای بزرگتر بودن یعنی چی؟)
۲- و اینکه گفته نسبت f(n) به n^loga b از n^e کمتره. این اپسیلونو چطوری باید تعیین کنیم؟ هر مقداری میتونه باشه؟
۳- و در مورد مثال زیر چطور؟
T(n) = 2T(n/2) + n/lgn
سلام. میتونید حاصل این روابط رو با درخت بازگشت بدست بیارید. فکر کنم حاصل اولی بشه nlg^{n}2 و حاصل دومی هم nlglgn.
(۰۵ مرداد ۱۳۹۱ ۰۲:۲۹ ق.ظ)Jooybari نوشته شده توسط: سلام. میتونید حاصل این روابط رو با درخت بازگشت بدست بیارید. فکر کنم حاصل اولی بشه nlg^{n}2 و حاصل دومی هم nlglgn.
ببخشید ولی سوالم چیز دیگه ای بود حلشو نخواستم. راجع به قضیه ی مستر سوال پرسیدم.
حالات خاصیه که اگه با درخت بازگشت برید متوجه میشید مجموع مقادیر هر سطح مقدار خیلی نزدیک دارن. چندتا مثال از حالاتی که این قضیه استفاده میشه و نمیشه رو با درخت حل کنید. در حالاتی که این قضیه قابل استفادست، مقادیری که باهم جمع میشن اونقدر نزدیک نیستن که مساوی درنظر بگیریم.
یه حالت پیش میاد که ثابت هایی که جمع میشن به عنوان مثال مقادیر n و n/2 و n/4 و ... هستن که در این حالت از قضیه استفاده میشه. (مجموع مقادیر رو میشه ۲n گرفت که عدد ۲ ثابت هست.)
یه حالت هم n و n-1 و n-2 و ... هستن. اینجا دیگه نمیشه از قضیه استفاده کرد. چون مقادیر خیلی نزدیکن. (مجموع مقادیر رو نمیشه kn گرفت که k ثابت باشه.)
با توجه به صفحه ی ۱۰۴ کتاب داده ساختارها و الگوریتم های دکترقدسی:
در قضیه ی اصلی مقایسه های > و < که برای دو تابع f و g در نظر گرفته می‌شوند، به معنی بزرگتر یا کوچکتر بودن آهنگ رشد دو چند جمله ای برای مقادیر بزرگ n است و بزرگ یا کوچک بودن آهنگ رشد هم به صورت دو چندجمله ای است. مثلا آهنگ رشد n^2 از nlogn و یا n از n^( 1/2 ) {رادیکال n} به صورت چند جمله ای بیشتر است. ولی آهنگ رشد nlgn از n به صورت چندجمله ای بیشتر نیست. چرا که در حالت آخر نمی توان epsilon >0 ای پیدا کرد که برای مقادیر بزرگ n داشته باشیم:
n^(a) <=nlgn
a=1+epsilon