T(n)=2T(n/2) + n/logn
۱)بچه ها کسی میتونه حل اینو برام توضیح بده!!
پارسه درخت بازگشتیو برای فقطn/lognکشیده ک من سر درنیاوردم ازش!
۲)تو رابطه بازگشتی زیر مرتبه رو n^2بگیریم؟؟پارسه حل کرده شدهn^2 logn
T(n)= 16T(n/4) + n^2
سلام برای پاسخ به سوال اولتون ببینید.
درختشو رسم میکنیم.من به صورت سطح سطح براتون مینویسم:
سطح اول(فقط ریشه)[tex]\leftarrow[/tex][tex]\frac{n}{Logn}[/tex]
سطح دوم[tex]\leftarrow[/tex][tex]\frac{\frac{n}{2}}{\log(\frac{n}{2})},\frac{\frac{n}{2}}{\log(\frac{n}{2})}[/tex]
سطح سوم[tex]\leftarrow[/tex] 4 تا عبارت [tex]\frac{\frac{n}{4}}{Log(\frac{n}{4})}[/tex] داریم
سطوح بعدی هم همین ریتم رو داره.حالا باید مقادیر تمام سطوح رو با هم جمع بزنیم:
[tex]\frac{n}{\log(n)} \frac{n}{\log(\frac{n}{2})} \frac{n}{\log(\frac{n}{4})} \frac{n}{\log(\frac{n}{8})} ......[/tex]
که حالا اینجری ساده میکنیم:
[tex]\: n(\frac{1}{\log(n)} \frac{1}{\log(n)-1} \frac{1}{\log(n)-2} \frac{1}{\log(n)-3} ......)[/tex]
که این عبارت همین عبارته زیره و ما اونو برعکس نوشتیم:
[tex]n(\frac{1}{1} \frac{1}{2} \frac{1}{3} .... \frac{1}{Log(n)})[/tex]
و این رابطه رو هم میدونیم:
[tex](\frac{1}{1} \frac{1}{2} \frac{1}{3} .... \frac{1}{EveryThing})=Ln(EveryThing)[/tex]
پس برای رابطه بالا داریم:
[tex]n(\frac{1}{1} \frac{1}{2} \frac{1}{3} .... \frac{1}{Log(n)})=n\ast Ln(Log(n))=(n)LogLog(n)[/tex]
پاسخ سوال دومتون هم ببینید رابطه ما اینه:
[tex]T(n)=16T(\frac{n}{4}) n^2[/tex]
از قضیه اصلی استفاده میکنیم:[tex]Log^{16}_4=2\rightarrow n^2=n^2\rightarrow T(n)=n^2Log(n)[/tex]
[tex]n^2[/tex] سمت راست همون [tex]n^2[/tex] تو معادله هستش
موضوع اینه چرا فقط برای n/lognدرخت اومده کشیده؟؟؟؟؟؟؟؟
بعدم رو چ حساب nlognتو سطح بعد میشه ۲تا[tex]\frac{n}{\frac{2}{\log(\frac{n}{2})}}[/tex] میشه؟؟؟؟؟
ببخشید این توضیحات رو میدم جسارت نباشه!!!
ببینید درخت بازگشت رو چجوری رسم میکنیم؟؟
قسمت ثابت ریشه و شاخه هامون هم قسمت های بازگشتی میشن قبول؟؟؟؟
حالا قسمت ثابت چیه؟[tex]\frac{n}{Log(n)}[/tex]
و در ضمن ما رابطه اصلی رو به این رابطه تبدیل میکنیم:[tex]T(n)=T(\frac{n}{2}) T(\frac{n}{2}) \frac{n}{Log(n)}[/tex]
خب ریشه که شد [tex]\frac{n}{Log(n)}[/tex] و شاخه سمت چپ و راست که یکین.حالا شاخه چجوریه.دقت کنید قسمت بازگشتی ما به صورت [tex]\frac{n}{2}[/tex] هستش به زبون ساده میگم تو سطح بعد هر جا [tex]n[/tex] دیدی جاش [tex]n/2[/tex] بذار خب؟؟؟
حالا ما [tex]\frac{n}{Log(n)}[/tex] رو داریم جای [tex]n[/tex] هاش [tex]n/2[/tex] میذاریم که میشه:[tex]\frac{\frac{n}{2}}{Log(\frac{n}{2})}[/tex]
ببینید ما در واقع اصل کار اینه [tex]\frac{n}{Log(n)}[/tex] رو داریم و هر بار داریم نصفش میکنیم
مشکل من همین رسم درخت بازگشتی بود!!!!!
پس همیشه مقدار ثابت رو ریشه میگیرم!!مث روند تقسیم و حل فرزندانش رو میسازیم درسته؟
مثلا تو مسئله زیر داریم:
[tex]T(n)=T(\frac{n}{5}) T(\frac{7n}{10}) n[/tex]
ریشه رو n می گیریم بعد فرزند چپ میشه [tex]\frac{n}{5}[/tex]فرزند راست هم میشه[tex]\frac{7n}{10}[/tex]
بعد زیر درخت چپ هر دفعه بجای n میزاریم [tex]\frac{n}{5}[/tex] برای زیر درخت راست هم بجای n میزاریم [tex]\frac{7n}{10}[/tex]؟؟؟؟؟؟؟
درست میگم یا نه؟
(۱۳ دى ۱۳۹۳ ۰۱:۴۷ ب.ظ)shamim_70 نوشته شده توسط: مشکل من همین رسم درخت بازگشتی بود!!!!!
پس همیشه مقدار ثابت رو ریشه میگیرم!!مث روند تقسیم و حل فرزندانش رو میسازیم درسته؟
مثلا تو مسئله زیر داریم:
[tex]T(n)=T(\frac{n}{5}) T(\frac{7n}{10}) n[/tex]
ریشه رو n می گیریم بعد فرزند چپ میشه [tex]\frac{n}{5}[/tex]فرزند راست هم میشه[tex]\frac{7n}{10}[/tex]
بعد زیر درخت چپ هر دفعه بجای n میزاریم [tex]\frac{n}{5}[/tex] برای زیر درخت راست هم بجای n میزاریم [tex]\frac{7n}{10}[/tex]؟؟؟؟؟؟؟
درست میگم یا نه؟
بله کاملا درسته!!!!ببین هر بار که داشتی میشکستی یه نودی رو باید دو شاخه براش بذاری یکی از شاخه ها n/10 و یکی ۷n/10