ارسال های بالا کمی بهم ریخته هست، به زودی به کمک تیم مدیریت درست میکنم
دلیل اصلی این بهم ریختگی این بود که من نت رو جز در گوشی نداشتم و نمیتونستم ادامه دهم و خواستم کلا موضوع رو ببندم.
الان شرایط مساعده خداروشکر،و البته دلیل مهم تر در نیمه تمام ماندن بحث بالا این هستش که سوالات اون بخش کاملا با بخش درخت و مرتب سازی ادغام شده که معمولا در انتهای کتاب ساختمان داده به اون پرداخته میشه
موضوع بحث را در اولین فرصت،با رابطه های بازگشتی ادامه میدهیم

---

سر فصل دوم(روابط بازگشتی)
سوال اول (از کتاب ۶۰۰ مساله)
کدام یک از گزینه های زیر بهترین پاسخ برای رابطه ی بازگشتی $T(n)=T(\frac{n}{4})+T(\frac{3n}{4})+n^2\: ,\: T(1)=1$
است ؟
۱)$\theta(nlogn)$
۲)$\theta(n^2logn)$
۳)$\theta(n^3)$
۴)$\theta(n^2)$

سوال سوم ۶۰۰ مساله (سراسری ۸۶)
رابطه های بازگشتی زیر برای اعداد صحیح $n>2$ تعریف شده اند و داریم $T(0)=T(1)=1$ کدام یک از این رابطه ها، پاسخ چند جمله ای ندارد؟
۱)$T(n)=2T(n-2)+1$
۲)$T(n)=T(\lfloor\frac{7n}{8}\rfloor)+\: 8n\: +1$
۳)$T(n)=3T(\lfloor\frac{n}{2}\rfloor)+\: n^2$
۴)$T(n)=T(n-1)\: +\: n^2$

پاسخ سوال دوم(*)

با توجه به تشریح سوال داریم: تعداد لیست های موجود kتا است که هر کدام $\frac{n}{k}$ عنصر دارند. پس تعداد لیست های موجود برابر است با : $(\frac{n}{k})^k$

حال برای ادغام این لیست ها هر کدام از این لیست ها میتوانند با هم ترکیب شوند که داریم : $(\frac{n}{k})\: !\: ^k$ در کل تعداد حالات برابر است با :

$\frac{n!}{(\frac{n}{k})!^k}$

با توجه به ایده ی موجود در سوال قبلی برای پیمودن درختی(با توجه به مرتب بودن عناصر میشود با حذف بزرگترین عناصر هر لیست از آن ها یک هرم بیشینه ساخت و پس از آن پا پیمودن این درخت عناصر بعدی را اضافه نمود که با توجه به ارتفاع درخت مرتبه ای لگاریتمی داریم) با ساختار ذکر شده تعداد حالات موجود یا رسیدن به هر برگ هزینه ای برابر با ارتفاع آن درخت دارد که معادل است با :
$\log(\frac{n!}{(\frac{n}{k})!^k})$ و چون کران پایین خواسته شده. داریم :

$\Omega(\log\frac{n!}{(\frac{n}{k})!^k})$

از تقریب استرلینگ که معادل است با : $\log n!\approx n\: \log n$ و ساده سازی روابط لگاریتمی داریم :
$\Omega(nlogn-k(\frac{n}{k})\times\log(\frac{n}{k}))=(nlogn-nlogn+nlogk)=\Omega(nlogk)$

گزینه ی ۲ صحیح است
نکته (کتاب نارنجی پوران){برای کمک به حل سوال} : اگر تعداد راه های مختلف ادغام k لیست مرتب n/k ام عنصری و تولید یک لیست مرتب n عنصری خواسته شود داریم :
تعداد n عنصر دارای $n!$ جایگشت ولی عناصر هر لیست n/k ام عنصری دارای $(\frac{n}{k})!$ جایگشت هستند که غیر مجاز است.یعنی نباید عناصر یک لیست جا به جا شوند.چرا؟؟؟ ( چون لیست ها هر کدام مرتب هستند و جابه جایی عناصر این ترتیب را به هم میریزد).و در نهایت چون k jh لیست مرتب وجود دارد. پس تعداد راه های ادغام برابر است با : $\frac{n!}{((\frac{n}{k})!)^k}$

---

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

میخواهیم k لیست مرتب هر کدام با $\frac{n}{k}$ عنصر را در هم ادغام کنیم و یک لیست مرتب nتایی ایجاد نماییم.برای این کار ابتدا لیست ۱ را با لیست ۲ ادغام میکنیم،سپس لیست حاصل را با لیست ۳ و . . . در پایان لیست حاصل را با لیست kام ادغام میکنیم.زمان اجرای این الگوریتم در بدترین حالت بر حسب n و k چقدر است ؟
۱) $O(n)$
۲) $O(nk)$
۳) $O(nlogk)$
۴) $O(klogk)$

سوال۱ ۶۰۰مساله
من تا آخر تیر درگیر هستم و از اون به بعد میتونم فعال تر باشم.

