۰
subtitle
ارسال: #۱
جواب یک رابطه بازگشتی مرتبه ۲؟
با عرض سلام.
یه رابطه بازگشتی داریم بصورت :(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) ∈O(2N
چرا رابطه داده شده به این صورت حل شده؟در واقع در چه مسائلی میشه از این روش استفاده کرد؟و منظور از (T(N) ≤ ۲ T(N-1 چیه؟آیا میخواد بگه که این دو
[ (tn=t(n-1) + t(n-2) + O(1 و (T(N) ≤ ۲ T(N-1 ] تقریبا مثل هم هستند؟
۰
ارسال: #۲
RE: جواب یک رابطه بازگشتی مرتبه ۲؟
این رابطه‌ی بازگشتی حل نشده، با این روش فقط مرتبه ش پیدا شده!
اون رابطه ای که نوشتید، میتونه رابطه‌ی بازگشتی زمان الگوریتم فیبوناچی بازگشتی باشه، و اگه خاطرتون باشه اگه اون رابطه‌ی بازگشتی رو با روال معمول برای حل معادلات حلش کنیم، ریشه هایی که برای معادله مشخصه به دست میاد روند نیست، و توش رادیکال داره و اینا! واسه همین اینجا که نیاز نداشته برای محاسبه‌ی مرتبه‌ی رابطه حل دقیقش رو داشته باشه، اومده از یه روش راحت‌تر استفاده کرده.
اومده حد بالا و پایینی برای رابطه پیدا کرده، رابطه‌ی بازگشتی رو برای اون حدها که خیلی ساده‌تر از رابطه‌ی اصلی هستند حل کرده. (به نظرم این روش برای تست خوبه)
پیشنهاد میکنم یه بار معادله مشخصه‌ی رابطه‌ی مورد سوالتون رو به دست بیارید حلش کنید و مقایسه کنید. (البته اگه نکردید این کارو!)
اون رابطه ای که نوشتید، میتونه رابطه‌ی بازگشتی زمان الگوریتم فیبوناچی بازگشتی باشه، و اگه خاطرتون باشه اگه اون رابطه‌ی بازگشتی رو با روال معمول برای حل معادلات حلش کنیم، ریشه هایی که برای معادله مشخصه به دست میاد روند نیست، و توش رادیکال داره و اینا! واسه همین اینجا که نیاز نداشته برای محاسبه‌ی مرتبه‌ی رابطه حل دقیقش رو داشته باشه، اومده از یه روش راحت‌تر استفاده کرده.
اومده حد بالا و پایینی برای رابطه پیدا کرده، رابطه‌ی بازگشتی رو برای اون حدها که خیلی ساده‌تر از رابطه‌ی اصلی هستند حل کرده. (به نظرم این روش برای تست خوبه)
پیشنهاد میکنم یه بار معادله مشخصه‌ی رابطه‌ی مورد سوالتون رو به دست بیارید حلش کنید و مقایسه کنید. (البته اگه نکردید این کارو!)
۰
ارسال: #۳
RE: جواب یک رابطه بازگشتی مرتبه ۲؟
ببینید این یه جواب تخمینی هست و از نظر مجانبی درسته یعنی در واقع O اون رو حساب کردیم . فصل اول ساختمان داده پارسه قضیه اصلی رو با عملگر های کوچکتر و بزرگتر رو بررسی کرده میتونید یه نگاه بهش بندازین(کتاب رو اگه گیر بیاری کار ۱ دقیقه هست)
۰
ارسال: #۴
RE: جواب یک رابطه بازگشتی مرتبه ۲؟
(۲۳ دى ۱۳۸۹ ۰۲:۲۹ ق.ظ)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 . حلش هم که از طریق جایگذاریه.
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
 |
سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ | Azadam | ۶ | ۳,۹۹۷ |
۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ آخرین ارسال: Soldier's life |
| نظر در رابطه با استاد داور | علیصا | ۰ | ۱,۴۸۱ |
۱۴ مهر ۱۴۰۰ ۰۶:۰۵ ب.ظ آخرین ارسال: علیصا |
|
| مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۰۸۲ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
| مرتبه شبه کد | rad.bahar | ۱ | ۲,۰۸۶ |
۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ آخرین ارسال: BBumir |
|
| تعداد جواب | mostafaheydar1370 | ۲۱ | ۱۷,۳۰۰ |
۰۱ مهر ۱۳۹۹ ۱۱:۴۱ ب.ظ آخرین ارسال: miinaa |
|
| حل مساله مرتبه زمانی حلقه های تو در تو | sarashahi | ۱۶ | ۲۱,۳۷۴ |
۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ آخرین ارسال: gillda |
|
| مرتبه زمانی | Sanazzz | ۱۷ | ۱۹,۴۴۱ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ آخرین ارسال: mohsentafresh |
|
| جواب سوالهای تخصصی دکتری هوش مصنوعی سال ۹۸ | Lootus | ۱ | ۲,۵۶۰ |
۲۹ بهمن ۱۳۹۸ ۰۱:۴۳ ب.ظ آخرین ارسال: machine86 |
|
| مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۳,۴۶۷ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |
|
| مرتبه مانی | Sanazzz | ۳ | ۳,۳۴۶ |
۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ آخرین ارسال: Sanazzz |
|
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close