زمان کنونی: ۰۳ بهمن ۱۴۰۳, ۰۳:۱۶ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سوال از روابط بازگشتی

ارسال:
  

livane_abi پرسیده:

Question سوال از روابط بازگشتی

سلام
جواب این رابطه بازگشتی چی میشه؟
!T(N)=T(N/2)+LGN

۲
ارسال:
  

- rasool - پاسخ داده:

سوال از روابط بازگشتی

با تشکر از آقای mfXpert

همچنین

پاسخ رابطه‌ی‌: T(n)=T(n2)nlogn

به سادگی از راه قضیه اصلی حل می شه و جواب θ(nlogn)
خواهد بود.

۱
ارسال:
  

mfXpert پاسخ داده:

RE: سوال از روابط بازگشتی

چون عبارت lg(n!) با nlgn هم مرتبه هستش میتونید تو رابطه بازگشتی به جای lg(n!) عبارت nlgn رو قرار بدید و بعد با یه تغییر متغیر ساده میتونید جواب رو به دست بیارید

۰
ارسال:
  

mfXpert پاسخ داده:

RE: سوال از روابط بازگشتی

اول تغییر متغیر زیر رو در نظر می گیریم:
n=2kk=lgn
حالا شکل معادله رو بعد از اعمال تغییر متغیر می نویسیم:
T(2k)=T(2k1)2kk
حالا با در نظر گرفتن S(k)=T(2k) داریم:
S(k)=S(k1)2kk
معادله بالا یک معادله بازگشتی نا همگن با ضرایب ثابت هستش که معادله مشخصه اون به صورت زیر هستش:
(k2)2=0
معادله بالا ریشه مضاعف داره و اگر ریشه‌ها رو در جواب عمومی معادلات بازگشتی قرار بدیم داریم:
S(k)=C12kC2k2k
حالا با تغییر متغیر معکوس داریم:
T(n)=C1nC2nlgn
پس T از مرتبه تتای nlgn هستش


پ.ن‌: جواب رو با توجه به اون چیزهایی که از این بحث یادم می اومد نوشتم و ممکنه صد در صد درست نباشه

۰
ارسال:
  

yarandish پاسخ داده:

RE: سوال از روابط بازگشتی

با نظر ahmadi_development کاملا موافقم

