![]() |
حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - نسخهی قابل چاپ |
حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - Iranian Wizard - 28 آبان ۱۳۹۴ ۱۲:۴۳ ق.ظ
سلام.کسی میدونه که باید چجور پیچیدگی زمانی این مسئله ی بازگشتی رو بدست بیارم؟ [tex]T(n)\: =\: T(\frac{n}{2}\: \: \sqrt{n})\: \: \sqrt{6046}[/tex] |
RE: حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - sixsixsix - 28 آبان ۱۳۹۴ ۰۲:۲۷ ق.ظ
(۲۸ آبان ۱۳۹۴ ۱۲:۴۳ ق.ظ)IranianWizard نوشته شده توسط: سلام.کسی میدونه که باید چجور پیچیدگی زمانی این مسئله ی بازگشتی رو بدست بیارم؟ T(n) < T(n/2 + n) + 80 پس T(n) < T(3n/2) + 80 در نتیجه T(n)=O(log n) حالا جواب چی بوده؟ |
RE: حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - Iranian Wizard - 28 آبان ۱۳۹۴ ۰۴:۱۱ ق.ظ
(۲۸ آبان ۱۳۹۴ ۰۲:۲۷ ق.ظ)sixsixsix نوشته شده توسط: حالا جواب چی بوده؟متاسفانه جوابشو نمیدونم.یه تمرینه.هرچقد بهش فکر کردم،به ذهنم نرسید که چجور حلش کنم. خب اینجور شما یه حد بالا واسش تعریف کردین.ولی دقیقش که معلوم نیست ![]() (۲۸ آبان ۱۳۹۴ ۰۲:۲۷ ق.ظ)sixsixsix نوشته شده توسط: T(n) < T(n/2 + n) + 80یه سوال داشتم.شما گفتین رشد ( T( n کوچکتر از رشد T(3n/2) + 80 هستش...ولی این T(3n/2) + 80 که اصلا قابل حل نیست.چون اینجور که ما n رو نمیشکنیم.هر بار بزرگترش میکنیم که. با قضیه مستر هم که قابل حل نیست.چون در aT(n/b) + c باید b بزرگتر از ۱ باشه،ولی اینجا b=2/3 هستش. ![]() |
RE: حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - amniat0101 - 28 آبان ۱۳۹۴ ۰۳:۳۴ ب.ظ
برای این سوال نکته داریم : [tex]T(n)=T(\frac{n}{a}) b\: ,\: a>1\: \Rightarrow\: O(\log_an)[/tex] علاوه بر حل با نکته شما با توجه به رابطه ای که با هم ارزی ساخته شده می توانید از تغییر متغیر استفاده کنید و یک رابطه ی ناهمگن بسازید. به این شکل که جمله ی [tex]\frac{3n}{2^k}=1\: [/tex] را در نظر گرفته که ۱ شرط توقف می باشد. سپس مقدار k را از این رابطه بدست آورید که می شود : [tex]k=\log_{\frac{2}{3}}n\: [/tex] سپس در معادله ی اصلی به جای مقداری ۳n قرار دهید [tex]2^k[/tex] . معادله به صورت مقابل میشود : [tex]T(2^k)=T\: (\frac{2^k}{2}) 80\: =T\: (2^{k-1}) 80[/tex] سپس با تغییر متغیر : [tex]t_k=T(2^k)\: [/tex] در معادله ی فوق آن را به صورت : [tex]t_k=t_{k-1} 80[/tex] بنویسید. حال با توجه به روابط بازگشتی و حل آنها،این رابطه را که یک رابطه ی ناهمگن است حل کنید که به مرتبه ی زمانی ذکر شده در نکته خواهید رسید. فکر کنم با درخت بازگشت هم قابل حل باشد |
RE: حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - sixsixsix - 28 آبان ۱۳۹۴ ۰۳:۵۲ ب.ظ
(۲۸ آبان ۱۳۹۴ ۰۴:۱۱ ق.ظ)IranianWizard نوشته شده توسط:(28 آبان ۱۳۹۴ ۰۲:۲۷ ق.ظ)sixsixsix نوشته شده توسط: حالا جواب چی بوده؟متاسفانه جوابشو نمیدونم.یه تمرینه.هرچقد بهش فکر کردم،به ذهنم نرسید که چجور حلش کنم. آره شما درست میگید ولی درحالت کلی برای nهای بزرگ sqrt(n) < n/a هست که a عددی ثابت هست. یعنی شما میتونید یه a دلخواه در نظر بگیرید که مقدار T(bn/c) جوری بدست بیاد که b/c <1 بشه و باز هم جواب logn هست. حالا مبناش خیلی فرق نمیکنه امیدوارم منظورم رو متوجه شده باشید |
RE: حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - Iranian Wizard - 28 آبان ۱۳۹۴ ۰۵:۴۳ ب.ظ
(۲۸ آبان ۱۳۹۴ ۰۳:۳۴ ب.ظ)amniat0101 نوشته شده توسط: برای این سوال نکته داریم : ممنون از پاسختون. ولی شما اومدین [tex]\frac{3n}{2^k}=1[/tex] قرار دادین.در حالیکه بایستی بنویسیم [tex](\frac{3}{2})^kn=1[/tex] .و هر بار n با اینکه تقسیم بر ۲ میشه،ضربدر ۳ هم میشه.که اینجور به هیچوقت به ۱ نمیرسه. پس اینجور اینکه گفتین [tex]3n\: =\: 2^k[/tex] اشتباه میشه. ![]() (۲۸ آبان ۱۳۹۴ ۰۳:۵۲ ب.ظ)sixsixsix نوشته شده توسط: آره شما درست میگید ولی درحالت کلی برای nهای بزرگ sqrt(n) < n/a هست که a عددی ثابت هست. بله متوجه شدم.ممنونم از پاسختون. |
RE: حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - amniat0101 - 28 آبان ۱۳۹۴ ۰۸:۲۹ ب.ظ
بله حق با شماست بنده اشتباه کردم : ولی فکر کنم این راه حل درست باشد : [tex]T(n)=3\: T\: (\frac{n}{2}) 80[/tex] در رابطه ی بالا اگر به روش جایگذاری و تکرار عمل کنیم میرسیم به چنین رابطه ای : [tex]3^k\: T(\frac{n}{2^k})[/tex] حال داریم : [tex]\frac{n}{2^k}=1\: \Rightarrow\: n=2^k\: ,\: \: k=\log_2n\: \: \: 3^kT(1)=3^{\log_2n}[/tex] حال به جای n ها قرار میدهیم : [tex]\: n=2^k\: [/tex] که به این رابطه میرسیم : [tex]T(2^k)=3^{\log_22^k}\: T(\frac{2^k}{2}) 80\: \: \Rightarrow\: T(2^k)=2^{klog_23}\: T\: (2^{k-1}) 80\: [/tex] حال اگر [tex]\log_23\approx1[/tex] و فکر کنم با توجه به اینکه تمرکز ما بیشتر بر روی مقدار k است این درست باشد.داریم : [tex]T(2^k)=2^kT(2^{k-1}) 80[/tex] حال با تغییر متغیر : [tex]t_k=2^k[/tex] داریم : [tex]t_k=t_k\: (t_{k-1}) 80\: \Rightarrow\: \: t_k-t_k\times t_{k-1}=80\: \Rightarrow\: t_k(1-t_{k-1})=80\: \Rightarrow\: k(1-k)=80[/tex] حال برای حل رابطه ی ناهمگن بالا داریم : مقدار چند جمله ای ما عدد ثابت ۸۰ هست که از درجه ی صفر می باشد.(البته در بالا دقت نمایید که برای حل روابط بازگشتی ناهمگن ما میتوانیم قسمت همگن را با برابر قرار دادن صفر محاسبه کنیم که از همانجا یک ریشه ی k=0 بدست می آید و نادیده گرفته میشود) نهایتا به این میرسیم که : [tex](k-1)^2=0[/tex] که ریشه ی تعدد ۲ دارد: حال در آخر سر داریم : [tex]t_k=c_1(1)^n c_2k(1)^n[/tex] با جایگذاری [tex]k=\log_2n[/tex] و به دست آوردن مقادیر C ها میتوان به پیچیدگی [tex]\log_2n[/tex] رسید امیدوارم درست باشد |
RE: حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - Iranian Wizard - 28 آبان ۱۳۹۴ ۰۹:۲۸ ب.ظ
(۲۸ آبان ۱۳۹۴ ۰۸:۲۹ ب.ظ)amniat0101 نوشته شده توسط: بله حق با شماست بنده اشتباه کردم :خیلی ممنونم از وقتی که میذارید. ولی [tex]T(n)=T(\frac{3n}{2}) 80[/tex] خیلی با [tex]T(n)=3T(\frac{n}{2}) 80[/tex] متفاوته ![]() |
RE: حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - amniat0101 - 29 آبان ۱۳۹۴ ۰۲:۰۳ ق.ظ
بله حق با شماست.ولی توی همین سعی و خطا نکته هایی به ذهنم میاد که حرف نداره.سوال قبلی با فرض خودم درسته. و اما برای این سوال یک نظری دارم، ولی خودتان جستجو کنید و صحیح یا غلط بودنش را به ما هم بگید. به نظرم اگر در همان ابتدای کار تغیر متغیر دهیم بهتر باشد : به این شکل که : [tex]T(n)=T(\frac{3n}{2}) 80\: \Rightarrow\: [/tex] با تغییر متغیر : [tex]n=2^k\: [/tex] داریم : [tex]T(2^k)=T(3\times2^{k-1}) 80[/tex] حال مجددا تغییر متغیر داده و داریم : [tex]t_k=2^k\: \Rightarrow\: t_k=3t_{k-1} 80\: \Rightarrow\: t_k-3t_{k-1}=80[/tex] این را تا آخر امتحان کنید، اگر هم به نتیجه نرسیدید، نکته ای که در ابتدای حل مثال عرض کردم رو برای همیشه در خاطرتون خواهید داشت ![]() و هر زمان این شکل از سوالات روابط بازگشتی رو ببینید با اون نکته حلش میکنید.اگر این شکل روابط ساده بودن قطعا توی سه کتاب چنین نکته ای رو براشون بیان نمیکردن. |
RE: حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - sahabi2015 - 01 آذر ۱۳۹۴ ۰۲:۴۱ ب.ظ
نکته ای رو که گفتید فکر نکنم جایی گقته شده باشه و هرچند تو بعضی منال ها جواب درست میده اما نمیشه بصور کلی درست درنظر گرفت ما یک نکته داریم که : [tex]T(n)=aT(n-b) c[/tex] که مرتبه این رابطه بصورت [tex]T(n)\in\theta(a^{\frac{n}{b}})[/tex] و نکته دوم هم که مربوط به قضیه مستره که [tex]T(n)=aT(\frac{n}{b}) c[/tex] که a=1 , b>1 انگاه [tex]T(n)=T(\frac{n}{b}) c[/tex] [tex]T(n)\in\theta(\log n)[/tex] ----------- حالا تو این مثال [tex]T(n)<T(\frac{n}{2} n) c[/tex] [tex]T(n)<T(\frac{3n}{2}) c[/tex] [tex]T(n)<T(\frac{n}{\frac{2}{3}}) c[/tex] با تغییر متغییر [tex]n=(\frac{2}{3})^k[/tex] [tex]T((\frac{2}{3})^k)=T((\frac{2}{3})^{k-1}) c[/tex] با تغییر متغیر [tex]T((\frac{2}{3})^k)[/tex] به [tex]t_k[/tex] داریم [tex]t(k)=t(k-1) c[/tex] که مرتبه ان میشود [tex]\theta(k)[/tex] که با توجه به [tex]n=(\frac{2}{3})^k[/tex] K میشود [tex]k=\log_{\frac{2}{3}}\: n[/tex] که با جایگذاری [tex]T(n)\in\theta(\log n)[/tex] نکته ای رو که گفتید فکر نکنم جایی گقته شده باشه و هرچند تو بعضی منال ها جواب درست میده اما نمیشه بصور کلی درست درنظر گرفت ما یک نکته داریم که : [tex]T(n)=aT(n-b) c[/tex] که مرتبه این رابطه بصورت [tex]T(n)\in\theta(a^{\frac{n}{b}})[/tex] و نکته دوم هم که مربوط به قضیه مستره که [tex]T(n)=aT(\frac{n}{b}) c[/tex] که a=1 , b>1 انگاه [tex]T(n)=T(\frac{n}{b}) c[/tex] [tex]T(n)\in\theta(\log n)[/tex] ----------- حالا تو این مثال [tex]T(n)<T(\frac{n}{2} n) c[/tex] [tex]T(n)<T(\frac{3n}{2}) c[/tex] [tex]T(n)<T(\frac{n}{\frac{2}{3}}) c[/tex] با تغییر متغییر [tex]n=(\frac{2}{3})^k[/tex] [tex]T((\frac{2}{3})^k)=T((\frac{2}{3})^{k-1}) c[/tex] با تغییر متغیر [tex]T((\frac{2}{3})^k)[/tex] به [tex]t_k[/tex] داریم [tex]t(k)=t(k-1) c[/tex] که مرتبه ان میشود [tex]\theta(k)[/tex] که با توجه به [tex]n=(\frac{2}{3})^k[/tex] K میشود [tex]k=\log_{\frac{2}{3}}\: n[/tex] که با جایگذاری [tex]T(n)\in\theta(\log n)[/tex] که مبنای لگاریتم تو مرتبه زمانی مهم نیست |
RE: حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - LEA3C - 30 آذر ۱۳۹۴ ۱۲:۱۳ ب.ظ
من فکر میکنم جواب این سوال اینطوری بشه: [tex]n=2^m[/tex] [tex]T(2^m)=T(2^{m-1} 2^{\frac{m}{2}}) O(1)[/tex] [tex]S(m)=S(m-1 \frac{m}{2}) O(1)[/tex] [tex]S(m)=S(\frac{3m}{2}-1) O(1)[/tex] [tex]O(\log m)[/tex] با تغییر متغیر [tex]O(\log\log n)[/tex] امیدوارم درست باشه |
RE: حل مسئله ی بازگشتی T(n)=T(n/2 + √n)+√۶۰۴۶ - LEA3C - 08 بهمن ۱۳۹۴ ۰۵:۱۷ ب.ظ
(۳۰ آذر ۱۳۹۴ ۱۲:۱۳ ب.ظ)LEA3C نوشته شده توسط: من فکر میکنم جواب این سوال اینطوری بشه: دوستان کسی راجع به این راه حلی که من نوشتم نظری نداره؟ به نظر خودم که درسته نظر شما چیه؟ |