راه حل های مختلف برای به دست آوردن مرتبه ی این روابط هست. اما فرمش شبیه قضیه ی اصلی یا معادله ی همگن و ناهمگن نیست، از تکرار و جایگزینی میتونیم استفاده کنیم و درخت بازگشت. در درخت بازگشت، $t(n)$ از جمع چند تا $t(\frac{n}{a})$ ساخته شده به علاوه ی هزینه ی $t(n)$، همین طور اون $t(\frac{n}{a})$ هم از جمع توابعی به اون صورت ساخته شده، این شاخه ها رو رسم میکنیم و در هر سطح هزینه رو مینویسیم، هزینه به ازای $t(n)$ برابر با $n^2$ هست، پس به ازای $t(\frac{n}{a})$ میشه $(\frac{n}{a})^2$. معمولا دو تا اتفاق میفته، یا هزینه ی تمامی سطوح برابر با هم هستند و در نتیجه به تعداد سطوح(ارتفاع درخت) اون هزینه رو داریم و حاصل میشه ارتفاع*هزینه ی یک سطر. یا مثل این سوال هزینه ی سطوح یک دنباله ی هندسی رو تشکیل میدهند که جمع میکنیم با هم این هزینه ها رو.

نکته ی ۱: این سوال رو از اون راه حل $\sum\frac{1}{ai}$ نمیتونیم بریم. چون هزینه ی ریشه در درخت، یا در واقع هزینه ی تابع به ازای k=n برابر با n نیست در این جا..
نکته ی ۲: چون در هر سطح هزینه ی متفاوتی به دست میاد پس نباید از این راه بریم که هزینه ی یک سطر رو در ارتفاع ضرب کنیم، هزینه ی تمامی سطوح رو با هم جمع میکنیم.
نکته ی ۳: جمع این هزینه ها، باید تعدادش اندازه ی ارتفاع درخت باشه، یعنی حد بالای $\sum$ میشه همون ارتفاع درخت.
حل: هزینه های سطوح از ریشه تا برگ رو با هم جمع میکنیم:
$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)$
البته همونطور که گفتم i از ۰ شروع میشه تا ارتفاع درخت. (بزرگترین ارتفاع رو در نظر میگیریم، در این جا logn(در مبنای۳/۴) ارتفاع هست.)

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

پاسخ سوال سوم
====
بررسی مباحث به کار رفته در این سوال :
قانون جایگذاری در روابط بازگشتی : هر بار مقدار داخلی $T(n)$ را در رابطه قرار میدهیم تا به یک حالت کلی برسیم.
یا از نکته ی زیر استفاده کنیم :
نکته : اگر $T(n)=a\: .\: T(n-b)+c\:$ که a و b و c ثابت هستند آنگاه اگر $a\: \ne\: 1$ داریم :
$T(n)\: =\theta(a^{\frac{n}{b}})$
و اگر $a=1\: ,\: c\ne\: 0\:$ آنگاه :
$T(n)=\theta(n)\:$
با توجه به نکته ی بالا گزینه ی اول بررسی میشود.و میتوان گفت از مرتبه ی $T(n)=\theta(n^{\frac{n}{2}})\:$ می باشد پس مرتبه چند جمله ای ندارد
قضیه مستر : با فرض $a\ge1\: ,\: b>1\:$ با توجه به رابطه بازگشتی $T(n)=a\: T(\frac{n}{b})+f(n)$ که $\frac{n}{b}$ می تواند به شکل سقف یا کف یا $\frac{n}{b}\pm C\:$ باشد(دقت شود).برای یافتن $T(n)$ داریم :
۱) اگر $f(n)=O(n^{Log\: \alpha-\epsilon})$ که $\epsilon>0\:$ ثابت است ، آنگاه $T(n)=\theta(n^{\log^a_b})$

۲) اگر $f(n)=\theta(n^{\log_b^a})$ آنگاه : $T(n)=\theta(f(n)\: .\: \log n)=\theta(n^{\log_b^a}\: .\: \log\: n)$

۳) اگر $f(n)=\Omega\: (n^{\log_b^{a+\epsilon}})$ که $\epsilon>0$ ثابت است و اگر $a\: f(\frac{n}{b})\le Cf(n)$ برای ثابت $C<1$ و n های به اندازه ی کافی بزرگ آنگاه : $T(n)=\theta(f(n))$

طبف نکات بیان شده گزینه های ۲ و ۳ به ترتیب از مرتبه های : $\theta(n)$ و $\theta(n^2)$ هستند.(در ادامه سوالاتی که با مستر قابل حل نخواهند بود و دلایل حل نشدن آنها شرح داده خواهد شد).
همچنین برای گزینه ی چهارم میشود بنا بر روش جایگذاری و تکرار با شرط اولیه ی $T(1)=1$ به $\sum^n_{i=1}i^2$ رسید.که از مرتبه ی $\theta(n^3)$ است.
نکته : در حالت کلی داریم : $\sum^n_{i=1}i^k=\theta(n^{k+1})$
پاسخ گزینه ی ۱

سوال چهارم (کتاب نارنجی پوران)
رفتار مجانبی تابع $T(n)$ با توجه به رابطه ی بازگشتی $T(2)=2$ , $T(1)=1$ و $T(n)=T(\frac{n}{2})+T(\lfloor\sqrt{n}\rfloor)+n$ کدام است ؟ می توانید n را توانی از ۲ فرض کنید ؟

۱)$O(n.\log n)$
۲)$O(n)$
۳)$O(\log^2n)$
۴)$O(n\sqrt{n})$