طبق قضیه اصلی (T(n)=T(n)=aT(nb)cf(n)
جواب می شود n log n‌، اینکه livane_abi میگین جواب هست n log^2 n ،طبق قضیه اصلی جواب در صورتی این می شود که سوال ضریب ۲ داشته باشد (!T(N)=2T(N/2)+LGN )‌، پس یا اشتباه دیده (با احترام )و یا کتاب اشتباه زده !

ارسال:
  

- rasool - پاسخ داده:

RE: سوال از روابط بازگشتی

(۱۸ مهر ۱۳۹۰ ۰۶:۱۷ ب.ظ)yarandish نوشته شده توسط:  ،طبق قضیه اصلی جواب در صورتی این می شود که سوال ضریب ۲ داشته باشد (!T(N)=2T(N/2)+LGN )‌،
دوست عزیز‌، توجه کنید که اگه ضریب ۲ داشت ،یعنی رابطه‌ی ما T(n)=2T(n2)nlogn
بود اونوقت با قضیه اصلی حل نمی شد. بلکه باید با راههای دیگه حل می کردیم که همانطوری که فرمودید می شه θ(nlog2n)

تاپیک مرتبط:


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

- rasool - پاسخ داده:

سوال از روابط بازگشتی

جمع بندی:

در این تاپیک در مورد دو رابطه بحث شد:

اولین رابطه‌:

T(n)=T(n2)nlogn

** با قضیه اصلی حل می شود .
** پاسخی رو هم آقای mfXpert در پست چهارم داده اند (از راه تغییر متغیر)
**پاسخ آن O(nlogn) می شود.

---------------------------------------------------------------------------------
دومین رابطه‌:

T(n)=2T(n2)nlogn

** با قضیه اصلی حل نمی شود. (ولی می توان با تبصره و تعمیمی که در این مورد وجود دارد آن را حل کرد)
** می توان از راه درختی آن را حل کرد.
** پاسخ آن O(nlog2n) می شود.

۰
ارسال:
  

Masoud05 پاسخ داده:

RE: سوال از روابط بازگشتی

(۱۸ مهر ۱۳۹۰ ۰۲:۲۸ ب.ظ)livane_abi نوشته شده توسط:  سلام
جواب این رابطه بازگشتی چی میشه؟
!T(N)=T(N/2)+LGN

فکر کنم اینجوری میشه:




دوستان برای تشکر هم از دکمه تشکر و یا تایید ارسال استفاده کنن( بجای گزاشتن یک ارسال ). با اجازتون ارسال های حاشیه ای رو حذف میکنم تا دوستانی که بعدا از این موضوع استفاده میکنن‌، مستقیم به اصل موضوع رجوع کنند.

۰
ارسال:
  

ahmadnouri پاسخ داده:

RE: سوال از روابط بازگشتی

با استفاده از تبصره ای که آقای یوسفی در پوران گفتن میشه گفت که
T(n)=(nlgnlgn)
اگه از روش درخت بازگشتی هم این مسئله رو حل کنیم
nlgnn2lgn2n4lgn4...0=n(lgn12lgn214lgn4...0)
که تعداد جملات داخل پرانتز lgn تاست و خود جملات داخل پرانتز هم از مرتبه lgn است
که میشه
O(nlgnlgn)

ارسال: #۱۰
  

Masoud05 پاسخ داده:

RE: سوال از روابط بازگشتی

(۱۹ مهر ۱۳۹۰ ۰۱:۳۲ ق.ظ)ahmadnouri نوشته شده توسط:  با استفاده از تبصره ای که آقای یوسفی در پوران گفتن میشه گفت که
T(n)=(nlgnlgn)
اگه از روش درخت بازگشتی هم این مسئله رو حل کنیم
nlgnn2lgn2n4lgn4...0=n(lgn12lgn214lgn4...0)
که تعداد جملات داخل پرانتز lgn تاست و خود جملات داخل پرانتز هم از مرتبه lgn است
که میشه
O(nlgnlgn)
در ارسال های قبلی ،دوستان این مسئله رو با ۳ روش حل کردند:
۱- تغییر متغیر( توسط دوست خوبم mfXpert )
۲- روش اصلی( Master )
۳- روش جایگذاری .
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  روابط احساسی خارج از ازدواج مردان متأهل morweb ۶۲ ۳۵,۴۷۱ ۱۰ بهمن ۱۴۰۲ ۰۲:۴۱ ب.ظ
آخرین ارسال: fatemehbiglar
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) Saman ۶ ۷,۶۴۱ ۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ
آخرین ارسال: saeed_vahidi
  رسم درخت بازگشتی برای t(n)=9t(n/3)+n jumper ۶ ۶,۸۷۱ ۱۷ دى ۱۳۹۶ ۰۶:۱۶ ب.ظ
آخرین ارسال: jumper
  حل روابط بازگشتی درجه ۳ rahkaransg ۲ ۳,۱۶۷ ۱۴ دى ۱۳۹۶ ۰۵:۲۴ ب.ظ
آخرین ارسال: rahkaransg
  جواب رابطه های بازگشتی rahkaransg ۰ ۱,۸۸۶ ۱۴ دى ۱۳۹۶ ۱۲:۲۴ ق.ظ
آخرین ارسال: rahkaransg
  روابط بازگشتی amir_ghanati ۴ ۴,۲۳۳ ۰۴ شهریور ۱۳۹۶ ۰۳:۲۳ ق.ظ
آخرین ارسال: amir_ghanati
  حل رابطه بازگشتی Hopegod ۳ ۳,۱۸۸ ۲۰ اسفند ۱۳۹۵ ۰۷:۳۱ ب.ظ
آخرین ارسال: Hopegod
  حل سوال ۱۹ دکتری ۹۶ ( تابع بازگشتی ) arash691 ۰ ۱,۷۹۷ ۰۷ اسفند ۱۳۹۵ ۰۹:۴۰ ب.ظ
آخرین ارسال: arash691
  حل سوال ۱ دکتری ۹۶ ( رابطه بازگشتی ) arash691 ۰ ۱,۶۱۸ ۰۷ اسفند ۱۳۹۵ ۰۹:۱۰ ب.ظ
آخرین ارسال: arash691
  مشکل در حل روابط بازگشتی به روش تغییر متغییر sara27 ۲ ۴,۲۲۰ ۰۶ اسفند ۱۳۹۵ ۰۷:۲۳ ب.ظ
آخرین ارسال: arash691

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close