صورت سوال:
پیچیدگی زمانی؟؟
G0=1,G1=2,G2=4,Gn=Gn-1+2Gn-2+Gn-3
جواب:
[tex]G0<G1<G2<...<Gn[/tex] ***
[tex]Gn=Gn-1 2Gn-2 Gn-3<=Gn-1 2Gn-1 Gn-1=4Gn-1[/tex]
و [tex]Gn-1<=4Gn-2[/tex]
در نتیجه [tex]Gn<=4^{2}Gn-2[/tex]
خلاصه میشه :[tex]Gn<=4^{n}[/tex]
حالا سوالم اینه که خط ستاره رو از کجا کشف کرد ؟؟؟؟ تو صورت که چیزی نگفته ، شاید بعد G2، بعدیش کوچکتر باشه
اینو ممنون میشم بگین
این اومده از تقریب استفاده کرده. اولش اومده گفته که چون مشخصه دنباله ما صعودیه یعنی جملات بعدی از جملات قبلی بزرگترند. (همونی که تو ستاره اومده) بعد اومده گفته جمله [tex]G(n)=G(n-1) 2G(n-2) G(n-3)[/tex] کوچکتر از اون جمله ای که به جای G(n-2) , G(n-3) با G(n-1) جایگذاری شده بعد اومده حلش کرده شده [tex]4^{n}[/tex]
این جواب دقیقی نیست اما گاهی اوقات می تونه به ما کمک کنه. برای محاسبه جواب دقیق باید از حل معادلات همگن استفاده کنین. همون مبحثی که تو کتابای گسسته و معادلات هستش. یعنی
این معادله میشه:
[tex]r^{3}-r^{2}-2r-1=0[/tex]
بعد با محاسبه ریشه هاش می تونیم جواب نهایی رو محاسبه کنیم که اونم نمایی میشه و مطمئنا مقدارش کمتر از [tex]4^{n}[/tex] هست