سلام همون طور که میدونید ما توی مرتب سازیه ادغامی رابطه که به شکل زیر در نظر میگیریم:
[tex]T(n)=2T(\frac{n}{2}) \theta(n)[/tex]
البته اصل رابطه اینه :[tex]T(n)=T(\lfloor\frac{n}{2}\rfloor) T(\lceil\frac{n}{2}\rceil) \theta(n)[/tex]
ولی خب ما [tex]n[/tex] رو توانی از ۲ در نظر میگیریم هرچند اگه رابطه رو همون [tex]T(n)=T(\lfloor\frac{n}{2}\rfloor) T(\lceil\frac{n}{2}\rceil) \theta(n)[/tex] در نظر بگیریم توی رسم درخت فرقی نداره چون ما سقف و کف رو در نظر نمیگیریم
خب حالا رسم درخت.همون طور که میدونی برای رسم درخت [tex]f(n)[/tex] رو ریشه میذاریم که اینجا همون [tex]n[/tex] میشه و درسطح های بعدی به جای [tex]n[/tex] مقادیر بازگشتی رو قرار میدیم
سطح ۰[tex]\leftarrow[/tex][tex]n[/tex]
سطح ۱[tex]\leftarrow[/tex][tex]\frac{n}{2},\frac{n}{2}[/tex]
سطح ۲[tex]\leftarrow[/tex][tex]\frac{n}{4},\frac{n}{4},\frac{n}{4},\frac{n}{4}[/tex]
سطح ۳[tex]\leftarrow[/tex][tex]8[/tex] تا [tex]\frac{n}{8}[/tex] داریم
و ......
خب حالا باید مقادیر سطح ها رو با هم جمع بزنیم که میبینی جمع هر سطری [tex]n[/tex] میشه و چون ارتفاع درخت هم [tex]Logn[/tex] هستش پس زمان اجرا [tex]nLogn[/tex] میشه
[tex]----------------------------------------------[/tex]
سوال دوم
گفتیم رابطمون این میشه:[tex]T(n)=2T(\frac{n}{2}) \theta(n)[/tex] خب ببین اون زمان [tex]n[/tex] به خاطر الگوریتم [tex]Merge[/tex] هستش و حداکثر تعداد مقایسه توی الگوریتم [tex]Merge[/tex] برای دو لیست [tex]n[/tex] و [tex]m[/tex] عنصری میشه :[tex]n m-1[/tex] و اگه به رابطمون دقت کنی ما داریم ارایه رو به دو زیر مساله با اندازه [tex]\frac{n}{2}[/tex] تقسیم می کنیم پس الان ما میخوایم حداکثر مقایسه رو توی دو زیر ارایه به اندازه [tex]\frac{n}{2}[/tex] به دست بیاریم که طبق اون چیزی که بالا گفتیم میشه:[tex]\frac{n}{2} \frac{n}{2}-1=n-1[/tex]
پس زمان الگوریتم مرتب سازی ادغامی در بدترین حالت(بیشترین تعداد مقایسه) میشه:[tex]T(n)=2T(\frac{n}{2}) n-1[/tex]
که اگه درخت بازگشتشو بکشی میبینی میشه:
سطح ۰ [tex]\leftarrow[/tex][tex]n-1[/tex]
سطح ۱ [tex]\leftarrow[/tex][tex]\frac{(n-1)}{2},\frac{(n-1)}{2}[/tex]
سطح ۳[tex]\leftarrow[/tex][tex]\frac{(n-1)}{4},\frac{(n-1)}{4},\frac{(n-1)}{4},\frac{(n-1)}{4}[/tex]
و....
که جمع سطوح دارای این رابطست:[tex]\sum^{k-1}_{i=0}(n-2^i)[/tex]
و مقذار سیگما هم میشه:
[tex]\sum^{k-1}_{i=0}(n-2^i)=\sum^{k-1}_{i=0}(n)-\sum^{k-1}_{i=0}(2^i)[/tex]
[tex]\sum^{k-1}_{i=0}(n)=(n)\sum^{k-1}_{i=0}(1)=nk[/tex][tex]\sum^{k-1}_{i=0}(2^i)=2^0 2^1 2^2 2^3 2^{k-1}=2^0\ast\frac{1-2^k}{1-2}=2^k-1[/tex]
و حالا داریم:[tex]nk-(n-1)=nk-n-2^k 1[/tex]
حالا مونده مقدار [tex]k[/tex] کنیم ببین ما از ریشه درخت تا رسیدن به حالت پایه [tex]k[/tex] تا سطح داریم برای همین کران بالای سیگما [tex]k-1[/tex] شد چون کران پایین رو از صفر شروع کردیم پس تا [tex]k-1[/tex] ادامه میدیم که [tex]k[/tex] سطح میشه و برای محاسبه هم داریم:[tex]n-2^k=0[/tex]
۲نکته:اول اینکه [tex]k[/tex] الان سطح رو نشون میده یعنی توی سطح [tex]k[/tex]ام چند مقایسه داریم و و دوم هم اینکه حالت پایه اینه که تعداد مقایسه ها صفر بشه برای همین صفر نوشتیم.یعنی اینقد ادامه میدیم که دیگه احتیاجی به مقایسه نداشته باشیم
خب حالا رابطمونو حل میکنیم:
[tex]n-2^k=0\rightarrow2^k=n\rightarrow k=Log(n)[/tex]
خب الان توی مقداری که به دست اوردیم به جای [tex]k[/tex] از [tex]Logn[/tex] استفاده میکنیم:
[tex]nk-2^k 1=nLogn-2^{\log n} 1=nLogn-n 1[/tex]
خب اینم از این
فک کنم دارم رکورد تایپ مانشتو میزنم
[tex]----------------------------------[/tex]
سوال سوم
خب میتونی از اندیس های عناصر ارایه به عنوان یه کمک استفاده کنی.مثلا داری مقایسه انجام میدی و میخوای ارایه رو صعودی مرتب کنی حالا مقایسه میکنی عنصری که کوچکتر بود رو خب قاعدتا زودتر مینویسیم و اونایی هم که برابرن رو میایم اندیساشون رو بررسی میکنیم و اونی که اندیس کوچکتری داره رو زودتر مینویسیم و اینطوری پایداری الگوریتم رو به وجود میاریم
پایداری الگوریتم:ترتیب عناصر با کلید یکسان را حفظ کند
مثلا عناصر ورودی:[tex]2,1,3,1^{\alpha}[/tex]
بعد از مرتب سازی:[tex]1,1^{\alpha},2,3[/tex]
تموم اخخخخخیش
امیدوارم خیلی بد نگفته باشم.ببخشید دیگه