۰
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 را بگید....
۱
ارسال: #۲
RE: کجا و چ وقتایی میشه از قضیه master برای مرتبه زمانی استفاده کرد؟؟
۰
ارسال: #۳
RE: کجا و چ وقتایی میشه از قضیه master برای مرتبه زمانی استفاده کرد؟؟
من خودم هم زیاد به قضایا مسلط نیستم , در حد خودم فقط میتونم بگم:
اول ببینید این قضیه ی مستر رو اگه اشتباه نکنم برای مواردی که بازگشتی ما خطی باشه استفاده میکنیم , الان این رابطه بازگشتی که شما فرمودید خطی نیست و باید براش درخت بازگشت رسم کنیم ,
بعد هم اینو بگم که کلاً این موارد رو باید بر حسب تجربه بدست بیارید,یعنی چندتا حل کنید راحت دستتون میاد که بتونید سریع بگید چطور حلش کنید
اول ببینید این قضیه ی مستر رو اگه اشتباه نکنم برای مواردی که بازگشتی ما خطی باشه استفاده میکنیم , الان این رابطه بازگشتی که شما فرمودید خطی نیست و باید براش درخت بازگشت رسم کنیم ,
بعد هم اینو بگم که کلاً این موارد رو باید بر حسب تجربه بدست بیارید,یعنی چندتا حل کنید راحت دستتون میاد که بتونید سریع بگید چطور حلش کنید
۰
ارسال: #۴
RE: کجا و چ وقتایی میشه از قضیه 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 میتونه برابر یک هم باشه مشکلی نداره بازم قضیه جواب میده. اما در مورد مثالی که زدید به این خاطر از قضیه مستر قابل حل نیست چون اولا نگا کنید توی این معادله دو رابطه بازگشتی داریم ولی در قضیه مستر فقط یدونه هستش. پس برای حلش از درخت بازگشتی استفاده میکنیم. از روی صورت سوال هم مشخصه توی هر سطر درخت مجموع سطرها برابر ان هستش.
ارسال: #۵
RE: کجا و چ وقتایی میشه از قضیه master برای مرتبه زمانی استفاده کرد؟؟
(۰۲ بهمن ۱۳۹۳ ۰۴:۴۵ ب.ظ)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 ??
ارسال: #۶
RE: کجا و چ وقتایی میشه از قضیه master برای مرتبه زمانی استفاده کرد؟؟
۰
ارسال: #۷
RE: کجا و چ وقتایی میشه از قضیه master برای مرتبه زمانی استفاده کرد؟؟
باسلام
روش Akra Bazzi راحت ترین و بهترین روش هست!
پیشنهاد میکنم اگر وقت دارید به کتاب ط.الگوریتم مدرسان یا در اینترنت جستجو کنید .... و اگر ن ایشاالله بعد کنکور....(برای المپیاد بخونیدش!)
روش Akra Bazzi راحت ترین و بهترین روش هست!
پیشنهاد میکنم اگر وقت دارید به کتاب ط.الگوریتم مدرسان یا در اینترنت جستجو کنید .... و اگر ن ایشاالله بعد کنکور....(برای المپیاد بخونیدش!)
۰
ارسال: #۸
RE: کجا و چ وقتایی میشه از قضیه master برای مرتبه زمانی استفاده کرد؟؟
قضییه مستر شرطش اینه که [tex]a\ge1\: و\: b\ge2[/tex] باشه
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close