چند تابع بازگشتی هستند که کلافه ام کردن
اولی رو میدونم که میشه n log logn ولی توی حل کردنش به جواب نمیرسم:[tex]T(n)\: =\: 2T(\frac{n}{2})\: \: \frac{n}{\log\: n}[/tex]
این مورد رو هم اینجوری حل کردم که به نظر خیلی دقیق نیست.
[tex]T(n)=T(\frac{n}{3}) \: T(\frac{n}{6}) \: n^{\sqrt{\log n}}[/tex]
من گفتم توی درختش که میکشیم مسیر T(n/3) دیرتر به پایان میرسه پس زمان معادله بالا کوچکتر از زمانیه که به جای T(n/6) هم T(n/3) بگذاریم و بعد از قضیه Master این قسمت میشه [tex]n^{^{\log^{2_{_3}}}}[/tex] که طبیعتا زمان تابع نمایی بیشتره . جواب هم میشه [tex]n^{\sqrt{\log n}}[/tex]
مورد بعدی رو اصلا نمیفهمم که چرا جواب میشه : [tex]\sqrt{2^{(n^2 n)}}[/tex]
[tex]T(n)\: =\: 2^nT(n-1)[/tex]
(۰۲ دى ۱۳۹۳ ۰۱:۴۵ ب.ظ)ana9940 نوشته شده توسط: چند تابع بازگشتی هستند که کلافه ام کردن
[tex]T(n)\: =\: 2T(\frac{n}{2})\: \: \frac{n}{\log\: n}[/tex]
این مورد رو هم اینجوری حل کردم که به نظر خیلی دقیق نیست.
[tex]T(n)=T(\frac{n}{3}) \: T(\frac{n}{6}) \: n^{\sqrt{\log n}}[/tex]
من گفتم توی درختش که میکشیم مسیر T(n/3) دیرتر به پایان میرسه پس زمان معادله بالا کوچکتر از زمانیه که به جای T(n/6) هم T(n/3) بگذاریم و بعد از قضیه Master این قسمت میشه [tex]n^{^{\log^{2_{_3}}}}[/tex] که طبیعتا زمان تابع نمایی بیشتره . جواب هم میشه [tex]n^{\sqrt{\log n}}[/tex]
مورد بعدی رو اصلا نمیفهمم که چرا جواب میشه : [tex]\sqrt{2^{(n^2 n)}}[/tex]
[tex]T(n)\: =\: 2^nT(n-1)[/tex]
=============
لطفا عکس بزارید مشخص نیست
(۰۲ دى ۱۳۹۳ ۰۱:۵۷ ب.ظ)flowerirani نوشته شده توسط: لطفا عکس بزارید مشخص نیست
عکس سوالات یا راه حلم؟؟
اگه صورت texها نمیاد، یه refresh کنید حل میشه.
سلام برای پاسخ به سوال اولتون ببینید.
درختشو رسم میکنیم.من به صورت سطح سطح براتون مینویسم:
سطح اول(فقط ریشه)[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)=2^nT(n-1)=2^n\ast2^{n-1}\ast T(n-2)=2^n\ast2^{n-1}\ast2^{n-2}\ast T(n-3)....[/tex]
و همین طور ادامه میدیم تا به حالت پایه برسیم که اخر کار به یه همچین شکلی میرسیم:
[tex]T(n)=2^n\ast2^{n-1}\ast2^{n-2}\ast2^{n-3}\ast2^{n-4}\ast2^{n-5}\ast.......\ast2^0=2^{0 1 2 3 4 ....n-2 n-1 n}=2^{\frac{n(n 1)}{2}}=\sqrt{2^{(n^2 n)}}[/tex]
مـــــــــــرسی
الان که حل شدن به نظرم خیلی آسونه، نمیدونم چرا خودم نمیتونستم حلشون کنم.
خواهش میکنم کاری نکردم