۰
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