با سلام
اساتید گرامی میشه لطفا راهنمایی کنید این دوتا پیچیدگی زمانی چطور بدست می آید ؟
ممنون میشم اگر توضیح بدهید ...
T(7N/8)+8N
T(N+2) + logN
با تشکر پیشاپیش
(۲۳ شهریور ۱۳۹۲ ۰۵:۴۹ ب.ظ)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] با این فرم که گفته شد خیلی تفاوت داره و بقول دوستمون مسئله داره تو هر مرحله هی بزرگ و بزرگتر میشه
درست میگید من فراموش کرده بودم حتی با صرف نظر از ۲ باز هم شرط مستر رو نداره چرا که باید b>1 باشه
دقت رو باید بالا برد
ممنون ازتون azk84 و amin222
(۲۳ شهریور ۱۳۹۲ ۱۰:۱۸ ب.ظ)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
که شما خیلی زیبا برطرفش کردید