سوال:[tex]T\left ( n \right )= 2T \left ( \frac{n}{2} \right )\dotplus n\log n[/tex]
تعمیم قضیه اصلی: صفحه ۷۹ کتاب طراحی الگوریتم مقسمی
[tex]T\left ( n \right )= aT\left ( n/b \right ) c f\left ( n \right )[/tex]
اگر [tex] n^{log_{b}^{a}}> O\left ( f\left ( n \right ) \right )[/tex]
[tex]T\left ( n \right )= O\left (n^{log _{b}^{a}} \right )[/tex]
اگر [tex]n^{log_{b}^{a}}< O\left ( f\left ( n \right ) \right )[/tex]
[tex]T\left ( n \right )= O\left ( f\left ( n \right ) \right )[/tex]
اگر [tex]a= b[/tex]
[tex]T\left ( n \right )= \log n\ast O\left ( f\left ( n \right ) \right )[/tex]
شرط سوم برقرار میشه و جواب [tex]T\left ( n \right )= O\left ( n\cdot log^{2}n \right )[/tex]
یه سوال مگه ما اینجا n . log ^2 n داریم تو صورت سوال؟؟؟؟
شرط سوم که a=b هست برقرار میشه
که [tex]T\left ( n \right )= \log n\ast O\left ( f\left ( n \right ) \right )=\log n\ast nlogn= n\ast log^{2}n[/tex]
سلام به همگی
بچه ها این مساله رو نمیشه از طریق قضیه اصلی رفت. چون nlogn به صورت چند جمله ای از n بزرگتر نیست.
باید این مساله رو از طریق حدس یا جایگذاری حل کرد.
این شرط هایی هم که parva نوشته کامل نیستند.
حدسی در کار نیست. با درخت بازگشت راحت قابل فهمه. سطر اول nlgn، سطر بعد میشه (nlg(n/2 و ... و در آخر هم nlg1 که اگه از n فاکتور بگیریم و با درنظر گرفتن lgn=lg(n/2)+1 به جواب میرسیم. اگرم مبنای لگاریتم بجای ۲ عدد نپر بود هم فرقی نمیکرد. قضیه اصلی هم حالت کلی داره و یه استثنا. شرایطشم مشخصه. ولی شاید فهمش و اثبات درست بودنش سخت باشه.
(۱۱ مرداد ۱۳۹۱ ۱۱:۰۸ ب.ظ)Jooybari نوشته شده توسط: حدسی در کار نیست. با درخت بازگشت راحت قابل فهمه. سطر اول nlgn، سطر بعد میشه (nlg(n/2 و ... و در آخر هم nlg1 که اگه از n فاکتور بگیریم و با درنظر گرفتن lgn=lg(n/2)+1 به جواب میرسیم. اگرم مبنای لگاریتم بجای ۲ عدد نپر بود هم فرقی نمیکرد. قضیه اصلی هم حالت کلی داره و یه استثنا. شرایطشم مشخصه. ولی شاید فهمش و اثبات درست بودنش سخت باشه.اگر از راه درخت بریم چطوری میشه؟
درخت رو که کشیدید مجموع هر سطر میشه ۲n logn؟ بعدش مجموع رو چطور حساب می کنید؟ میشه یکم بیشتر توضیح بدید.
(۱۱ مرداد ۱۳۹۱ ۱۱:۰۸ ب.ظ)Jooybari نوشته شده توسط: حدسی در کار نیست. با درخت بازگشت راحت قابل فهمه. سطر اول nlgn، سطر بعد میشه (nlg(n/2 و ... و در آخر هم nlg1 که اگه از n فاکتور بگیریم و با درنظر گرفتن lgn=lg(n/2)+1 به جواب میرسیم. اگرم مبنای لگاریتم بجای ۲ عدد نپر بود هم فرقی نمیکرد. قضیه اصلی هم حالت کلی داره و یه استثنا. شرایطشم مشخصه. ولی شاید فهمش و اثبات درست بودنش سخت باشه.خوب هر کسی از یه راهی می ره. منم گفتم حدس یا جایگذاری.
ضمن اینکه حل کردن این مساله از طریق قضیه ی اصلی از بیخ اشتباه است. بهتر قضیه ی اصلی رو اول فهمید بعد به کار برد.
دوستانی که این جواب ها رو دادند احتمالا ساختمان داده رو از روی کتاب تست مطالعه می کنند(حدس می زنم).
اولین شرط استفاده از قضیه ی اصلی اینه که اون جملات رابطه ی چند جمله ای داشته باشند.
بنظر منم شرایط قضیه اصلی صدق نمیکنه. چون نسبت [tex]\frac{f(n)}{n^{\log^{a}_{b}}}=\frac{nlogn}{n}=logn[/tex] که رابطه چند جمله ای را نمیده.
من با درخت بازگشت امتحان کردم میشه به جواب رسید:
تو سطح اول گره ریشه هزینش هست n logn
سطح دوم دو تا گره داریم که هرکدوم هزینش هست n/2 log n/2 که کل هزینه این سطح میشه n log n/2
سطح سوم چهار تا گره داریم که هر کدوم هزینش هست n/4 log n/4 که کلش میشه n log n/4
...
تو سطح k ام ۲ به توان k تا گره داریم که هزینه هرکدومش هست [tex]\frac{n}{2^{k}} log \frac{n}{2^{k}}[/tex] و کل هزینه سطح آخر میشه n log n/2^k
سیگما که بگیریم میشه:
[tex]n[logn log\frac{n}{2} log\frac{n}{4} ... log\frac{n}{2^{k}}][/tex]
[tex]=n[(logn logn ... logn)-(log2 log4 ... log2^{k})][/tex]
که تعداد log های داخل پرانتزها برابر ارتفاع درخت یعنی k=logn هست. ساده که بشه میرسیم به رابطه زیر:
[tex]n[(logn\times logn)-(1 2 ... k))]=n[(log^{2}n)-(\frac{(logn)(logn 1)}{2})][/tex]
که میشه [tex]\Theta (nlog^{2}n)[/tex]