۰
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