Posted: Sat Jul 31, 2010 9:36 am Post subject: قضیه مستر Master
The Master Theorem
در تئوری مستر دو ثابت a و b با این شرط که a>=1 و b>1 باشد داریم.
یک تابع f(n) داریم و یک تابع T(n)
این تابع T(n) تابعیست بازگشتی ، غیرمنفی که طبق فرمول زیر محاسبه می شود:
مقدار n/b می تواند کف n/b باشد یا سقف n/b .
جهت سادگی فرمول های بعدی مقادیر زیر را معادل A,B,C در نظر می گیریم:
مقدار n به توان( لگاریتم( a منهای اپسیلون )در مبنای b )را A در نظر می گیریم.
مقدار n به توان (لگاریتم a در مبنای b )را B در نظر می گیریم.
مقدار n به توان( لگاریتم( a بعلاوه اپسیلون )در مبنای b )را C در نظر می گیریم.
Last edited by vahid on Sat Jul 31, 2010 9:47 am; edited 1 time in total
حال T(n) می تواند به یکی از شروط زیر محدود شود:
1. اگر f(n) برابر O(A) برای بعضی ثوابت اپسیلون بزرگتر از صفر باشد آنگاه T(n) برابر تتایB خواهد بود.
2.اگر f(n) برابر تتای B باشد آنگاه T(n) برابر تتای B در lg n خواهد شد.
3. اگر f(n) برابر اومگای C برای بعضی ثوابت که اپسیلون بزرگتر از ضفر باشد و اگر a(f(n/b)<=cf(n) برای بعضی ثوابت c<1 و تمامی n های باندازه کافی بزرگ باشد. آنگاه T(n) برابر تتای f(n) خواهد شد.
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum