صفحه‌ها: ۱ ۲
سلام.
درخواست از مدیران محترم سایت : خواهشا به هیچ وجه تیک درست سوالات را نزنید،پاسخ سوالات در همه جا موجود است،و اینجا نحوه ی پاسخگویی متفاوت و البته کامل تر است
درخواست از کاربران محترم : جدا از گذاشتن سپاس و تشکر خودداری کنید،طرح سوالات به عهده ی خودم هست و پاسخ های مختلف از خودم و سایر کاربران،اگر سوالی به نظرتون جالب اومد و در طول سلسله مراتب بود حتما برای من پیام خصوصی کنید به اسم شما طرح و پاسخ داده میشود
اینجا میخوام هر روز که بیام یه سری سوال ساختمان داده ها با حلشون رو بزارم.این کارو از دیر باز دوست داشتم انجام بدم.
شاید بعضی از سوالات تکراری باشن یا پاسخ هایی که من بهشون میدم درست و کامل نباشن.هیچ کس اینجا جز حل سوال خواهشان چیزی نذاره.
این اتفاق در تلگرامم افتاده بود که به هیچ وجه برای من قابل قبول نبود و کلا نمیتونستم باهاش ارتباط برقرار کنم و تصمیم گرفتم این جا برقرارش کنم.
فرق اینجا با تلگرام در اینه که اینجا توضیحات هر مبحث رو به قدری کامل بدیم که حتی نیازی به مراجه به کتاب یا جزوه نباشه
سوالات به صورت سلسله مراتبی از مباحث ابتدایی به انتهایی کتاب طرح و حل میشن و هر سوال و پاسخی که کسی میخواد بگذاره در قالب ایده ای نو یا روشی جدید باید طبق این سلسله مراتب باشه.
این کارم واقعا به خاطر خودم انجام میدم فقط و کمک شما و همراهی شما دوستای عزیز مانشتی قطعا اینجا رو غنی تر میکنه و باعث خوشحالی و افتخاره.ضمنا مباحث و مطالب و ایده هایی که برای حل یک سوال رو میدید تا سال ها در این جا داریدش و میتونید درست یا غلط بودن یا ابهام در ایده هاتون برای حل سوال رو به مباحثه بگذارید و نتیجه ای تقریبا قطعی ازش بگیرید و در ذهنتون ماندگار و تثبیت بشه.
هر سوال حداکثر پس از سه روز پاسخ داده میشه تا فرصت برای فکر کردن دوستان هم فراهم بشه.روند سوال ها از ساده به مشکل هست.
خواهشا یا پاسخ ها کامل باشد(تمام توضیحات در مورد یک پاسخ داده شود) با توجه به هدف اصلی این پست. یا در صورت عدم کامل بودن من از شما کاربران محترمِ پاسخگو درخواست حذف پاسخ رو میدم و شما با من همراهی کنید.باز هم سپاس.
با آرزوی موفقیت برای همه دوستان عزیز
سر فصل اول
(ادغام دنباله های مرتب) :
سوال اول از ۶۰۰ مساله {به مرتب بودن دقت شود)
m لیست پیوندی مرتب با مجموعه n عنصر داده شده است و تعداد عناصر هر دنباله مشخص نیست.کدام یک از گزینه های زیر مرتبه ی سریع ترین الگوریتم برای ادغام این دنباله هاست ؟
۱) n logm
۲) nm
۳) n+m
۴) n logn
پاسخ سوال دوم(*)
با توجه به تشریح سوال داریم: تعداد لیست های موجود kتا است که هر کدام [tex]\frac{n}{k}[/tex] عنصر دارند. پس تعداد لیست های موجود برابر است با : [tex](\frac{n}{k})^k[/tex]
حال برای ادغام این لیست ها هر کدام از این لیست ها میتوانند با هم ترکیب شوند که داریم : [tex](\frac{n}{k})\: !\: ^k[/tex] در کل تعداد حالات برابر است با :
[tex]\frac{n!}{(\frac{n}{k})!^k}[/tex]
با توجه به ایده ی موجود در سوال قبلی برای پیمودن درختی(با توجه به مرتب بودن عناصر میشود با حذف بزرگترین عناصر هر لیست از آن ها یک هرم بیشینه ساخت و پس از آن پا پیمودن این درخت عناصر بعدی را اضافه نمود که با توجه به ارتفاع درخت مرتبه ای لگاریتمی داریم) با ساختار ذکر شده تعداد حالات موجود یا رسیدن به هر برگ هزینه ای برابر با ارتفاع آن درخت دارد که معادل است با :
[tex]\log(\frac{n!}{(\frac{n}{k})!^k})[/tex] و چون کران پایین خواسته شده. داریم :
[tex]\Omega(\log\frac{n!}{(\frac{n}{k})!^k})[/tex]
از تقریب استرلینگ که معادل است با : [tex]\log n!\approx n\: \log n[/tex] و ساده سازی روابط لگاریتمی داریم :
[tex]\Omega(nlogn-k(\frac{n}{k})\times\log(\frac{n}{k}))=(nlogn-nlogn+nlogk)=\Omega(nlogk)[/tex]
گزینه ی ۲ صحیح است
نکته (کتاب نارنجی پوران){برای کمک به حل سوال} : اگر تعداد راه های مختلف ادغام k لیست مرتب n/k ام عنصری و تولید یک لیست مرتب n عنصری خواسته شود داریم :
تعداد n عنصر دارای [tex]n![/tex] جایگشت ولی عناصر هر لیست n/k ام عنصری دارای [tex](\frac{n}{k})![/tex] جایگشت هستند که غیر مجاز است.یعنی نباید عناصر یک لیست جا به جا شوند.چرا؟؟؟ ( چون لیست ها هر کدام مرتب هستند و جابه جایی عناصر این ترتیب را به هم میریزد).و در نهایت چون k jh لیست مرتب وجود دارد. پس تعداد راه های ادغام برابر است با : [tex]\frac{n!}{((\frac{n}{k})!)^k}[/tex]
سوال سوم
با توجه به دو سوال قبل گزینه ی درست را انتخاب کنید و دلیل تفاوت در پاسخ خود را شرح دهید
میخواهیم k لیست مرتب هر کدام با [tex]\frac{n}{k}[/tex] عنصر را در هم ادغام کنیم و یک لیست مرتب nتایی ایجاد نماییم.برای این کار ابتدا لیست ۱ را با لیست ۲ ادغام میکنیم،سپس لیست حاصل را با لیست ۳ و . . . در پایان لیست حاصل را با لیست kام ادغام میکنیم.زمان اجرای این الگوریتم در بدترین حالت بر حسب n و k چقدر است ؟
۱) [tex]O(n)[/tex]
۲) [tex]O(nk)[/tex]
۳) [tex]O(nlogk)[/tex]
۴) [tex]O(klogk)[/tex]
ارسال های بالا کمی بهم ریخته هست، به زودی به کمک تیم مدیریت درست میکنم
دلیل اصلی این بهم ریختگی این بود که من نت رو جز در گوشی نداشتم و نمیتونستم ادامه دهم و خواستم کلا موضوع رو ببندم.
الان شرایط مساعده خداروشکر،و البته دلیل مهم تر در نیمه تمام ماندن بحث بالا این هستش که سوالات اون بخش کاملا با بخش درخت و مرتب سازی ادغام شده که معمولا در انتهای کتاب ساختمان داده به اون پرداخته میشه
موضوع بحث را در اولین فرصت،با رابطه های بازگشتی ادامه میدهیم
سر فصل دوم(روابط بازگشتی)
سوال اول (از کتاب ۶۰۰ مساله)
کدام یک از گزینه های زیر بهترین پاسخ برای رابطه ی بازگشتی [tex]T(n)=T(\frac{n}{4})+T(\frac{3n}{4})+n^2\: ,\: T(1)=1[/tex]
است ؟
۱)[tex]\theta(nlogn)[/tex]
۲)[tex]\theta(n^2logn)[/tex]
۳)[tex]\theta(n^3)[/tex]
۴)[tex]\theta(n^2)[/tex]
سوال۱ ۶۰۰مساله
من تا آخر تیر درگیر هستم و از اون به بعد میتونم فعال تر باشم.
راه حل های مختلف برای به دست آوردن مرتبه ی این روابط هست. اما فرمش شبیه قضیه ی اصلی یا معادله ی همگن و ناهمگن نیست، از تکرار و جایگزینی میتونیم استفاده کنیم و درخت بازگشت. در درخت بازگشت، [tex]t(n)[/tex] از جمع چند تا [tex]t(\frac{n}{a})[/tex] ساخته شده به علاوه ی هزینه ی [tex]t(n)[/tex]، همین طور اون [tex]t(\frac{n}{a})[/tex] هم از جمع توابعی به اون صورت ساخته شده، این شاخه ها رو رسم میکنیم و در هر سطح هزینه رو مینویسیم، هزینه به ازای [tex]t(n)[/tex] برابر با [tex]n^2[/tex] هست، پس به ازای [tex]t(\frac{n}{a})[/tex] میشه [tex](\frac{n}{a})^2[/tex]. معمولا دو تا اتفاق میفته، یا هزینه ی تمامی سطوح برابر با هم هستند و در نتیجه به تعداد سطوح(ارتفاع درخت) اون هزینه رو داریم و حاصل میشه ارتفاع*هزینه ی یک سطر. یا مثل این سوال هزینه ی سطوح یک دنباله ی هندسی رو تشکیل میدهند که جمع میکنیم با هم این هزینه ها رو.
نکته ی ۱: این سوال رو از اون راه حل [tex]\sum\frac{1}{ai}[/tex] نمیتونیم بریم. چون هزینه ی ریشه در درخت، یا در واقع هزینه ی تابع به ازای k=n برابر با n نیست در این جا..
نکته ی ۲: چون در هر سطح هزینه ی متفاوتی به دست میاد پس نباید از این راه بریم که هزینه ی یک سطر رو در ارتفاع ضرب کنیم، هزینه ی تمامی سطوح رو با هم جمع میکنیم.
نکته ی ۳: جمع این هزینه ها، باید تعدادش اندازه ی ارتفاع درخت باشه، یعنی حد بالای [tex]\sum[/tex] میشه همون ارتفاع درخت.
حل: هزینه های سطوح از ریشه تا برگ رو با هم جمع میکنیم:
[tex]n^2+n^2\times(\frac{10}{16})+n^2\times(\frac{10}{16})^2+....=n^2\times\sum(\frac{10}{16})^i=n^2\times\frac{1}{1-\frac{10}{16}}=\theta(n^2)[/tex]
البته همونطور که گفتم i از ۰ شروع میشه تا ارتفاع درخت. (بزرگترین ارتفاع رو در نظر میگیریم، در این جا logn(در مبنای۳/۴) ارتفاع هست.)
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سوال سوم ۶۰۰ مساله (سراسری ۸۶)
رابطه های بازگشتی زیر برای اعداد صحیح [tex]n>2[/tex] تعریف شده اند و داریم [tex]T(0)=T(1)=1[/tex] کدام یک از این رابطه ها، پاسخ چند جمله ای ندارد؟
۱)[tex]T(n)=2T(n-2)+1[/tex]
۲)[tex]T(n)=T(\lfloor\frac{7n}{8}\rfloor)+\: 8n\: +1[/tex]
۳)[tex]T(n)=3T(\lfloor\frac{n}{2}\rfloor)+\: n^2[/tex]
۴)[tex]T(n)=T(n-1)\: +\: n^2[/tex]
پاسخ سوال سوم
====
بررسی مباحث به کار رفته در این سوال :
قانون جایگذاری در روابط بازگشتی : هر بار مقدار داخلی [tex]T(n)[/tex] را در رابطه قرار میدهیم تا به یک حالت کلی برسیم.
یا از نکته ی زیر استفاده کنیم :
نکته : اگر [tex]T(n)=a\: .\: T(n-b)+c\: [/tex] که a و b و c ثابت هستند آنگاه اگر [tex]a\: \ne\: 1[/tex] داریم :
[tex]T(n)\: =\theta(a^{\frac{n}{b}})[/tex]
و اگر [tex]a=1\: ,\: c\ne\: 0\: [/tex] آنگاه :
[tex]T(n)=\theta(n)\: [/tex]
با توجه به نکته ی بالا گزینه ی اول بررسی میشود.و میتوان گفت از مرتبه ی [tex]T(n)=\theta(n^{\frac{n}{2}})\: [/tex] می باشد پس مرتبه چند جمله ای ندارد
قضیه مستر : با فرض [tex]a\ge1\: ,\: b>1\: [/tex] با توجه به رابطه بازگشتی [tex]T(n)=a\: T(\frac{n}{b})+f(n)[/tex] که [tex]\frac{n}{b}[/tex] می تواند به شکل سقف یا کف یا [tex]\frac{n}{b}\pm C\: [/tex] باشد(دقت شود).برای یافتن [tex]T(n)[/tex] داریم :
۱) اگر [tex]f(n)=O(n^{Log\: \alpha-\epsilon})[/tex] که [tex]\epsilon>0\: [/tex] ثابت است ، آنگاه [tex]T(n)=\theta(n^{\log^a_b})[/tex]
۲) اگر [tex]f(n)=\theta(n^{\log_b^a})[/tex] آنگاه : [tex]T(n)=\theta(f(n)\: .\: \log n)=\theta(n^{\log_b^a}\: .\: \log\: n)[/tex]
۳) اگر [tex]f(n)=\Omega\: (n^{\log_b^{a+\epsilon}})[/tex] که [tex]\epsilon>0[/tex] ثابت است و اگر [tex]a\: f(\frac{n}{b})\le Cf(n)[/tex] برای ثابت [tex]C<1[/tex] و n های به اندازه ی کافی بزرگ آنگاه : [tex]T(n)=\theta(f(n))[/tex]
طبف نکات بیان شده گزینه های ۲ و ۳ به ترتیب از مرتبه های : [tex]\theta(n)[/tex] و [tex]\theta(n^2)[/tex] هستند.(در ادامه سوالاتی که با مستر قابل حل نخواهند بود و دلایل حل نشدن آنها شرح داده خواهد شد).
همچنین برای گزینه ی چهارم میشود بنا بر روش جایگذاری و تکرار با شرط اولیه ی [tex]T(1)=1[/tex] به [tex]\sum^n_{i=1}i^2[/tex] رسید.که از مرتبه ی [tex]\theta(n^3)[/tex] است.
نکته : در حالت کلی داریم : [tex]\sum^n_{i=1}i^k=\theta(n^{k+1})[/tex]
پاسخ گزینه ی ۱
سوال چهارم (کتاب نارنجی پوران)
رفتار مجانبی تابع [tex]T(n)[/tex] با توجه به رابطه ی بازگشتی [tex]T(2)=2[/tex] , [tex]T(1)=1[/tex] و [tex]T(n)=T(\frac{n}{2})+T(\lfloor\sqrt{n}\rfloor)+n[/tex] کدام است ؟ می توانید n را توانی از ۲ فرض کنید ؟
۱)[tex]O(n.\log n)[/tex]
۲)[tex]O(n)[/tex]
۳)[tex]O(\log^2n)[/tex]
۴)[tex]O(n\sqrt{n})[/tex]
پاسخ سوال چهارم(*)
اگر به جای [tex]T(\lfloor\sqrt{n}\rfloor)\: [/tex] قرار دهیم [tex]T(\frac{n}{2})\: [/tex] مرتبه ی این تابع طبق مستر [tex]T(n.\log n)\: [/tex] میشود.
اما چون [tex]\sqrt{n}[/tex] از [tex]\frac{n}{2}[/tex] برای [tex]n\ge2[/tex] بزرگتر نیست پس حتما از مرتبه ی [tex]T(n)=O(n.\log n)[/tex] هست ولی امکان دارد این مرتبه کمتر از این باشد!
با صرف نظر از [tex]T(\sqrt{n})[/tex] در مقابل [tex]T(\frac{n}{2})[/tex] پاسخ [tex]O(n)[/tex] است که با جایگذاری اثبات میکنیم.(دقت کنید که باید حدس ما اثبات شود چرا که یکی از گزینه ها میتواند مرتبه ای کمتر از [tex]O(n)[/tex] نیز داشته باشد به [tex]O(\log n)\: ,\: O(\log\log n)[/tex] در مقابل [tex]O(n)[/tex] فکر کنید)
در نهایت باید نشان دهیم:
[tex]T(n)\le Cn[/tex] حال داریم :
[tex]T(n)=T(\frac{n}{2})+T(\sqrt{n})+n\le C\frac{n}{2}+C\sqrt{n}+n[/tex]
که به ازای C=4 داریم :
[tex]4\frac{n}{2}+4\sqrt{n}+n=3n+4\sqrt{n}\le4n[/tex]
=======
با توجه به سوال بالا به سوال زیر فکر کنید و مرتبه ی زمانی آن را بیابید؟!
(MIT یا تمرینات CLRS)
[tex]T(n)=T(\frac{n}{2}+\sqrt{n})+\sqrt{6046}[/tex]
سوال پنجم (*){MIT سال ۲۰۰۵ و سوال ۱۷ پوران نارنجی}
با توجه به رابطه ی [tex]T(n)=T(\frac{n}{3})+T(\frac{n}{6})+\theta(n^{\sqrt{\log n}})[/tex] داریم :
۱) [tex]T(n)=\theta(\log n.n^{\sqrt{\log n}})[/tex]
۲) [tex]T(n)=\theta(n^{\sqrt{\log n}})[/tex]
۳) [tex]T(n)=\theta(n^{\log n})[/tex]
۴) [tex]T(n)=\theta(\sqrt{n}^{\log n})[/tex]
پاسخ سوال پنجم(*)
نکته : دقت کنید که رشد تابعی که نمایی میشود(مثلا [tex]n[/tex] توان باشد) از رشد تمام چند جمله ای ها بیشتر است.
با حدس و استقرا و به ازای [tex]C=2[/tex] می توان ثابت کرد که روابط زیر برقرار هستند :
[tex]T(n)=T(\frac{n}{3})+T(\frac{n}{6})+\theta(n^{\sqrt{\log n}})\le2T(\frac{n}{3})+\theta(n^{\sqrt{\log n}})\: =\theta(n^{\sqrt{\log n}})[/tex]
و
[tex]T(n)=T(\frac{n}{3})+T(\frac{n}{6})+\theta(n^{\sqrt{\log n}})\ge2T(\frac{n}{6})+\theta(n^{\sqrt{\log n}})\: =\theta(n^{\sqrt{\log n}})[/tex]
با توجه به دو نامساوی فوق میتوان در یافت که مرتبه ی زمانی برابر است با [tex]T(n)\: =\theta(n^{\sqrt{\log n}})[/tex]، در واقع ما ثابت کردیم که این تابع هم از مرتبه ی [tex]T(n)\: =O(n^{\sqrt{\log n}})[/tex] و هم از مرتبه ی [tex]T(n)\: =\Omega(n^{\sqrt{\log n}})[/tex] است.
این پاسخ در حل المسائل انگلیسی هم موجود است!
پاسخ گزینه ی ۲
پاسخ فکر کنید:
دو روش برای پاسخ وجود دارد :
شرح روش کلی با استفاده از یک فرض در مثالی که به راحتی با قضیه مستر قاب حل است.
در رابطه ی [tex]T(n)=T(\frac{n}{2})+T(\frac{n}{2})\ +1\equiv T(n)=2T(\frac{n}{2})+1[/tex] ، این تابع همان طور که میدانید با مستر ثابت میشود که از مرتبه ی [tex]O(n)[/tex] است.
میدانیم که مقدار [tex]T(n)=T(\frac{n}{2})+T(\frac{n}{2})\ +1\equiv T(n)=2T(\frac{n}{2})+1[/tex] از مقدار [tex]T(n)=T(\frac{n}{2}+\sqrt{n})+\sqrt{6046}[/tex] بیشتر است . پس باید مقدار [tex]O(n)[/tex] را بهینه تر کنیم.
میتوان فرض کرد که مرتبه ی زمانی تابه ما [tex]O(\log n)[/tex] است، این فرض را با قرار دادن تابع اصلی در بین دو تابع دیگر میتوان به شکل زیر اثبات کرد، داریم :
[tex]T(\frac{n}{2})\le T(\frac{n}{2}+\sqrt{n})\le T(\frac{3n}{4})[/tex] ، با توجه به برقرار بودن این شرایط که در حالت اوی بزرگ به صورت مقابل است : [tex]O(\log_{\frac{4}{3}}n)[/tex] ، میتوان گفت که مرتبه ی این تابع [tex]O(\log n)[/tex] می باشد.
یک روش دیگر هم استفاده از این هم عرضی است که مقدار [tex]\sqrt{n}[/tex] را در مقابل [tex]T(\frac{n}{2})[/tex] نادیده بگیریم که به شکل زیر میشود :
[tex]T(n)=T(\frac{n}{2}+\sqrt{n})+\sqrt{6046} \simeq T(\frac{n}{2})+\theta(1) = \theta(\log n)[/tex]
دقت کنید مقدار [tex]\ sqrt{6046}[/tex] یک ثابت و از مرتبه ی تتا ۱ است.
بنابرین تابع مورد نظر از مرتبه ی [tex]\theta(\log n)[/tex] میباشد.
سوال ششم (*) {سوال ۱۳-۱ از ۶۰۰ سوال}
حل رابطه بازگشتی [tex]\: T(n)=\frac{1}{n}\sum_{i=1}^{n-1}T(i)+3n[/tex] و [tex]\: T(1)=1[/tex] برابر است با :
۱) [tex]O(\log n)[/tex]
۲)[tex]O(n)[/tex]
۳)[tex]O(n\: logn)[/tex]
۴)[tex]O(n^2)[/tex]
سوال ششم (*) {سوال ۱۳-۱ از ۶۰۰ سوال}
سلام.
راه حل اول:
*روابط بازگشتی که تووش [tex]T(n)[/tex] به صورت جمع یک سری به علاوه ی یک هزینه ی اولیه به ازای n نوشته شده که در این جا هزینه به ازای [tex]T(K=n)[/tex] برابر با ۳n هست رو میایم معمولاََ اون رابطه رو به ازای [tex]T(K=n-۱)[/tex] مینویسیم تا به یه رابطه ای بین این دو تا یعنی [tex]T(n-۱)[/tex] و [tex]T(n)[/tex] برسیم و از شر اون سری خلاص بشیم.
توی این جا [tex]T(n)[/tex]:
[tex]T(n)=\frac{1}{n}\Sigma\: T(i)\: +\: 3n[/tex] که i از ۱ تا n-1 هست.
و [tex]T(n-1)[/tex]:
[tex]T(n-1)=\frac{1}{n-1}\Sigma\: T(i)\: +\: 3(n-1)[/tex] و i از ۱ تا n-2 هست.
خب واسه این که یه کم ساده تر بشه و بتونیم تفاوت این دو تا عبارت رو ببینیم به شکل بازتری مینویسیم:
[tex]T(n)=\frac{1}{n}(T(1)+T(2)+T(3)+...+T(n-3)+T(n-2)+T(n-1))\: +\: 3n[/tex]
[tex]T(n-1)=\frac{1}{n-1}(T(1)+T(2)+T(3)+...+T(n-3)+T(n-2))\: +\: 3n-3[/tex]
حالا چون که توی اینجا یه کمی اون n و n-1 اذیت میکنه پس [tex]T(n-1)[/tex] رو در [tex]\frac{(n-1)}{n}[/tex] ضرب میکنیم تا شبیه [tex]T(n)[/tex] بشه و حالا داریم:
[tex]\frac{(n-1)}{n}T(n-1)=\frac{1}{n}(T(1)+T(2)+T(3)+...+T(n-3)+T(n-2))\: +\frac{\: 3(n-1)^2}{n}[/tex]
الان از [tex]T(n)[/tex] میایم این [tex]\frac{(n-1)}{n}T(n-1)[/tex] رو کم میکنیم، پس:
[tex]T(n)-\: \frac{(n-1)}{n}T(n-1)=\frac{\: 1}{n}(T(1)+....T(n-2)+T(n-1))+3n\: -\frac{1}{n}(T(1)+...+T(n-2))-\frac{3(n-1)^2}{n\: }\: =\: [/tex]
[tex]T(n)-\: \frac{(n-1)}{n}T(n-1)=\frac{\: 1}{n}T(n-1)+3n-\frac{3(n-1)^2}{n\: }\: =[/tex]
[tex]T(n)=\: \frac{(n-1)}{n}T(n-1)+\frac{\: 1}{n}T(n-1)+3n-\frac{3(n-1)^2}{n\: }\: =[/tex]
[tex]T(n)=\: \frac{(n-1+1)}{n}T(n-1)+3n-\frac{3(n-1)^2}{n\: }\: =[/tex]
[tex]T(n)=\: T(n-1)+3n-\frac{3(n-1)^2}{n\: }\: =[/tex]
[tex]T(n)=\: T(n-1)+\frac{3n^2\: -\: 3(n-1)^2}{n\: }\: =[/tex]
[tex]T(n)=\: T(n-1)+\theta(1)[/tex]
که این رابطه [tex]\theta(n)[/tex] هست چون n بار فراخوانی داره.
راه حل دوم:
روش استقرا :
مبنای استقرا:[tex]T(1)[/tex] از an+b کوچکتر است.
فرض استقرا: برای n=k نیز همین را داریم و [tex]T(k)[/tex]نیز از an+b کوچکتر است.
مرحله ی استقرا: نشان می دهیم که این مساله برای k+1 نیز صحیح است، در نتیجه میتوان گفت برای n صحیح است.
چرا گفتیم از an+b کوچیکتر باشه؟ حدس میزنم چون که هزینه به ازای [tex]T(n)[/tex] برابر با ۳n هست، خب برای هر [tex]T(k)[/tex]ای هم قطعا از [tex]\theta(n)[/tex] بزرگتر نیست و در نتیجه : [tex]\forall\: k\: \: \: T(k)\le an+b[/tex]
(البته ما مراحل استقرا رو دنبال نکردیم ولی با سطر بالا اثبات شد.)
خب الان میتونیم این طوری بنویسیم:
[tex]T(n)\le\frac{\: 1}{n}\Sigma(an+b)+3n[/tex] که اون سری معادل هست با n-1 تا .an+b. چون به تعداد n-1 تاست از i=1 تا i=n-1
الان [tex]T(n)\le\frac{\: 1}{n}\Sigma(an+b)+3n=\frac{\: 1}{n}((n-1)(an+b))+3n[/tex]
[tex]T(n)\le\frac{\: 1}{n}\Sigma(an+b)+3n=\frac{\: 1}{n}((n-1)(an+b))+3n=\frac{1}{n}(an(n-1)+b(n-1))+3n[/tex]
[tex]T(n)\le\frac{\: 1}{n}\Sigma(an+b)+3n=\frac{\: 1}{n}((n-1)(an+b))+3n=\frac{1}{n}(an(n-1)+b(n-1))+3n=a(n-1)+\frac{b(n-1)}{n}+3n=\: (a+3)n\: +b\cdot teta(1)-a\: =\: a.n+b[/tex]
حالا چون [tex]T(n)[/tex] هم از an+b کوچیکتر شد پس از مرتبه ی [tex]\theta(n)[/tex] هست.
سوال هفتم (*){سوال ۱۳ کتاب نارنجی} "بسیار مهم" [ این سوال مصداقی از سوالات ۶/۱ و ۱۸/۱ در ۶۰۰ مساله و چندین دوره از سوالات سراسری میباشد]
فرض کنید [tex]T(n)\: =\sum^k_{i=1}a_i.T(\frac{n}{b_i})+cn\: [/tex] که [tex]a_i[/tex] ها و [tex]b_i[/tex] ها ثابت هستند و [tex]1-\sum^k_{i=1}\frac{a_i}{b_i}>0[/tex] آنگاه :
۱) [tex]T(n)=O(n)[/tex]
۲)[tex]T(n)=O(n.\log n)[/tex]
۳)[tex]T(n)=O(\log n)[/tex]
۴)[tex]T(n)=O(n^2)[/tex]
سوال هفتم (*) {سوال ۱۳-۲ از نارنجی پوران}
راه حل اول:
توی صورت سوال نوشته شده که : [tex]1-\sum_{i=1}^k\frac{ai}{bi\: }>\: 0[/tex]
که یعنی: [tex]1>\: \sum^k_{i=1}\frac{ai}{bi}[/tex]
خب یه قضیه ای داشتیم که این بود:
برای رابطه ی : [tex]T(n)=\sum^k_{i=1}T(\frac{n}{ai})+\theta(n)[/tex]
اگر : [tex]\sum_{i=1}^{k\: }\frac{1}{ai}\: <1[/tex] آنگاه [tex]T(n)=O(n)[/tex]
اگر :[tex]\sum_{i=1}^{k\: }\frac{1}{ai}\: =1[/tex] آنگاه [tex]T(n)=O(nlogn)[/tex]
حالا این جا هم درست شبیه همون قضیه هست، b و a دو تا ثابت هستند، تابع [tex]T(n)[/tex] به صورت جمع تعدادی [tex]ai\: T(\frac{n}{bi})[/tex] هست که اینجا [tex]1>\: \sum^k_{i=1}\frac{ai}{bi}[/tex]
اگر تمامی ai ها برابر با ۱ باشه که درست میشه همون قضیه ی بالا و با توجه به این که [tex]\sum_{i=1}^k\frac{ai}{bi}=\sum^k_{i=1}\frac{1}{bi}<1[/tex] پس [tex]T(n)=\theta(n)[/tex]
در غیر اینطورت یعنی اگر ai ها برابر با ۱ نباشند چطور؟
فرض کنیم k=3 باشه مثلاََ.
خب حالا رابطه به این فرم میشه:
[tex]T(n)=\sum^3_{i=1}ai.\: T(\frac{n}{bi})+cn[/tex]
[tex]T(n)=a1.T(\frac{n}{b1})+a2.T(\frac{n}{b2})+a3.T(\frac{n}{b3})+cn[/tex]
خب اعدادی برای b1,b2,b3 و a1,a2,a3 بگذاریم که شرط [tex]1>\: \sum^k_{i=1}\frac{ai}{bi}[/tex] برقرار باشه، این رابطه رو به صورت درخت بازگشت حل کنیم حتما جمع هزینه ها ی هر سطر برابر میشه جمع جمله های یک سری هندسی با قدرنسبت کوچکتر از ۱، در نتیجه تابع از مرتبه ی [tex]O(n)[/tex] میشه.
پس تابع از مرتبه [tex]O(n)[/tex] هست.
راه حل دوم:
(تستی)
k که هر چیزی میتونه باشه، ۱ در نظر میگیریمش.
حالا داریم: [tex]T(n)=\: a1.T(\frac{n}{b1})+cn\: [/tex]
از طرفی طبق صورت سوال داریم :[tex]\sum_{i=1}^k\frac{ai}{bi}<1[/tex] و این یعنی [tex]\frac{a1}{b1}<1[/tex]
حالا مرتبه رو میخوایم با قضیه ی اصلی (master) به دست بیاریم. [tex]f(n)[/tex] رو با [tex]n^{\log^{a1}_{b1}}[/tex] مقایسه میکنیم. با توجه به این که[tex]\frac{a1}{b1}<1[/tex] ، پس : [tex]n^{\log^{a1}_{b1}}<\: n^1[/tex] و این یعنی [tex]T(n)=\theta(f(n))=\theta(n)[/tex]
راه حل سوم:
(تستی)
در نظر می گیریم که k یک نیست ولی [tex]b_i[/tex] بینهایت هست یا [tex]a_i[/tex] صفر هست (یا هر دو همزمان)، که این با توجه به شرایط صورت مساله یعنی[tex]\sum_{i=1}^k\frac{ai}{bi}<1[/tex]هم درست هست، حالا [tex]a_iT(\frac{n}{b_i})[/tex] برابر با صفر میشه و تنها چیزی که از [tex]^{ }T(n)=\sum^k_{i=1}a_i.T(\frac{n}{b_1})+cn[/tex] میمونه [tex]^{ }T(n)=cn[/tex] هست، در نتیجه [tex]^{ }T(n)=O(n)[/tex]
ضمن سپاس از پاسخ کاربر Pure Liveliness :
=====
بنابر "بسیار مهم" بودن سوال هفتم و البته با توجه به این که در دوره های متوالی و در کتاب های متعددی این سوال و سوالات بسیار نزدیک با منطق این سوال مورد بررسی قرار گرفته پاسخ چهارمی با منطقِ آنچه که کاربر Pure Liveliness ارائه داد در این جا خدمت دوستان دنبال کننده میگذارم :
راه حل چهارم سوال هفتم
فرض میکنیم تمام [tex]a_i[/tex] ها برابر باشند داریم :
[tex]T(n)=T(\frac{n}{a})+T(\frac{n}{a})+.\: .\: .+T(\frac{n}{a})+\theta(n)[/tex] یعنی Kتا [tex]T(\frac{n}{a})[/tex] داشته باشیم که میشود :
[tex]T(n)=kT(\frac{n}{a})+\theta(n)[/tex] و این بیانی دیگر از سیگما هست. در صورتی که داشته باشیم :
[tex]T(n)=\sum^k_{i=1}T(\frac{n}{a_i})+\theta(n)[/tex] که کاملا منطبق هست با سوال ۱۸/۱ در ۶۰۰ مساله که پاسخ های کامل آن را میشود به صورت زیر ارائه داد.
با توجه به قضیه ی مستر حالات زیر برقرار است :
۱) [tex]T(n)=\theta(n)\: \: if\: \: k<a[/tex]
۲)[tex]T(n)=\theta(n.logn)\: \: if\: \: k=a[/tex]
۳)[tex]T(n)=\theta(n^{\log_a^k})\: \: if\: \: k>a[/tex]
حال آنچه که این سوال را از سوال ۱۸/۱ متمایز میکند شرط مقابل است [tex]1-\sum^k_{i=1}\frac{a_i}{b_i}>0[/tex]
همان گونه که مشاهده میشود علاوه بر ثابت [tex]a_i[/tex] ثابت [tex]b_i[/tex] نیز اضافه شده است. ما اگر مقدار ثابت [tex]a_i[/tex] را با مقادیر برابر ست کنیم، میشود مقادیر [tex]b_i[/tex] را متفاوت در نظر گرفت این تمایز باعث میشود شرط سوال متفاوت تر از سوالات پیشین به نظر برسد : (ضمن دقت در نکته ی زیر از پوران):
نکته : رابطه ی بازگشتی : [tex]T(n)=T(\alpha n)+T(\beta n)+n[/tex] که [tex]\alpha\: ,\: \beta[/tex] ثابت هستندمفروض است اگر [tex]\alpha+\beta=1[/tex] داریم [tex]T(n)=\theta(n.\log n)[/tex] و اگر [tex]\alpha+\beta<1[/tex] آنگاه [tex]T(n)=\theta(n)[/tex]
حال با دقت در شرط سوال و پاسخ کتاب نارنجی پوران و مثال ارائه شده در این کتاب میتوان پی برد که شرط مذکور در سوال بیانگر همان مقدار :
[tex]\alpha+\beta<1[/tex] می باشد یعنی داریم : [tex]\alpha+\beta<1\: \equiv\: \sum^k_{i=1}\frac{a_i}{b_i}<1[/tex]
حل مثال زیر با مقادیر [tex]k=2[/tex] و [tex]a_1=a_2=1\: [/tex] و [tex]b_1=5[/tex] و [tex]b_2=\frac{10}{7}[/tex] که رابطه ی بازگشتی زیر را میسازد [tex]T(n)=T(\frac{n}{5})+T(\frac{7n}{10})+cn[/tex] با درخت بازگشت اثباتی برای ادعای بالا است. که مرتبه ی سوال برابر است با :
[tex]T(n)=O(n)[/tex] و گزینه ی اول پاسخ صحیح است