۰
subtitle
ارسال: #۱
کجا و چ وقتایی میشه از قضیه master برای مرتبه زمانی استفاده کرد؟؟
سلام
قضیه master : T(n)=aT(n/b)+f(n) =>> g(n)=n^logba
ببخشید در قضیه master میگیم به ازای a>=1 و b>1
پس چرا زمانی که a=1 باشه از این قضیه نمیشه استفاده کرد...؟؟؟؟
مثلا این سوال
T(n)=T(n/3)+T(2n/3)+n ==> به نظر من خب بیاییم دوتا دوتا مثل فرمول master بریم جلو...
اول T(n/3)+n که میشه O(n) چون در اینجا a=1 است و loga در مبنای۳ میشه صفر => میشه n^0=1 در نتیجه f(n) بزرگ تر است
خب بعدش دوباره بیاییم T(2n/3)+f(n) حساب کنیم که این دفعه هم g(n)=1 است پس => اینجا هم f بزرگ تره پس O(n)
ولی در جواب سوال نوشته شده ک از قضیه نمیشه استفاده کرد.و جواب رو از روش درخت حل کرده شده nlogn
لطفا موارد استفاده قضیه master را بگید....
قضیه master : T(n)=aT(n/b)+f(n) =>> g(n)=n^logba
ببخشید در قضیه master میگیم به ازای a>=1 و b>1
پس چرا زمانی که a=1 باشه از این قضیه نمیشه استفاده کرد...؟؟؟؟
مثلا این سوال
T(n)=T(n/3)+T(2n/3)+n ==> به نظر من خب بیاییم دوتا دوتا مثل فرمول master بریم جلو...
اول T(n/3)+n که میشه O(n) چون در اینجا a=1 است و loga در مبنای۳ میشه صفر => میشه n^0=1 در نتیجه f(n) بزرگ تر است
خب بعدش دوباره بیاییم T(2n/3)+f(n) حساب کنیم که این دفعه هم g(n)=1 است پس => اینجا هم f بزرگ تره پس O(n)
ولی در جواب سوال نوشته شده ک از قضیه نمیشه استفاده کرد.و جواب رو از روش درخت حل کرده شده nlogn
لطفا موارد استفاده قضیه master را بگید....