پاسخ سوال چهارم(*)
اگر به جای $T(\lfloor\sqrt{n}\rfloor)\:$ قرار دهیم $T(\frac{n}{2})\:$ مرتبه ی این تابع طبق مستر $T(n.\log n)\:$ میشود.
اما چون $\sqrt{n}$ از $\frac{n}{2}$ برای $n\ge2$ بزرگتر نیست پس حتما از مرتبه ی $T(n)=O(n.\log n)$ هست ولی امکان دارد این مرتبه کمتر از این باشد!
با صرف نظر از $T(\sqrt{n})$ در مقابل $T(\frac{n}{2})$ پاسخ $O(n)$ است که با جایگذاری اثبات میکنیم.(دقت کنید که باید حدس ما اثبات شود چرا که یکی از گزینه ها میتواند مرتبه ای کمتر از $O(n)$ نیز داشته باشد به $O(\log n)\: ,\: O(\log\log n)$ در مقابل $O(n)$ فکر کنید)
در نهایت باید نشان دهیم:
$T(n)\le Cn$ حال داریم :
$T(n)=T(\frac{n}{2})+T(\sqrt{n})+n\le C\frac{n}{2}+C\sqrt{n}+n$
که به ازای C=4 داریم :
$4\frac{n}{2}+4\sqrt{n}+n=3n+4\sqrt{n}\le4n$
=======
با توجه به سوال بالا به سوال زیر فکر کنید و مرتبه ی زمانی آن را بیابید؟!
(MIT یا تمرینات CLRS)

$T(n)=T(\frac{n}{2}+\sqrt{n})+\sqrt{6046}$

---

سوال پنجم (*){MIT سال ۲۰۰۵ و سوال ۱۷ پوران نارنجی}
با توجه به رابطه ی $T(n)=T(\frac{n}{3})+T(\frac{n}{6})+\theta(n^{\sqrt{\log n}})$ داریم :
۱) $T(n)=\theta(\log n.n^{\sqrt{\log n}})$
۲) $T(n)=\theta(n^{\sqrt{\log n}})$
۳) $T(n)=\theta(n^{\log n})$
۴) $T(n)=\theta(\sqrt{n}^{\log n})$

پاسخ سوال ۴ )

این سوال با روش های مختلفی قابل حل است . اما روشی که شهود بیشتری میدهد روش درختی ست .

می دانیم برای n های بزرگتر از یک سرعت به مقدار ثابت رسیدن $T(\sqrt{n})$ در برابر $T(\frac{n}{2})$
بسیار بیشتر میباشد .

مثلا برای n=1000 داریم :

$T(\frac{n}{2})=T(\frac{1000}{2})=500,250,125,62.5,31.25,15.125,7.5,3.75,1.75$

$T(\sqrt{n})=T(\sqrt{1000})=31.62,5.62,2.37,1.53$

در نتیجه ارتفاع درخت را $T(\frac{n}{2})$
مشخص میکند که طول بیشتری دارد .

پس می توان در این رابطه از $T(\sqrt{n})$ صرف نظر کرد:
$T(n)=T(\frac{n}{2})+n$

که با توجه به قضیه مستر مرتبه این رابطه $\theta(n)$ می باشد.[/align][/size]

پاسخ سوال پنجم(*)
نکته : دقت کنید که رشد تابعی که نمایی میشود(مثلا $n$ توان باشد) از رشد تمام چند جمله ای ها بیشتر است.
با حدس و استقرا و به ازای $C=2$ می توان ثابت کرد که روابط زیر برقرار هستند :
$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}})$
و
$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}})$

با توجه به دو نامساوی فوق میتوان در یافت که مرتبه ی زمانی برابر است با $T(n)\: =\theta(n^{\sqrt{\log n}})$، در واقع ما ثابت کردیم که این تابع هم از مرتبه ی $T(n)\: =O(n^{\sqrt{\log n}})$ و هم از مرتبه ی $T(n)\: =\Omega(n^{\sqrt{\log n}})$ است.

این پاسخ در حل المسائل انگلیسی هم موجود است!
پاسخ گزینه ی ۲

پاسخ فکر کنید:
دو روش برای پاسخ وجود دارد :
شرح روش کلی با استفاده از یک فرض در مثالی که به راحتی با قضیه مستر قاب حل است.
در رابطه ی $T(n)=T(\frac{n}{2})+T(\frac{n}{2})\ +1\equiv T(n)=2T(\frac{n}{2})+1$ ، این تابع همان طور که میدانید با مستر ثابت میشود که از مرتبه ی $O(n)$ است.
میدانیم که مقدار $T(n)=T(\frac{n}{2})+T(\frac{n}{2})\ +1\equiv T(n)=2T(\frac{n}{2})+1$ از مقدار $T(n)=T(\frac{n}{2}+\sqrt{n})+\sqrt{6046}$ بیشتر است . پس باید مقدار $O(n)$ را بهینه تر کنیم.
میتوان فرض کرد که مرتبه ی زمانی تابه ما $O(\log n)$ است، این فرض را با قرار دادن تابع اصلی در بین دو تابع دیگر میتوان به شکل زیر اثبات کرد، داریم :
$T(\frac{n}{2})\le T(\frac{n}{2}+\sqrt{n})\le T(\frac{3n}{4})$ ، با توجه به برقرار بودن این شرایط که در حالت اوی بزرگ به صورت مقابل است : $O(\log_{\frac{4}{3}}n)$ ، میتوان گفت که مرتبه ی این تابع $O(\log n)$ می باشد.
یک روش دیگر هم استفاده از این هم عرضی است که مقدار $\sqrt{n}$ را در مقابل $T(\frac{n}{2})$ نادیده بگیریم که به شکل زیر میشود :
$T(n)=T(\frac{n}{2}+\sqrt{n})+\sqrt{6046} \simeq T(\frac{n}{2})+\theta(1) = \theta(\log n)$
دقت کنید مقدار $\ sqrt{6046}$ یک ثابت و از مرتبه ی تتا ۱ است.
بنابرین تابع مورد نظر از مرتبه ی $\theta(\log n)$ میباشد.

