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

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

ارسال:
  

livane_abi پرسیده:

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

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

۲
ارسال:
  

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

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

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

همچنین

پاسخ رابطه‌ی‌: [tex]\large T(n)=T(\frac{n}{2}) nlogn[/tex]

به سادگی از راه قضیه اصلی حل می شه و جواب [tex]\large \theta (nlogn)[/tex]
خواهد بود.

۱
ارسال:
  

mfXpert پاسخ داده:

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

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

۰
ارسال:
  

mfXpert پاسخ داده:

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

اول تغییر متغیر زیر رو در نظر می گیریم:
[tex]n=2^{k}\Rightarrow k=lgn[/tex]
حالا شکل معادله رو بعد از اعمال تغییر متغیر می نویسیم:
[tex]T(2^{k})=T(2^{k-1}) 2^{k}k[/tex]
حالا با در نظر گرفتن [tex]S(k)=T(2^{k})[/tex] داریم:
[tex]S(k)=S(k-1) 2^{k}k[/tex]
معادله بالا یک معادله بازگشتی نا همگن با ضرایب ثابت هستش که معادله مشخصه اون به صورت زیر هستش:
[tex](k-2)^{2}=0[/tex]
معادله بالا ریشه مضاعف داره و اگر ریشه‌ها رو در جواب عمومی معادلات بازگشتی قرار بدیم داریم:
[tex]S(k)=C_{1}2^{k} C_{2}k2^{k}[/tex]
حالا با تغییر متغیر معکوس داریم:
[tex]T(n)=C_{1}n C_{2}nlgn[/tex]
پس T از مرتبه تتای nlgn هستش


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

۰
ارسال:
  

yarandish پاسخ داده:

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

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

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

ارسال:
  

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

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

(۱۸ مهر ۱۳۹۰ ۰۶:۱۷ ب.ظ)yarandish نوشته شده توسط:  ،طبق قضیه اصلی جواب در صورتی این می شود که سوال ضریب ۲ داشته باشد (!T(N)=2T(N/2)+LGN )‌،
دوست عزیز‌، توجه کنید که اگه ضریب ۲ داشت ،یعنی رابطه‌ی ما [tex]\large T(n)=2T(\frac{n}{2}) nlogn[/tex]
بود اونوقت با قضیه اصلی حل نمی شد. بلکه باید با راههای دیگه حل می کردیم که همانطوری که فرمودید می شه [tex]\large \theta (nlog^{2}n)[/tex]

تاپیک مرتبط:


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

۰
ارسال:
  

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

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

جمع بندی:

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

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

[tex]\large T(n)=T(\frac{n}{2}) nlogn[/tex]

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

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

[tex]\large T(n)=2T(\frac{n}{2}) nlogn[/tex]

** با قضیه اصلی حل نمی شود. (ولی می توان با تبصره و تعمیمی که در این مورد وجود دارد آن را حل کرد)
** می توان از راه درختی آن را حل کرد.
** پاسخ آن [tex]\large O(nlog^{2}n)[/tex] می شود.

۰
ارسال:
  

Masoud05 پاسخ داده:

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

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

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




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

۰
ارسال:
  

ahmadnouri پاسخ داده:

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

با استفاده از تبصره ای که آقای یوسفی در پوران گفتن میشه گفت که
[tex]T(n)=\bigcirc (n* lgn * lgn)[/tex]
اگه از روش درخت بازگشتی هم این مسئله رو حل کنیم
[tex]nlgn \frac{n}{2}lg\frac{n}{2} \frac{n}{4}lg\frac{n}{4} ... 0 = n(lgn \frac{1}{2}lg\frac{n}{2} \frac{1}{4}lg\frac{n}{4} ... 0)[/tex]
که تعداد جملات داخل پرانتز lgn تاست و خود جملات داخل پرانتز هم از مرتبه lgn است
که میشه
[tex]O(n*lgn*lgn)[/tex]

ارسال: #۱۰
  

Masoud05 پاسخ داده:

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

(۱۹ مهر ۱۳۹۰ ۰۱:۳۲ ق.ظ)ahmadnouri نوشته شده توسط:  با استفاده از تبصره ای که آقای یوسفی در پوران گفتن میشه گفت که
[tex]T(n)=\bigcirc (n* lgn * lgn)[/tex]
اگه از روش درخت بازگشتی هم این مسئله رو حل کنیم
[tex]nlgn \frac{n}{2}lg\frac{n}{2} \frac{n}{4}lg\frac{n}{4} ... 0 = n(lgn \frac{1}{2}lg\frac{n}{2} \frac{1}{4}lg\frac{n}{4} ... 0)[/tex]
که تعداد جملات داخل پرانتز lgn تاست و خود جملات داخل پرانتز هم از مرتبه lgn است
که میشه
[tex]O(n*lgn*lgn)[/tex]
در ارسال های قبلی ،دوستان این مسئله رو با ۳ روش حل کردند:
۱- تغییر متغیر( توسط دوست خوبم mfXpert )
۲- روش اصلی( Master )
۳- روش جایگذاری .
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال از بازگشتی Aurora ۷ ۳,۲۰۳ ۱۷ شهریور ۱۳۹۱ ۱۱:۴۰ ب.ظ
آخرین ارسال: azad_ahmadi
  (کمک در حل تست) تابع بازگشتی مربوط به برج هانوی samaneh_aftab ۴ ۵,۴۱۴ ۰۵ تیر ۱۳۹۱ ۰۱:۰۴ ب.ظ
آخرین ارسال: Parva
Lightbulb درخواست راهنمایی در حل رابطه بازگشتی - rasool - ۵۱ ۵,۴۸۸ ۲۴ بهمن ۱۳۹۰ ۰۷:۱۷ ق.ظ
آخرین ارسال: sasanlive
Lightbulb روابط بازگشتی دو متغیره - rasool - ۳ ۱,۹۷۸ ۰۶ دى ۱۳۹۰ ۰۵:۲۷ ب.ظ
آخرین ارسال: homa
  یه سوال بازگشتی از قضیه اصلی پشتکار ۱۱ ۳,۳۴۳ ۰۹ آبان ۱۳۹۰ ۱۲:۱۲ ق.ظ
آخرین ارسال: sasanlive
Smile حل رابطه بازگشتی Mojtaba ۹ ۲,۲۱۴ ۰۶ آبان ۱۳۹۰ ۱۱:۰۵ ب.ظ
آخرین ارسال: - rasool -
  جواب رابطه بازگشتی زیر چیست؟ پشتکار ۷ ۲,۲۴۵ ۲۸ مهر ۱۳۹۰ ۱۱:۲۸ ق.ظ
آخرین ارسال: si.mozhgan
  حل یه رابطه بازگشتی و نکته مهم آن پشتکار ۴ ۲,۲۵۷ ۲۵ مهر ۱۳۹۰ ۱۱:۵۲ ب.ظ
آخرین ارسال: ahmadi_development
  مرتبه اجرایی تابع بازگشتی khavar_1365 ۶ ۶,۹۷۶ ۱۴ مهر ۱۳۹۰ ۱۱:۰۱ ب.ظ
آخرین ارسال: summer_66

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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