با عرض سلام.
یه رابطه بازگشتی داریم بصورت :(tn=t(n-1) + t(n-2) + O(1
این رابطه بازگشتی به این شکل حل شده:
(T(N) ≤ ۲ T(N-1) ==> T(N) ∈O(2N
چرا رابطه داده شده به این صورت حل شده؟در واقع در چه مسائلی میشه از این روش استفاده کرد؟و منظور از (T(N) ≤ ۲ T(N-1 چیه؟آیا میخواد بگه که این دو
[ (tn=t(n-1) + t(n-2) + O(1 و (T(N) ≤ ۲ T(N-1 ] تقریبا مثل هم هستند؟
این رابطه‌ی بازگشتی حل نشده، با این روش فقط مرتبه ش پیدا شده!
اون رابطه ای که نوشتید، میتونه رابطه‌ی بازگشتی زمان الگوریتم فیبوناچی بازگشتی باشه، و اگه خاطرتون باشه اگه اون رابطه‌ی بازگشتی رو با روال معمول برای حل معادلات حلش کنیم، ریشه هایی که برای معادله مشخصه به دست میاد روند نیست، و توش رادیکال داره و اینا! واسه همین اینجا که نیاز نداشته برای محاسبه‌ی مرتبه‌ی رابطه حل دقیقش رو داشته باشه، اومده از یه روش راحت‌تر استفاده کرده.
اومده حد بالا و پایینی برای رابطه پیدا کرده، رابطه‌ی بازگشتی رو برای اون حدها که خیلی ساده‌تر از رابطه‌ی اصلی هستند حل کرده. (به نظرم این روش برای تست خوبه)
پیشنهاد میکنم یه بار معادله مشخصه‌ی رابطه‌ی مورد سوالتون رو به دست بیارید حلش کنید و مقایسه کنید. (البته اگه نکردید این کارو!)
ببینید این یه جواب تخمینی هست و از نظر مجانبی درسته یعنی در واقع O اون رو حساب کردیم . فصل اول ساختمان داده پارسه قضیه اصلی رو با عملگر های کوچکتر و بزرگتر رو بررسی کرده میتونید یه نگاه بهش بندازین(کتاب رو اگه گیر بیاری کار ۱ دقیقه هست)
(۲۳ دى ۱۳۸۹ ۰۲:۲۹ ق.ظ)sos006 نوشته شده توسط: با عرض سلام.
یه رابطه بازگشتی داریم بصورت :(tn=t(n-1) + t(n-2) + O(1
این رابطه بازگشتی به این شکل حل شده:
(T(N) ≤ ۲ T(N-1) ==> T(N) ∈O(2N
چرا رابطه داده شده به این صورت حل شده؟در واقع در چه مسائلی میشه از این روش استفاده کرد؟و منظور از (T(N) ≤ ۲ T(N-1 چیه؟آیا میخواد بگه که این دو
[ (tn=t(n-1) + t(n-2) + O(1 و (T(N) ≤ ۲ T(N-1 ] تقریبا مثل هم هستند؟
دلیل اینکه (tn=t(n-1) + t(n-2) + O(1
به صورت T(N) ≤ ۲ T(N-1) در اومده اینه که دو تا عبارت t(n-1) و t(n-2) تقریبا اعداد نزدیک به همی رو تولید می کنند پس برای سادگی حل مساله می تونیم بگیم: t(n-1)=t(n-2) و در نتیجه صورت مساله برابر می شه با: (T(N) ≤ ۲ T(N-1 . حلش هم که از طریق جایگذاریه.