سوال ششم (*) {سوال ۱۳-۱ از ۶۰۰ سوال}
حل رابطه بازگشتی $\: T(n)=\frac{1}{n}\sum_{i=1}^{n-1}T(i)+3n$ و $\: T(1)=1$ برابر است با :

۱) $O(\log n)$

۲)$O(n)$

۳)$O(n\: logn)$

۴)$O(n^2)$

سوال ششم (*) {سوال ۱۳-۱ از ۶۰۰ سوال}
سلام.
راه حل اول:
*روابط بازگشتی که تووش $T(n)$ به صورت جمع یک سری به علاوه ی یک هزینه ی اولیه به ازای n نوشته شده که در این جا هزینه به ازای $T(K=n)$ برابر با ۳n هست رو میایم معمولاََ اون رابطه رو به ازای $T(K=n-۱)$ مینویسیم تا به یه رابطه ای بین این دو تا یعنی $T(n-۱)$ و $T(n)$ برسیم و از شر اون سری خلاص بشیم.
توی این جا $T(n)$:
$T(n)=\frac{1}{n}\Sigma\: T(i)\: +\: 3n$ که i از ۱ تا n-1 هست.
و $T(n-1)$:
$T(n-1)=\frac{1}{n-1}\Sigma\: T(i)\: +\: 3(n-1)$ و i از ۱ تا n-2 هست.

خب واسه این که یه کم ساده تر بشه و بتونیم تفاوت این دو تا عبارت رو ببینیم به شکل بازتری مینویسیم:
$T(n)=\frac{1}{n}(T(1)+T(2)+T(3)+...+T(n-3)+T(n-2)+T(n-1))\: +\: 3n$
$T(n-1)=\frac{1}{n-1}(T(1)+T(2)+T(3)+...+T(n-3)+T(n-2))\: +\: 3n-3$

حالا چون که توی اینجا یه کمی اون n و n-1 اذیت میکنه پس $T(n-1)$ رو در $\frac{(n-1)}{n}$ ضرب میکنیم تا شبیه $T(n)$ بشه و حالا داریم:
$\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}$
الان از $T(n)$ میایم این $\frac{(n-1)}{n}T(n-1)$ رو کم میکنیم، پس:
$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\: }\: =\:$
$T(n)-\: \frac{(n-1)}{n}T(n-1)=\frac{\: 1}{n}T(n-1)+3n-\frac{3(n-1)^2}{n\: }\: =$
$T(n)=\: \frac{(n-1)}{n}T(n-1)+\frac{\: 1}{n}T(n-1)+3n-\frac{3(n-1)^2}{n\: }\: =$
$T(n)=\: \frac{(n-1+1)}{n}T(n-1)+3n-\frac{3(n-1)^2}{n\: }\: =$
$T(n)=\: T(n-1)+3n-\frac{3(n-1)^2}{n\: }\: =$
$T(n)=\: T(n-1)+\frac{3n^2\: -\: 3(n-1)^2}{n\: }\: =$
$T(n)=\: T(n-1)+\theta(1)$
که این رابطه $\theta(n)$ هست چون n بار فراخوانی داره.

---

راه حل دوم:
روش استقرا :
مبنای استقرا:$T(1)$ از an+b کوچکتر است.
فرض استقرا: برای n=k نیز همین را داریم و $T(k)$نیز از an+b کوچکتر است.
مرحله ی استقرا: نشان می دهیم که این مساله برای k+1 نیز صحیح است، در نتیجه میتوان گفت برای n صحیح است.
چرا گفتیم از an+b کوچیکتر باشه؟ حدس میزنم چون که هزینه به ازای $T(n)$ برابر با ۳n هست، خب برای هر $T(k)$ای هم قطعا از $\theta(n)$ بزرگتر نیست و در نتیجه : $\forall\: k\: \: \: T(k)\le an+b$
(البته ما مراحل استقرا رو دنبال نکردیم ولی با سطر بالا اثبات شد.)
خب الان میتونیم این طوری بنویسیم:
$T(n)\le\frac{\: 1}{n}\Sigma(an+b)+3n$ که اون سری معادل هست با n-1 تا .an+b. چون به تعداد n-1 تاست از i=1 تا i=n-1
الان $T(n)\le\frac{\: 1}{n}\Sigma(an+b)+3n=\frac{\: 1}{n}((n-1)(an+b))+3n$
$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$
$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$
حالا چون $T(n)$ هم از an+b کوچیکتر شد پس از مرتبه ی $\theta(n)$ هست.

پاسخ سوال دهم

برای شرط $i^2\le\: N$ میتوان گفت که چون i با سرعت بیشتری به N می رسد پس از مرتبه ی N نخواهد بود(در کتاب ۶۰۰ گزینه ها متفاوت از کتاب نارنجی هستند و مرتبه ی $O(N)$ نیز مطرح است ) یا میتوان گفت از طرفین رابطه $i^2\le\: N$ رادیکال میگیریم و البته با در نظر گرفتن این موضوع که i هر بار ۲ واحد اضافه میشود. که به دست می آید :
$\frac{\sqrt{N}}{2}$
بنابراین مرتبه ی کد : $O(\sqrt{N})$ است.

پاسخ سوال یازدهم

حلقه ی بیرونی $\log n$ بار تکرار میشود و حلقه ی درونی $\log i$ چون در حلقه ی درونی i را داخل j قرار میدهیم.

---

