سلام .

برای تست اولی خود تابع رو بهت داده و خواسته T رو بدست بیاری (زمان الگوریتم تابع F رو به دست بیاورید یعنی اون n که با تابع F جمع شده خروجی محاسبات داخلی تابع بازگشتی است نه سربار زمانی) که میشه $O(n)$

برای دومی باید توجه داشت که همون طوری که صورت تست گفته شده تابع بازگشتی زمانی یا همون T رو بهت داده یعنی اون n که با تابع T جمع شده سربار زمانی به ازای هر بار اجرای تابع است و باید محاسبه کنی که میشه همون $O(n^{2})$

سلام .
این دو تا سوالی که در ادامه پرسیدی سوال های جالبی هستن که دوستان با تحلیلشون هم یه جور دست گرمی هستش و هم میتونن نتایج جالب و جدیدی رو کسب کنن.

سوال اول


که فک کنم من در آوردی بوده چون من ندیدم همچین T رو توی تست ها و تمرینها فقط یه جایی این سوال رو دیدم اونم توی مقاله ی خارجی بود که یه الگوریتم ابداعی روی Max-Heap داشت که T الگوریتم همین میشد ولی در کل جالبه و البته دارای ابهام .

اول به این مسئله زیر که امیر جان خودتم به درستی حلش کردی نگاهی بندازیم چون در ادامه به دردمون میخوره

طبق قضیه ای که توی کتاب CLRS بهش اشاره شده با استفاده از تقریب استرلینگ(کتاب الگوریتم محاسبات دانشگاه MIT این تقریب رو کامل توضیح داده) میتونیم بگیم که چون تفاوت لگاریتم ها اونقدری نیست که در تابع اثر بزاره و ما چون داریم به صورت حدی نیز کار میکنیم پس میتونیم در واقع فرض کنیم که همه ی لگاریتم ها همون logn هستند که میشه n تا logn که باعث میشه تساوی ${\color{Red} logn!=\theta (nlogn)}$ درست باشه.

حالا این دوستمون که گفتن جواب $2^{n}\log n$ تقریبا با اثباتی که در زیر میارم و با توجه به نکته ی بالا درست گفتن ولی در ادامه میبینیم که اینم شاید جواب درست نباشه

اثبات اول درخت بازگشت :
اگر بخوایم از طریق درخت بازگشت حل کنیم هزینه هر سطح درخت به صورت زیر محاسبه میشه :


خب حالا جمع کردن این هزینه ها یه کم کار سختیه چون لگاریتم ها با هم متفاوت هستن . ولی اگر از همون قضیه تقریب استرلینگ استفاده کنیم میتونیم فرض کنیم که مسئله به صورت زیر جمع میشه :


همون طوری که میبینیم اینجا نیز فرض کردیم که همه ی لگاریتم ها برابر هستند که باعث میشه فرض کنیم $2^{n}$ تا $logn$ داریم که جواب میشه $\theta (2^{n}\log n)$

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

خب در اینجا ما حد پایین و بالای مسئله رو اثبات کردیم که از مرتبه ی $\theta (2^{n})$ پس در نتیجه مسئله ما هم باید از همین مرتبه باشه

سوال دوم

واسه این معادله مشخصه کاربرد نداره چون با تغییر متغیر $n=2^{m}$ داریم
حالا معادله قسمت همگن این عبارت به صورت زیر هستش
اگر کسی بتونه ریشه های این معادله رو به دست بیاره اولا بهش تبریک میگم دوما قطعا به راحتی به جواب این مسئله میرسه

خب میریم سراغ روش دوم یعنی درخت بازگشت و هزینه سطوح درخت به صورت زیر است

${\color{Red} (n \frac{n7}{8} \frac{n63}{64} ...)}$

اینجا کار یه کم سخته ولی باز یه قاعده هستش که ما رو کمک میکنه این قاعده رو در CLRS بهش اشاره شده و فک کنم آقای یوسفی هم بهش اشاره کرده :
$(\frac{1}{2} \frac{1}{4} \frac{1}{8} \frac{1}{16} ...) = c$

این قضیه داره میگه که جمع این سری همیشه یه عدد ثابت میشه و این باعث میشه که سری زیر به این صورت حل بشه

$n \frac{n}{2} \frac{n}{4} \frac{n}{8} ...= n(1 \frac{1}{2} \frac{1}{4} \frac{1}{8} \frac{1}{16} ...) = nc=\theta (n)$

حواسمون باشه که این با سری $n(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} \frac{1}{5} ...) = \theta (nlogn)$ تفاوت داره چون سری اعداد اینجا خیلی بزرگتر هستش

و در ادامه اگر به سری اعداد خودمون توجه کنیم میبینیم که از سری اعداد $\frac{1}{2} \frac{1}{4} \frac{1}{16} \frac{1}{32} ...$ خیلی کوچیکتره و