(۲۳ شهریور ۱۳۹۲ ۰۵:۴۹ ب.ظ)Soodabezare نوشته شده توسط:  سلام من که اینجا یه شاگردم ولی جسارتا جواب میدم

هر دورو می تونی از طریق قضیه master به دست بیاری

با توجه به اینکه n به توان log 7 در مبنای ۸ مرتبه بیشتری از n داره اولی میشه n به توان log 7 در مبنای ۸

برای دومی از ۲ داخل پرانتز صرف نظر می کنی با توجه به اینکه مرتبه n به توان log 1 خطی میشه پس مرتبه logn بیشتره و اون میشه جواب
امیدوارم واضح گفته باشم

سلام :-)

Soodabezare عزیز، اولی رو اشتباه حل کردین و دومی هم مستر رو نمیشه براش استفاده کرد :-)

(۲۳ شهریور ۱۳۹۲ ۰۵:۳۸ ب.ظ)zerocool_ir نوشته شده توسط:  با سلام

اساتید گرامی میشه لطفا راهنمایی کنید این دوتا پیچیدگی زمانی چطور بدست می آید ؟
ممنون میشم اگر توضیح بدهید ...

T(7N/8)+8N

T(N+2) + logN

با تشکر پیشاپیش

در مورد اولی، قضیه مستر برای روابط به شکل (T(n) = aT(n/b) + f(n هستش که در اینجا a = 1 و b = 8/7 هستش. طبق قضیه اصلی (همون مستر) باید این دو تابع مقایسه بشن (البته اینجا شهودی بررسی می‌کنیم):
[tex]n^{log_{b} a}=n^{log_{\frac{8}{7}}1}=n^{0}=1[/tex]
و
[tex]f(n)=8n[/tex]
چون (f(n سرعت رشدش بیشتر از ۱ هستش، پس جواب میشه [tex]T(n)=\Theta (8n)=\Theta (n)[/tex]


در مورد دومی، چون قضیه مستر برای روابط به شکل (T(n) = aT(n/b) + f(n هستش و اینجا به کار نمیاد. احتمالاً منظورتون T(n-2) + logN هستش، چون اون چیزی که شما نوشتین هیچ‌وقت به شرط پایه نمیرسه. با همین فرض صورت سؤال شما به صورت زیر میشه:
[tex]T(n)=T(n-2) log(n)[/tex]

برای حل این رابطه می‌تونیم بسطش بدیم:
[tex]T(n)=T(n-2) log(n)=(T(n-4) log(n-2)) log(n) = ((T(n-6) log(n-4)) log(n-2)) log(n)=...=T(0) log(2) log(4) log(6) log(8) ... log(n-2) log(n)[/tex]

به جای پایه (همون [tex]T(0)[/tex]) هر عدد ثابتی می‌تونه باشه. ما اینجا برای راحتی عدد ۰ رو فرض می‌کنیم. با این جایگذاری داریم:
[tex]T(n)=\sum_{i=1}^{\frac{n}{2}}log(2i)[/tex]

با حل این رابطه داریم:
[tex]T(n)=\sum_{i=1}^{\frac{n}{2}}log(2i)=log((n)(n-2)(n-4)...(4)(2))= log(2^{\frac{n}{2}}\times (\frac{n}{2})!)=log(2^{\frac{n}{2}}) log((\frac{n}{2})!)=\frac{n}{2} \Theta (\frac{n}{2}log(\frac{n}{2}))=\Theta(n) \Theta(n\cdot log(n))=\Theta(n\cdot logn)[/tex]

بنابراین جواب رابطه‌ی دوم میشه [tex]T(n)=\Theta(n\cdot logn)[/tex]

---

در مورد اولی یک راه ساده‌تر و شهودی‌تر هم هست برای فکر کردن بهش. در هر مرحله تعداد عناصر ما ۷/۸ برابر میشه. بنابراین تعداد عملیات ما (همون بخش غیر بازگشتی رابطه) میشه:
تعداد عملیات مرحله اول: [tex]8n[/tex]
تعداد عملیات مرحله دوم: [tex]8\times (\frac{7}{8})n[/tex]
تعداد عملیات مرحله سوم: [tex]8\times (\frac{7}{8})^{2}n[/tex]
تعداد عملیات مرحله چهارم: [tex]8\times (\frac{7}{8})^{3}n[/tex]
و...

بنابراین تعداد کل عملیات ما میشه مجموع یک سری هندسی بی‌نهایت با ضریب q = 7/8 و جمله‌ی اولیه‌ی a = 8n که نتیجه‌اش برابره با:
[tex]T(n)=\frac{a}{1-q}=\frac{8n}{1-\frac{7}{8}}=64n=\Theta (n)[/tex]

(۲۳ شهریور ۱۳۹۲ ۱۰:۱۸ ب.ظ)azk84 نوشته شده توسط:  سلام :-)

Soodabezare عزیز، اولی رو اشتباه حل کردین و دومی هم مستر رو نمیشه براش استفاده کرد :-)

در مورد دومی، چون قضیه مستر برای روابط به شکل (T(n) = aT(n/b) + f(n هستش و اینجا به کار نمیاد. احتمالاً منظورتون T(n-2) + logN هستش، چون اون چیزی که شما نوشتین هیچ‌وقت به شرط پایه نمیرسه. با همین فرض صورت سؤال شما به صورت زیر میشه:
[tex]T(n)=T(n-2) log(n)[/tex]

خدایی اولی رو سربه هوایی جواب دادم شرمنده ولی دومی رو اصلا نمی دونستم چرا نمیشه مستر رفت ؟
خوب خوبه که هستین اشتباهاتو گوشزد کنین
و میشه در مورد اینکه هیچوقت به شرط پایه نمیرسه یکم بیشتر بگید ؟؟
ممنون

(۲۳ شهریور ۱۳۹۲ ۱۱:۱۰ ب.ظ)Soodabezare نوشته شده توسط:  

(23 شهریور ۱۳۹۲ ۱۰:۱۸ ب.ظ)azk84 نوشته شده توسط:  سلام :-)

Soodabezare عزیز، اولی رو اشتباه حل کردین و دومی هم مستر رو نمیشه براش استفاده کرد :-)

در مورد دومی، چون قضیه مستر برای روابط به شکل (T(n) = aT(n/b) + f(n هستش و اینجا به کار نمیاد. احتمالاً منظورتون T(n-2) + logN هستش، چون اون چیزی که شما نوشتین هیچ‌وقت به شرط پایه نمیرسه. با همین فرض صورت سؤال شما به صورت زیر میشه:
[tex]T(n)=T(n-2) log(n)[/tex]

خدایی اولی رو سربه هوایی جواب دادم شرمنده ولی دومی رو اصلا نمی دونستم چرا نمیشه مستر رفت ؟
خوب خوبه که هستین اشتباهاتو گوشزد کنین
و میشه در مورد اینکه هیچوقت به شرط پایه نمیرسه یکم بیشتر بگید ؟؟
ممنون

دلیل این که هیچوقت در رابطه‌ای مثل [tex]T(n)=T(n 2) log(n)[/tex] به شرط پایه نمی‌رسیم اینه که هر بار n ما داره زیاد میشه و هیچوق کم نمیشه تا به شرط پایه برسه (معمولاً شرط پایه برای اعداد ثابتی مثل ۰ یا ۱ در نظر گرفته میشه). همیشه وقتی بسط بدین رابطه رو می‌بینین که انتها نداره و همینطور n ما داره بزرگ میشه :-)

(۲۴ شهریور ۱۳۹۲ ۱۲:۵۲ ق.ظ)azk84 نوشته شده توسط:  دلیل این که هیچوقت در رابطه‌ای مثل [tex]T(n)=T(n 2) log(n)[/tex] به شرط پایه نمی‌رسیم اینه که هر بار n ما داره زیاد میشه و هیچوق کم نمیشه تا به شرط پایه برسه (معمولاً شرط پایه برای اعداد ثابتی مثل ۰ یا ۱ در نظر گرفته میشه). همیشه وقتی بسط بدین رابطه رو می‌بینین که انتها نداره و همینطور n ما داره بزرگ میشه :-)

بسیار ممنونم
نگفتین چرا نمیشه از مستر رفت ؟

(۲۴ شهریور ۱۳۹۲ ۰۱:۲۴ ق.ظ)Soodabezare نوشته شده توسط:  

(24 شهریور ۱۳۹۲ ۱۲:۵۲ ق.ظ)azk84 نوشته شده توسط:  دلیل این که هیچوقت در رابطه‌ای مثل [tex]T(n)=T(n 2) log(n)[/tex] به شرط پایه نمی‌رسیم اینه که هر بار n ما داره زیاد میشه و هیچوق کم نمیشه تا به شرط پایه برسه (معمولاً شرط پایه برای اعداد ثابتی مثل ۰ یا ۱ در نظر گرفته میشه). همیشه وقتی بسط بدین رابطه رو می‌بینین که انتها نداره و همینطور n ما داره بزرگ میشه :-)

بسیار ممنونم
نگفتین چرا نمیشه از مستر رفت ؟

خواهش می‌کنم :-)

دلیل این که دومی رو نمیشه از مستر رفت اینه که مستر فقط برای روابط بازگشتی به شکل [tex]T(n)=aT(\frac{n}{b}) f(n)[/tex] به کار میره و برای روابط بازگشتی دیگه استفاده نمیشه.

(۲۴ شهریور ۱۳۹۲ ۰۱:۲۴ ق.ظ)Soodabezare نوشته شده توسط:  

(24 شهریور ۱۳۹۲ ۱۲:۵۲ ق.ظ)azk84 نوشته شده توسط:  دلیل این که هیچوقت در رابطه‌ای مثل [tex]T(n)=T(n 2) log(n)[/tex] به شرط پایه نمی‌رسیم اینه که هر بار n ما داره زیاد میشه و هیچوق کم نمیشه تا به شرط پایه برسه (معمولاً شرط پایه برای اعداد ثابتی مثل ۰ یا ۱ در نظر گرفته میشه). همیشه وقتی بسط بدین رابطه رو می‌بینین که انتها نداره و همینطور n ما داره بزرگ میشه :-)

بسیار ممنونم
نگفتین چرا نمیشه از مستر رفت ؟

سلام دوست عزیز
به این دلیل نمیشه از مستر رفت که مستر واسه توابعی به فرم [tex]T(n)=aT(n/b) f(n)[/tex] هست و هینطور که میبینید توی این فرم تو هر مرحله مسئله به a مسئله کوچیکتر با سایز [tex]1/b[/tex] مسئله قبلی تبدیل میشه ولی این رابطه [tex]T(n)=T(n 2) log(n)[/tex] با این فرم که گفته شد خیلی تفاوت داره و بقول دوستمون مسئله داره تو هر مرحله هی بزرگ و بزرگتر میشه

(۲۳ شهریور ۱۳۹۲ ۱۰:۱۸ ب.ظ)azk84 نوشته شده توسط:  

(23 شهریور ۱۳۹۲ ۰۵:۴۹ ب.ظ)Soodabezare نوشته شده توسط:  سلام من که اینجا یه شاگردم ولی جسارتا جواب میدم

هر دورو می تونی از طریق قضیه master به دست بیاری

با توجه به اینکه n به توان log 7 در مبنای ۸ مرتبه بیشتری از n داره اولی میشه n به توان log 7 در مبنای ۸

برای دومی از ۲ داخل پرانتز صرف نظر می کنی با توجه به اینکه مرتبه n به توان log 1 خطی میشه پس مرتبه logn بیشتره و اون میشه جواب
امیدوارم واضح گفته باشم

سلام :-)