سوال سیزدهم(*) سوال ۷۸-۱ از ۶۰۰
چند تا از گزاره های زیر درست است؟[
۱) تفاوت زمان اجرای هر الگوریتم قطعی در بدترین حالت و حالت میانگین تنها در ضریب ثابتشان است

۲)تابع های $f(n)$ و $g(n)$ وجود دارند به طوری که $f(n)=O(g(n))$ و $f(n)=\omega(g(n))$

۳) اگر $f(n)=\sqrt{n}$ و $g(n)=n.(n\: \mod\: 100)$ در آن صورت $f(n)=O(g(n))$


۱)۰
۲)۱
۳)۲
۴)۳

---

سوال چهاردهم (سوال ۱۳ فصل اول کتاب نارنجی)

فرض کنید آرایه $A[1...n]\:$ یا همه ی عناصرش صفر است یا $\frac{n}{2}$ صفر و $\frac{n}{2}$ یک، اگر بخواهیم با احتمال حداقل $\frac{3}{4}$ مشخص کنیم آرایه A کدام نوع است . باید چند درایه از A بخوانیم و بررسی کنیم؟

۱)$\frac{n}{2}+1$
۲)$\frac{n}{4}+1$
۳)۲
۴)۴
سوال چهاردهم پایان مبحث فصل اول(روابط بازگشتی)

---

در ادامه ی سوالات دو بخش مرتب سازی و تقسیم و غلبه و مرتبه های اماری به دلیل نزدیکی و تداخل مباحث با هم مورد بررسی دقیق قرار میگیرد،برای مرتب سازی هایی که از درخت استفاده میشود سعی بر آن است که مباحث مقدماتی لازم به کلی توضیح داده شود

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

سوال هفتم (*){سوال ۱۳ کتاب نارنجی} "بسیار مهم" [ این سوال مصداقی از سوالات ۶/۱ و ۱۸/۱ در ۶۰۰ مساله و چندین دوره از سوالات سراسری میباشد]

فرض کنید $T(n)\: =\sum^k_{i=1}a_i.T(\frac{n}{b_i})+cn\:$ که $a_i$ ها و $b_i$ ها ثابت هستند و $1-\sum^k_{i=1}\frac{a_i}{b_i}>0$ آنگاه :

۱) $T(n)=O(n)$

۲)$T(n)=O(n.\log n)$

۳)$T(n)=O(\log n)$

۴)$T(n)=O(n^2)$

سوال هفتم (*) {سوال ۱۳-۲ از نارنجی پوران}

راه حل اول:

توی صورت سوال نوشته شده که : $1-\sum_{i=1}^k\frac{ai}{bi\: }>\: 0$
که یعنی: $1>\: \sum^k_{i=1}\frac{ai}{bi}$
خب یه قضیه ای داشتیم که این بود:
برای رابطه ی : $T(n)=\sum^k_{i=1}T(\frac{n}{ai})+\theta(n)$
اگر : $\sum_{i=1}^{k\: }\frac{1}{ai}\: <1$ آنگاه $T(n)=O(n)$
اگر :$\sum_{i=1}^{k\: }\frac{1}{ai}\: =1$ آنگاه $T(n)=O(nlogn)$
حالا این جا هم درست شبیه همون قضیه هست، b و a دو تا ثابت هستند، تابع $T(n)$ به صورت جمع تعدادی $ai\: T(\frac{n}{bi})$ هست که اینجا $1>\: \sum^k_{i=1}\frac{ai}{bi}$
اگر تمامی ai ها برابر با ۱ باشه که درست میشه همون قضیه ی بالا و با توجه به این که $\sum_{i=1}^k\frac{ai}{bi}=\sum^k_{i=1}\frac{1}{bi}<1$ پس $T(n)=\theta(n)$
در غیر اینطورت یعنی اگر ai ها برابر با ۱ نباشند چطور؟
فرض کنیم k=3 باشه مثلاََ.
خب حالا رابطه به این فرم میشه:
$T(n)=\sum^3_{i=1}ai.\: T(\frac{n}{bi})+cn$
$T(n)=a1.T(\frac{n}{b1})+a2.T(\frac{n}{b2})+a3.T(\frac{n}{b3})+cn$
خب اعدادی برای b1,b2,b3 و a1,a2,a3 بگذاریم که شرط $1>\: \sum^k_{i=1}\frac{ai}{bi}$ برقرار باشه، این رابطه رو به صورت درخت بازگشت حل کنیم حتما جمع هزینه ها ی هر سطر برابر میشه جمع جمله های یک سری هندسی با قدرنسبت کوچکتر از ۱، در نتیجه تابع از مرتبه ی $O(n)$ میشه.
پس تابع از مرتبه $O(n)$ هست.

---

راه حل دوم:
(تستی)
k که هر چیزی میتونه باشه، ۱ در نظر میگیریمش.
حالا داریم: $T(n)=\: a1.T(\frac{n}{b1})+cn\:$
از طرفی طبق صورت سوال داریم :$\sum_{i=1}^k\frac{ai}{bi}<1$ و این یعنی $\frac{a1}{b1}<1$
حالا مرتبه رو میخوایم با قضیه ی اصلی (master) به دست بیاریم. $f(n)$ رو با $n^{\log^{a1}_{b1}}$ مقایسه میکنیم. با توجه به این که$\frac{a1}{b1}<1$ ، پس : $n^{\log^{a1}_{b1}}<\: n^1$ و این یعنی $T(n)=\theta(f(n))=\theta(n)$

---

