سلام
پیچدگی زمانی این رابطه بازگشتی از مرتبه ای (n^2)θ؟لطفا راهنمایی کنید.
ممنون
شرط توقف
T(1)=1
سلام.
بهتر بود فرمولش رو با TEX پایین بنویسید یا عکس بذارید.
توی این طور سوالا که تابع رو به صورت یک سری نوشته واسه خلاص شدن از سری معمولا میان مثلا [tex]T(n-1)[/tex] رو حساب میکنن و تفاضل [tex]T(n-1)[/tex] و [tex]T(n)[/tex] باعث میشه خیلی از جملات بره و عبارت ساده تری بر حسب این دو تا و یه سری جملات دیگه به دست بیاد. گاهی هم باید توی ضریبی ضرب بشه این عبارت ها.
یه مثال مشابه این سوال
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
.
[tex]T(n)=n+\sum_{k=1}^{n-1}T(n-k)+T(k)[/tex]
[tex]T(n)=n+\sum_{k=1}^{n-1}T(n-k)+T(k)=T(n-1)+T(1)+T(n-2)+T(2)+T(n-3)+T(3)...+T(n-(n-1))+T(n-1)=2T(n-1)+2T(n-2)+...+2T(2)+2T(1)+n[/tex]
حالا [tex]T(n-1)[/tex] رو مینویسیم:
[tex]T(n-۱)=n-۱+\sum_{k=1}^{n-2}T(n-1-k)+T(k)=T(n-2)+T(1)+T(n-3)+T(2)+T(n-4)+T(3)...+T(n-1-(n-2))+T(n-2)=2T(n-2)+2T(n-3)+...+2T(2)+2T(1)+n-1[/tex]
حالا میایم این دو تا رو از هم کم میکنیم:
[tex]T(n)-T(n-1)=\sum^{n-1}_{k=1}T(n-k)+T(k)+n-\sum^{n-2}_{k=1}T(n-1-k)+T(k)-(n-1)=2T(n-1)+2T(n-2)+...+2T(1)-2T(n-2)-...-2T(1)+n-(n-1)=2T(n-1)+1[/tex]
یعنی داریم:
[tex]T(n)-T(n-1)=2T(n-1)+1[/tex]
پس:
[tex]T(n)=3T(n-1)+1[/tex]
این رابطه یه معادله ی خطی ناهمگن هست:
[tex](x-3)(x-1)=0[/tex] معادله ی مشخصه ش هست.
[tex]x_1=3,\: x_2=1[/tex] ریشه هاش هستن. پس [tex]T(n)=\(c_13^n+c_21^n)[/tex]
این تابع از مرتبه ی [tex]T(n)=\theta(3^n)[/tex]هست. با توجه به این که پس : [tex]T(1)=c_13^1+c_21^1=3c_1+c_2=1[/tex] اما دو تا ثابت داره پس حداقل باید دو تا شرط اولیه داشته باشه.
سلام. وقت بخیر.
اگه سیگما روی هردو جمله باشه (که به نظر میاد اینطوریه) میتونید اختلاف دو جمله متوالی رو پیدا کنید:
[tex]T(n)=n+\sum_{k=1}^{n-1}(T(n-k)+T(k))=n+2\sum_{k=1}^{n-1}T(k)[/tex]
[tex]T(n-1)=n-1+2\sum_{k=1}^{n-2}T(k)[/tex]
[tex]T(n)-T(n-1)=1+2T(n-1)[/tex]
[tex]T(n)=1+3T(n-1)[/tex]
به نظر میرسه جواب از مرتبه [tex]\theta(3^n)[/tex] باشه.
سلام.
Θ(۳^n) توی گزینه ها هست .ولی جواب سوال رو Θ(۲^n) اعلام کردن؟!!!
که خیلی هم از وقت من رو گرفت تا آخرش سوال رو اینجا مطرح کردم.
با تشکر از هر دو مدیر محترم
(۲۳ آبان ۱۳۹۵ ۰۸:۵۳ ب.ظ)Alirezaj نوشته شده توسط:
سلام.
Θ(۳^n) توی گزینه ها هست .ولی جواب سوال رو Θ(۲^n) اعلام کردن؟!!!
که خیلی هم از وقت من گرفت تا آخرش سوال رو اینجا مطرح کردم.
با تشکر از هر دو مدیر محترم
سلامت باشید. اشتباهش تو بیشترین مقدار سیگما بوده. تست مربوط به کجا بود؟
(۲۳ آبان ۱۳۹۵ ۱۰:۴۴ ب.ظ)Jooybari نوشته شده توسط:(23 آبان ۱۳۹۵ ۰۸:۵۳ ب.ظ)Alirezaj نوشته شده توسط:
سلام.
Θ(۳^n) توی گزینه ها هست .ولی جواب سوال رو Θ(۲^n) اعلام کردن؟!!!
که خیلی هم از وقت من رو گرفت تا آخرش سوال رو اینجا مطرح کردم.
با تشکر از هر دو مدیر محترم
سلامت باشید. تست مربوط به کجا بود؟
آزمون آزمایشی جمعه گذشته
وقت بخیر
ببخشید معادله ی مشخصه رو ممکن بگید چرا تبدیل به این فرم شد؟)(x-1)(x^2-3x)
(۲۵ آبان ۱۳۹۵ ۱۲:۱۶ ب.ظ)Alirezaj نوشته شده توسط: وقت بخیروقتتون بخیر. ببخشید من اشتباهی دیدم. معادله ی مشخصه میشه [tex](x-3)(x-1)^1=0[/tex]
ببخشید معادله ی مشخصه رو ممکن بگید چرا تبدیل به این فرم شد؟)(x-1)(x^2-3x)
الان توی جواب قبلی هم اصلاح میکنم.
بابت حل تشریحی سوال بصورت کامل وهمچنین توضیحاتتون .ممنون وسپاسگزارم.