Soodabezare عزیز، اولی رو اشتباه حل کردین و دومی هم مستر رو نمیشه براش استفاده کرد :-)

(۲۳ شهریور ۱۳۹۲ ۰۵:۳۸ ب.ظ)zerocool_ir نوشته شده توسط:  با سلام

اساتید گرامی میشه لطفا راهنمایی کنید این دوتا پیچیدگی زمانی چطور بدست می آید ؟
ممنون میشم اگر توضیح بدهید ...

T(7N/8)+8N

T(N+2) + logN

با تشکر پیشاپیش

در مورد اولی، قضیه مستر برای روابط به شکل (T(n) = aT(n/b) + f(n هستش که در اینجا a = 1 و b = 8/7 هستش. طبق قضیه اصلی (همون مستر) باید این دو تابع مقایسه بشن (البته اینجا شهودی بررسی می‌کنیم):
[tex]n^{log_{b} a}=n^{log_{\frac{8}{7}}1}=n^{0}=1[/tex]
و
[tex]f(n)=8n[/tex]
چون (f(n سرعت رشدش بیشتر از ۱ هستش، پس جواب میشه [tex]T(n)=\Theta (8n)=\Theta (n)[/tex]


در مورد دومی، چون قضیه مستر برای روابط به شکل (T(n) = aT(n/b) + f(n هستش و اینجا به کار نمیاد. احتمالاً منظورتون T(n-2) + logN هستش، چون اون چیزی که شما نوشتین هیچ‌وقت به شرط پایه نمیرسه. با همین فرض صورت سؤال شما به صورت زیر میشه:
[tex]T(n)=T(n-2) log(n)[/tex]

برای حل این رابطه می‌تونیم بسطش بدیم:
[tex]T(n)=T(n-2) log(n)=(T(n-4) log(n-2)) log(n) = ((T(n-6) log(n-4)) log(n-2)) log(n)=...=T(0) log(2) log(4) log(6) log(8) ... log(n-2) log(n)[/tex]

به جای پایه (همون [tex]T(0)[/tex]) هر عدد ثابتی می‌تونه باشه. ما اینجا برای راحتی عدد ۰ رو فرض می‌کنیم. با این جایگذاری داریم:
[tex]T(n)=\sum_{i=1}^{\frac{n}{2}}log(2i)[/tex]

با حل این رابطه داریم:
[tex]T(n)=\sum_{i=1}^{\frac{n}{2}}log(2i)=log((n)(n-2)(n-4)...(4)(2))= log(2^{\frac{n}{2}}\times (\frac{n}{2})!)=log(2^{\frac{n}{2}}) log((\frac{n}{2})!)=\frac{n}{2} \Theta (\frac{n}{2}log(\frac{n}{2}))=\Theta(n) \Theta(n\cdot log(n))=\Theta(n\cdot logn)[/tex]

بنابراین جواب رابطه‌ی دوم میشه [tex]T(n)=\Theta(n\cdot logn)[/tex]

---

در مورد اولی یک راه ساده‌تر و شهودی‌تر هم هست برای فکر کردن بهش. در هر مرحله تعداد عناصر ما ۷/۸ برابر میشه. بنابراین تعداد عملیات ما (همون بخش غیر بازگشتی رابطه) میشه:
تعداد عملیات مرحله اول: [tex]8n[/tex]
تعداد عملیات مرحله دوم: [tex]8\times (\frac{7}{8})n[/tex]
تعداد عملیات مرحله سوم: [tex]8\times (\frac{7}{8})^{2}n[/tex]
تعداد عملیات مرحله چهارم: [tex]8\times (\frac{7}{8})^{3}n[/tex]
و...

بنابراین تعداد کل عملیات ما میشه مجموع یک سری هندسی بی‌نهایت با ضریب q = 7/8 و جمله‌ی اولیه‌ی a = 8n که نتیجه‌اش برابره با:
[tex]T(n)=\frac{a}{1-q}=\frac{8n}{1-\frac{7}{8}}=64n=\Theta (n)[/tex]

استاد عزیز بسیار ممنون و سپاسگذارم
مخصوصا روی این مورد که منظورم همین جمع بود خیلی ابهام داشتم : T(N+2) + logN
که شما خیلی زیبا برطرفش کردید

درست میگید من فراموش کرده بودم حتی با صرف نظر از ۲ باز هم شرط مستر رو نداره چرا که باید b>1 باشه
دقت رو باید بالا برد ممنون ازتون azk84 و amin222