راه حل سوم:
(تستی)
در نظر می گیریم که k یک نیست ولی $b_i$ بینهایت هست یا $a_i$ صفر هست (یا هر دو همزمان)، که این با توجه به شرایط صورت مساله یعنی$\sum_{i=1}^k\frac{ai}{bi}<1$هم درست هست، حالا $a_iT(\frac{n}{b_i})$ برابر با صفر میشه و تنها چیزی که از $^{ }T(n)=\sum^k_{i=1}a_i.T(\frac{n}{b_1})+cn$ میمونه $^{ }T(n)=cn$ هست، در نتیجه $^{ }T(n)=O(n)$

ضمن سپاس از پاسخ کاربر Pure Liveliness :
=====
بنابر "بسیار مهم" بودن سوال هفتم و البته با توجه به این که در دوره های متوالی و در کتاب های متعددی این سوال و سوالات بسیار نزدیک با منطق این سوال مورد بررسی قرار گرفته پاسخ چهارمی با منطقِ آنچه که کاربر Pure Liveliness ارائه داد در این جا خدمت دوستان دنبال کننده میگذارم :
راه حل چهارم سوال هفتم

فرض میکنیم تمام $a_i$ ها برابر باشند داریم :
$T(n)=T(\frac{n}{a})+T(\frac{n}{a})+.\: .\: .+T(\frac{n}{a})+\theta(n)$ یعنی Kتا $T(\frac{n}{a})$ داشته باشیم که میشود :
$T(n)=kT(\frac{n}{a})+\theta(n)$ و این بیانی دیگر از سیگما هست. در صورتی که داشته باشیم :
$T(n)=\sum^k_{i=1}T(\frac{n}{a_i})+\theta(n)$ که کاملا منطبق هست با سوال ۱۸/۱ در ۶۰۰ مساله که پاسخ های کامل آن را میشود به صورت زیر ارائه داد.

با توجه به قضیه ی مستر حالات زیر برقرار است :

۱) $T(n)=\theta(n)\: \: if\: \: k<a$

۲)$T(n)=\theta(n.logn)\: \: if\: \: k=a$

۳)$T(n)=\theta(n^{\log_a^k})\: \: if\: \: k>a$

حال آنچه که این سوال را از سوال ۱۸/۱ متمایز میکند شرط مقابل است $1-\sum^k_{i=1}\frac{a_i}{b_i}>0$

همان گونه که مشاهده میشود علاوه بر ثابت $a_i$ ثابت $b_i$ نیز اضافه شده است. ما اگر مقدار ثابت $a_i$ را با مقادیر برابر ست کنیم، میشود مقادیر $b_i$ را متفاوت در نظر گرفت این تمایز باعث میشود شرط سوال متفاوت تر از سوالات پیشین به نظر برسد : (ضمن دقت در نکته ی زیر از پوران):

نکته : رابطه ی بازگشتی : $T(n)=T(\alpha n)+T(\beta n)+n$ که $\alpha\: ,\: \beta$ ثابت هستندمفروض است اگر $\alpha+\beta=1$ داریم $T(n)=\theta(n.\log n)$ و اگر $\alpha+\beta<1$ آنگاه $T(n)=\theta(n)$

حال با دقت در شرط سوال و پاسخ کتاب نارنجی پوران و مثال ارائه شده در این کتاب میتوان پی برد که شرط مذکور در سوال بیانگر همان مقدار :
$\alpha+\beta<1$ می باشد یعنی داریم : $\alpha+\beta<1\: \equiv\: \sum^k_{i=1}\frac{a_i}{b_i}<1$

حل مثال زیر با مقادیر $k=2$ و $a_1=a_2=1\:$ و $b_1=5$ و $b_2=\frac{10}{7}$ که رابطه ی بازگشتی زیر را میسازد $T(n)=T(\frac{n}{5})+T(\frac{7n}{10})+cn$ با درخت بازگشت اثباتی برای ادعای بالا است. که مرتبه ی سوال برابر است با :
$T(n)=O(n)$ و گزینه ی اول پاسخ صحیح است

سوال هشتم (*) {ادغام چندین سوال از ۶۰۰ سوال و کتاب نارنجی) سوال ۳۰/۱ و سوال ۴۱/۱ و سوال ۵ و ۷ از نارنجی

چه تعداد از عبارات زیر صحیح است ؟ {تشریح گزینه ها ضروریست}

۱)$n\: !\: =\omega(2^n)$

۲)$n\: !\: =o(n^n)$

۳)$\log(n\: !)\: =\theta(n\: \log n)$

۴)$n\: !=O(n^n)$

۵)$3^{2^n}=\Omega(2^{3^n})$

۶)$n^{2+\frac{1}{\sqrt{n}}}=O(n^2)$

۷)$\sum^n_{i=1}i^k\log i=O(n^{k+1}\log^{k+1}n)$

۸)$\sum^n_{i=1}\lceil\frac{1}{i}\rceil=O(n\: \log n)$

۱)۰
۲)۱
۳)۲
۴)۴

---

سوال نهم{سوال ۲۶ از کتاب نارنجی}

کدام عبارت صحیح است ؟
الف) $\log^{\ast}(\log n)\in\omega(\log(\log^{\ast}n))$

ب ) اگر $k.\ln k=\theta(n)$ آن گاه $k=\theta(\frac{n}{\ln n})$

پ ) $\sqrt{n}\in\Omega(n^{\sin n})$ یا $\sqrt{n}\in O(n^{\sin n})$

۱)الف
۲)الف و پ
۳) الف و ب
۴)هر سه مورد

---

