اگر T رو بگیریم تعداد ستاره های چاپ شده:
[tex]T(n) = 2 T(n/2) 1[/tex]
چون هر بار یک ستاره چاپ میکنه و دو بار n/2 رُ صدا میزنه
حالا اگر n رُ بگیریم ۲^m تابع جدید میشه:
[tex]F(m) = 2 F(m-1) 1[/tex]
که ریشه معادله مشخصه میشه ۲ و:
[tex]F(m) = a2^{m} b[/tex]
و: چون تغییر متغیر دادیم:
[tex]n= 2^{m} \rightarrow m=log (n)[/tex]
با جاگذاری:
[tex]T(n)= a'2^{logn} b'[/tex]
که با احتساب شرایط اولیه فرمول کلی گزینه آخر میشه[/align]

منم همون هایی تو گذاشتی رو بدست می آرم

(۱۷ بهمن ۱۳۹۱ ۱۱:۱۴ ق.ظ)pkpooria نوشته شده توسط:  اگر T رو بگیریم تعداد ستاره های چاپ شده:
[tex]T(n) = 2 T(n/2) 1[/tex]
چون هر بار یک ستاره چاپ میکنه و دو بار n/2 رُ صدا میزنه
حالا اگر n رُ بگیریم ۲^m تابع جدید میشه:
[tex]F(m) = 2 T(m-1) 1[/tex]
که ریشه معادله مشخصه میشه ۲ و:
[tex]F(m) = a2^{m} b[/tex]
و: چون تغییر متغیر دادیم:
[tex]n= 2^{m} \rightarrow m=log (n)[/tex]
با جاگذاری:
[tex]T(n)= a'2^{logn} b'[/tex]
که با احتساب شرایط اولیه فرمول کلی گزینه آخر میشه

مرسی دوست عزیز اما این رابطه اولی که بدست اوردید که من بدست میارم مرتبه n میشه!هرچند سوال تعداد رو خواسته
اما من همه سوالا رو با این روش تونستم حل کنم اما اینو نمیشه!
من بازم فکر می کنم که یه else کم داره!!!
بهرحال ما با هر روشی مرتبه رو بدست بیاریم این مرتبه ها باید با عدد گذاری تایید بشه نه اینکه رد بشه!موافق نیستید بامن؟!

دقت کنید:
ما تو این سوال دنبال مرتبه نیستیم بلکه دنبال جواب رابطه بازگشتی هستیم، که اونم با بدست آوردن معادله مشخصه و اعمال شرایط اولیه به دست میاد.
اگه else بذاره و توی اون چاپ کنه، فقط وقتی مقدار ورودی کمتر از صفر باشه ستاره چاپ میشه اونوقت برای بدست آوردنش باید درخت بکشید و به راحتی تعداد برگ ها رُ بررسی کنید
اما این الگوریتم تو هر فراخانی یک بار ستاره چاپ میکنه و دو بارم تابع رُ به ازای n/2 صدا میزنه یعنی:
[tex]T(n)=2T(n/2) 1[/tex]
حالا یه رابطه بازگشتی داریم که باید جواب کُلیشُ به دست بیاریم، که به دست آوردنش همونطور که بالا گفتم با تغییر متغییر و معادله مشخصه...

(۱۷ بهمن ۱۳۹۱ ۰۲:۴۷ ب.ظ)۸Operation نوشته شده توسط:  

(17 بهمن ۱۳۹۱ ۱۱:۱۴ ق.ظ)pkpooria نوشته شده توسط:  اگر T رو بگیریم تعداد ستاره های چاپ شده:
[tex]T(n) = 2 T(n/2) 1[/tex]
چون هر بار یک ستاره چاپ میکنه و دو بار n/2 رُ صدا میزنه
حالا اگر n رُ بگیریم ۲^m تابع جدید میشه:
[tex]F(m) = 2 T(m-1) 1[/tex]
که ریشه معادله مشخصه میشه ۲ و:
[tex]F(m) = a2^{m} b[/tex]
و: چون تغییر متغیر دادیم:
[tex]n= 2^{m}
ightarrow m=log (n)[/tex]
با جاگذاری:
[tex]T(n)= a'2^{logn} b'[/tex]
که با احتساب شرایط اولیه فرمول کلی گزینه آخر میشه

مرسی دوست عزیز اما این رابطه اولی که بدست اوردید که من بدست میارم مرتبه n میشه!هرچند سوال تعداد رو خواسته
اما من همه سوالا رو با این روش تونستم حل کنم اما اینو نمیشه!
من بازم فکر می کنم که یه else کم داره!!!
بهرحال ما با هر روشی مرتبه رو بدست بیاریم این مرتبه ها باید با عدد گذاری تایید بشه نه اینکه رد بشه!موافق نیستید بامن؟!

شما اشتباه حساب کردین. جواب میشه ۴n-1 که نزدیکترین جواب همون گزینه چهار هست درستش اینه
[tex]2^{log(n)) 2}-1=4n-1[/tex]
که با مثالهای شما درسته اما ای کاش عددای بزرگتر هم تست می کردین تا همه چی دستتون میومد

n=2,7
n=4,15
n=8, 31
n=16,63

---

یه نکته دیگه زمانی جواب دو به توان n هست که ارتفاع درخت n باشه اما در اینجا میبینیم که ارتفاع متناسب با log هست. پس میشه دو به توان log
همچنین اگه آخر برنامه else داشت جواب میشد ۲n که باز هم از مرتبه n هست