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

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

ارسال:
  

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 )
۳- روش جایگذاری .
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) 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
  حل رابطه بازگشتی arash691 ۲ ۷۹۹ ۰۶ اسفند ۱۳۹۵ ۱۱:۴۵ ق.ظ
آخرین ارسال: arash691

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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