با ۶ تا ۱۰ سوال دیگر بخش اول به پایان میرسد، سوالات شامل ترتیب های رشد پیچیدگی تکه برنامه ها و مسائل استخراجی با ایده ی بازگشتی خواهد بود

پاسخ سوال نهم (سوال ۱-۲۶ از کتاب نارنجی پوران)
در مورد گزینه ی الف:
یه فرمولی هست که $\log^{\ast}(\log n)=\log^{\ast}n\: -\: 1$
این فرمول از کجا اومده؟ $\log^{\ast}$ هر چیزی یعنی انقدر ازش لگاریتم بگیریم که به عددی کوچکتر از یک یا یک برسه، تعدادش میشه $\log^{\ast}n$ که معمولا برای اعداد خیلییی بزرگ هم بیشتر از ۶ نمیشه. حالا فرض کنیم که لگاریتم یه عدد رو داریم یعنی log n تا این جا یه مرحله رو انجام دادیم، حالا میایم از این log n، $\log^{\ast}$ش رو حساب میکنیم، یعنی یه دونه از مراحل $\log^{\ast}n$ کمتر، که میشه $\log^{\ast}n\: -1$. مثال می زنم.
n=16
$\log16=3$ یعنی باید یه بار لگاریتم بگیریم از ۱۶ که بشه ۴، بار دوم از ۴ لگاریتم بگیریم که بشه ۲ و بار سوم از ۲ لگاریتم بگیریم در مبنای ۲ که بشه ۱، سه بار لگاریتم گرفتیم تا برسیم به ۱، این سه تا میشه $\log^{\ast}۱۶$

$\log^{\ast}\log16=\log^{\ast}4=2$
حالا $\log^{\ast}16=3$
خب پس این فرمول قابل درک هست:$\log^{\ast}(\log n)=\log^{\ast}n\: -\: 1$
توی صورت سوال داریم که $\log^{\ast}(\log n)\: \in\omega(\log(\log^{\ast}n))$ حالا از اونجایی که $\log^{\ast}(\log n)=\log^{\ast}n\: -\: 1$ و این که می دونیم رشد $\log(\log^{\ast}n)$ از رشد $\log^{\ast}n$ کمتر هست پس این گزینه کاملا درسته.

گزینه ی دو:
فرض میکنیم تالی درست باشه، یعنی واقعا $k=\theta(\frac{n}{\ln n})$ خب پس به جای k توی عبارت $k.\ln k$، معادلش رو مینویسیم.
$k.\ln k=\frac{\: n}{\ln n}.\ln(\frac{n}{\ln n})$
می دونیم که $\ln(\frac{x}{y})=\ln x-\ln y$ پس عبارت بالا به صورت زیر میشه:
$\frac{n}{\ln n}.\ln(\frac{n}{\ln n})=\frac{n}{\ln n}.(\ln n\: -\: \ln\: \ln n)=\frac{n.\ln n}{\ln n}-\frac{\: n}{\ln n}.\ln\ln n=n-\frac{n}{\ln n}.\ln\ln n=n.(1-\frac{\ln\ln n}{\ln n})$
که می دونیم رشد $\frac{\ln\ln n}{\ln n}$ از ۱ کمتر هست پس عبارت بالا میشه:
$\theta(n)$ که خب درسته.
پس این گزینه هم درسته.

گزینه ی سوم:
کلا وقتی می تونیم مرتبه ی بزرگی دو تا تابع رو با هم مقایسه کنیم که هر کدوم یا صعودی یا نزولی باشه، یه سری از توابع هستند که تناوبی هستند و توی یه بازه هایی صعودی هستند و یه بازه هایی نزولی بعد ممکنه نشه با بعضی از توابع مقایسه بشن.
توی این مثال: خب $-1\: <\: \sin\: n\: <\: 1$
وقتی $-1\: <\: \sin\: n\: <\: 0$ اونوقت $n^{\sin n}$ معادل میشه با $n^k\: \: (-1<k<0)$ که یعنی توان n از یک کمتر هست، پس یعنی توی این بازه ی مشخص شده $\sqrt[]{n}=omega(n^{\sin n})$
اما وقتی$0\: <\: \sin\: n\: <\: 1$ اونوقت $n^{\sin n}$ معادل میشه با $n^k\: \: (0<k<1)$ که یعنی توان n از یک بیشتر هست، پس یعنی توی این بازه ی مشخص شده $\sqrt[]{n}=O(n^{\sin n})$
اگر شکل این دو تابع رو هم بکشیم متوجه میشیم توی یه بازه ای اولی بالای دومی هست و توی بازه ی بعدی بالعکس، پس نمیشه این دو تا رو مقایسه کرد و غلط هست سوال به کل.
پس گزینه ی سه درسته یعنی الف و ب درست هستند.

ضمن سپاس و در ادامه پاسخ کاربر Pure Liveliness :

۳)طبق قضیه ی استرلینگ داریم : $\log(n!)\equiv n\: \log n$ این هم ارزی در رشددرست بودن حالت سوم را نشان میدهد.

۴) تابع توضیحات عالی دوست عزیزمان این گزینه مانند حالت دوم قابل اثبات است

۵) باز هم به تبعیت از توضیحات کاربر Pure Liveliness :
میشود از طرفین رابطه لگاریتم گرفت : تا به حالت زیر برسیم :
$2^n\log3\le3^n\log2$ و نادرستی این گزینه نیز ثابت شود.

