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

همچنین

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

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

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

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


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

با نظر 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 )‌، پس یا اشتباه دیده (با احترام )و یا کتاب اشتباه زده !

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

دوست عزیز‌، توجه کنید که اگه ضریب ۲ داشت ،یعنی رابطه‌ی ما [tex]\large T(n)=2T(\frac{n}{2}) nlogn[/tex]
بود اونوقت با قضیه اصلی حل نمی شد. بلکه باید با راههای دیگه حل می کردیم که همانطوری که فرمودید می شه [tex]\large \theta (nlog^{2}n)[/tex]

تاپیک مرتبط:


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

جمع بندی:

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

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

[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] می شود.

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

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




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

با استفاده از تبصره ای که آقای یوسفی در پوران گفتن میشه گفت که
[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]

(۱۹ مهر ۱۳۹۰ ۰۱:۳۲ ق.ظ)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 )
۳- روش جایگذاری .