ParsX.com
پذیرش پروژه از دانشجویی ... تا سازمانی 09376225339
 
   ProfileProfile   Log in to check your private messagesLog in to check your private messages  |  FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups Log inLog in   RegisterRegister 

قضیه مستر Master

 
Post new topic   Reply to topic    ParsX.com Forum Index -> طراحي الگوريتم
View previous topic :: View next topic  
Author Message
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Sat Jul 31, 2010 9:36 am    Post subject: قضیه مستر Master Reply with quote

The Master Theorem
در تئوری مستر دو ثابت a و b با این شرط که a>=1 و b>1 باشد داریم.
یک تابع f(n) داریم و یک تابع T(n)
این تابع T(n) تابعیست بازگشتی ، غیرمنفی که طبق فرمول زیر محاسبه می شود:
T(n)=aT(n/b)+f(n)
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Sat Jul 31, 2010 9:37 am    Post subject: Reply with quote

مقدار 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
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Sat Jul 31, 2010 9:40 am    Post subject: Reply with quote

حال 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) خواهد شد.
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Tue Aug 10, 2010 8:31 am    Post subject: Reply with quote

f(n) در قضیه مستر هزینه تقسیم مساله ها و ادغام نتیجه آنها می باشد.
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Mon Aug 16, 2010 10:38 am    Post subject: Reply with quote

در موارد زیر قضیه مستر برقرار نیست :
nT(n/2)+logn
نیست چون a مقدار ثابتی نیست.
2T(n/2)+n/logn

0.5T(n/2)+logn

چون a کوچکتر از یک است.
3T(n/2)-3n

چون f(n) کوچکتر از صفر شده است.
Back to top
Display posts from previous:   
Post new topic   Reply to topic    ParsX.com Forum Index -> طراحي الگوريتم All times are GMT + 3.5 Hours
Page 1 of 1

 
Jump to:  
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