۶) میتوان گفت برای هر مقدار $\epsilon$ در توان افزایش قابل ملاحظه ای در پیچیدگی خواهیم داشت و در این مثال به ازای n0 که n>n0 باشد داریم : $n^{2+\frac{1}{\sqrt{n}}}\ge n^2$ که از مرتبه ی $\Omega$ خواهد بود.پس این گزینه نیز غلط است.

۷) در جستجوی پاسخ مناسب و ساده و کاربردی . . .(در حال تکمیل . . . )

پاسخ سوال هشتم (سوال ۱-۳۱ و ۱-۴۱ ۶۰۰ مساله ی دکتر قدسی و سوال ۵ و ۷ نارنجی پوران)
۱)$n!=\omega(2^n)$
راه حل اول:
درست هست چون $n!=n\times(n-1)\times(n-2)\times...\times3\times2\times1$ که ضرب n عدد از ۱ تا n در هم هست.
$2^n=\: 2\times2\times2\times....\times2$ که ضرب n عدد ۲ در هم هست و مشخص هست که از ضرب ۱ تا n کمتر هست.
راه حل دوم:
لگاریتم میگیریم. $\log_22^n=nlog_2^2=n$ و $\log_2n!=nlogn$ که خب مشخص هست که nlogn از n بزرگتر هست.

---

۲)$n!\: =\: O(n^n)$
درست هست چون طبق ۱ n! از ضرب ۱ تا n به دست میاد و $n^n$ از ضرب n تا n
با گرفتن log هم به همین نتیجه خواهیم رسید. گرچه همیشه این روش جواب نمیده. یعنی مثلا n با توان های مختلف رو اگه ازش log بگیریم، حاصل log هم مرتبه است ولی رشد به ازای توان های مختلف فرق داره.

---

۷)$\sum^n_{i=1}i^k.\log k\: \in O(n^{k+1}.\log^{k+1}n)$
$\sum_{i=1}^ni^k.\log i=1^k.\log1+2^k.\log2+3^k.\log3+....+n^k.\log n$
این سری تک تک جملاتش از $n^k.\log n$ کوچیکتر هست، از طرفی n تا جمله داریم از i=1 تا n
$\sum^n_{i=1}i^k.\log k\: =1^k.\log1+....+n^k.\log n\: \le n.n^k.\log n\le n^{k+1}.\log^{k+1}n$ که خب اثبات شد که $\sum^n_{i=1}i^k.\log k\: \in O(n^{k+1}.\log^{k+1}n)$

---

۸)$\sum^n_{i=1}floor(\frac{1}{i})=\theta(n)$
$\sum^n_{i=1}ceil(\frac{1}{i})=ceil(\frac{1}{1})+ceil(\frac{1}{2})+ceil(\frac{1}{​3})+…+ceil(\frac{1}{n})=1+1+1+...+1=n=\theta(n)$
چون علامت سقف رو پیدا نکردم نوشتم ceil
نکته: اگر علامت براکت نبود اوضاع فرق داشت، همیشه نمیشه از براکت توی مرتبه زمانی ها چشم پوشی کرد. می دونیم: $\sum^n_{i=1}\frac{1}{i}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\ln n=\theta(\log n)$

سوال دهم (۳۰ کتاب نارنجی و ۵۱/۱ از ۶۰۰ سوال)

زمان اجرای رویه ی زیر چقدر است(بهترین گزینه را انتخاب کنید) :

۱) $O(\log N)$

۲)$\theta(\log N)$

۳)$O(\sqrt{n})$

۴)$\theta(\sqrt{n})$

---

سوال یازدهم (۵۹/۱از ۶۰۰ سوال و ارشد ۹۱)
هزینه ی زمانی تکه برنامه ی روبه رو کدام است؟ (دقت شود که مقادیر i/2 و j/3 به صورت کفِ مقادیر میباشند)


۱)$O(\log^2n)$

۲)$O(\log n)$

۳)$O(n)$

۴) $O(n^2)$

---

سوال دوازدهم(*)(۶۳/۱ از ۶۰۰ سوال)
آرایه A به طول n داده شده است که تمام درایه های آن در ابتدا صفر هستند.عمل درج روبه رو را n بار با مقادیر دلخواه x انجام میدهیم هزینه ی سرشکن شده ی هر عمل درج کدام است؟بهترین گزینه را انتخاب کنید

پاسخ سوال سیزدهم
گزاره ی اول نادرست است ، چون الگوریتم مرتب سازی سریع یک مثال نقض مناسب برای آن است.
زمان اجرای این الگوریتم در بدترین حالت $O(n^2)$ و در حالت میانگین $O(nlogn)$ است.

نکته : در مرتب سازی سریع اگر لیست از قبل مرتب باشد یا به صورت معکوس مرتب باشد داریم : $\theta(n^2)$ چرا که در این دو حالت در هر فراخوانی از روال partition یک زیر لیست با $Q(n-1)$ و دیگری با $Q(0)$ (یک لیست تهی) فراخوانی میشود که در کل مرتبه ی زمانی برابر است با :
$Q(n)=Q(n-1)+Q(0)+n-1$ دقت کنید که n-1 از نتیجه ی مقایسه عنصور محوری با کل عناصر است. مرتبه ی این حالت در کل : $\theta(n^2)$ است.

مرتب سازی سریع در حالت میانگین و بهترین حالت از مرتبه ی $\theta(nlogn)$ است که در نتیجه ی حالتی است که عنصر میانه را در وسط لیست بگیریم که رابطه ی بازگشتی تقریبی زیر با مرتبه ی ذکر شده به دست آید.
$Q(n)\simeq Q(\frac{n}{2})+Q(\frac{n}{2})+n-1$

(در حال تکمیل . . .)