سلام
قضیه 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 را بگید....
من خودم هم زیاد به قضایا مسلط نیستم , در حد خودم فقط میتونم بگم:
اول ببینید این قضیه ی مستر رو اگه اشتباه نکنم برای مواردی که بازگشتی ما خطی باشه استفاده میکنیم , الان این رابطه بازگشتی که شما فرمودید خطی نیست و باید براش درخت بازگشت رسم کنیم ,
بعد هم اینو بگم که کلاً این موارد رو باید بر حسب تجربه بدست بیارید,یعنی چندتا حل کنید راحت دستتون میاد که بتونید سریع بگید چطور حلش کنید
(۰۲ بهمن ۱۳۹۳ ۱۲:۱۳ ب.ظ)mostafa2012 نوشته شده توسط: سلام
قضیه 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
سلام
این قضیه مستر وقتی استفاده میشه که فرم معادله دقیقا مثل همون فرمولی که خودتون نوشتید باشه. بر خلاف اون چیزی که گفتیم a میتونه برابر یک هم باشه مشکلی نداره بازم قضیه جواب میده. اما در مورد مثالی که زدید به این خاطر از قضیه مستر قابل حل نیست چون اولا نگا کنید توی این معادله دو رابطه بازگشتی داریم ولی در قضیه مستر فقط یدونه هستش. پس برای حلش از درخت بازگشتی استفاده میکنیم. از روی صورت سوال هم مشخصه توی هر سطر درخت مجموع سطرها برابر ان هستش.
(۰۲ بهمن ۱۳۹۳ ۰۴:۴۵ ب.ظ)shayesteb نوشته شده توسط:(02 بهمن ۱۳۹۳ ۱۲:۱۳ ب.ظ)mostafa2012 نوشته شده توسط: سلام
قضیه 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
سلام
این قضیه مستر وقتی استفاده میشه که فرم معادله دقیقا مثل همون فرمولی که خودتون نوشتید باشه. بر خلاف اون چیزی که گفتیم a میتونه برابر یک هم باشه مشکلی نداره بازم قضیه جواب میده. اما در مورد مثالی که زدید به این خاطر از قضیه مستر قابل حل نیست چون اولا نگا کنید توی این معادله دو رابطه بازگشتی داریم ولی در قضیه مستر فقط یدونه هستش. پس برای حلش از درخت بازگشتی استفاده میکنیم. از روی صورت سوال هم مشخصه توی هر سطر درخت مجموع سطرها برابر ان هستش.
سلام
ببخشید خب نمیشه دوتا دوتا با هم گرفت=>> اینجوری میشه master ??
(۰۲ بهمن ۱۳۹۳ ۰۵:۲۳ ب.ظ)mostafa2012 نوشته شده توسط: سلام
ببخشید خب نمیشه دوتا دوتا با هم گرفت=>> اینجوری میشه master ??
تا اونجایی که من اطلاع دارم این روش غلط هست . معادله به هم وابستش نمیشه جداش کنی چطوری میشه این کارا کرد وقتی اینها در کنار همدیگه یک معادله رو تشکیل میدن.
(۰۲ بهمن ۱۳۹۳ ۱۲:۱۳ ب.ظ)mostafa2012 نوشته شده توسط: T(n)=T(n/3)+T(2n/3)+n
این میشه nlogn
باسلام
روش Akra Bazzi راحت ترین و بهترین روش هست!
پیشنهاد میکنم اگر وقت دارید به کتاب ط.الگوریتم مدرسان یا در اینترنت جستجو کنید .... و اگر ن ایشاالله بعد کنکور....(برای المپیاد بخونیدش!)
قضییه مستر شرطش اینه که [tex]a\ge1\: و\: b\ge2[/tex] باشه