۰
subtitle
ارسال: #۱
تابع بازگشتی
سلام
من از تابع بازگشتی های زیر مشکل دارم ممنون میشم هر کسی که بلده واسم توضیح بده.
t(n)=3t(n/3+5)+n/2
t(n)=t(n-1)+2lgn
من از تابع بازگشتی های زیر مشکل دارم ممنون میشم هر کسی که بلده واسم توضیح بده.
t(n)=3t(n/3+5)+n/2
t(n)=t(n-1)+2lgn
۰
ارسال: #۲
تابع بازگشتی
سلام. سوال اول چون مقدار n بزرگ فرض میشه و دنباله هم لگاریتمیه، میتونید بنویسید t(n)=3t(n/3)+n/2. مشکلی پیش نمیاد. بجای (t(n/ 3^1000 باید بنویسیم (t(n/ 3^1000+7.5. جوابشم از روی درخت بازگشت و یا روش های دیگه بدست میاد. میشه n/2+3*n/6+9*n/27+... که میشه از مرتبه nlgn.
سوال دوم رو میشه اینجوری نوشت:
t(n)=t(n-1)+2lgn
(t(n-1)=2t(n-2)+2lg(n-1
...
t(2)=2t(1)+2lg1
نتیجه میگیریم:
t(n)=2lgn+2lg(n-1)+2lg(n-2)+...+2lg2
میدونیم lgn=lg(n/2)+1 و n تا جمله داریم. پس از مرتبه nlgn میشه.
سوال دوم رو میشه اینجوری نوشت:
t(n)=t(n-1)+2lgn
(t(n-1)=2t(n-2)+2lg(n-1
...
t(2)=2t(1)+2lg1
نتیجه میگیریم:
t(n)=2lgn+2lg(n-1)+2lg(n-2)+...+2lg2
میدونیم lgn=lg(n/2)+1 و n تا جمله داریم. پس از مرتبه nlgn میشه.
ارسال: #۳
RE: تابع بازگشتی
(۰۵ مرداد ۱۳۹۱ ۰۳:۳۶ ق.ظ)Jooybari نوشته شده توسط: سلام. سوال اول چون مقدار n بزرگ فرض میشه و دنباله هم لگاریتمیه، میتونید بنویسید t(n)=3t(n/3)+n/2. مشکلی پیش نمیاد. بجای (t(n/ 3^1000 باید بنویسیم (t(n/ 3^1000+7.5. جوابشم از روی درخت بازگشت و یا روش های دیگه بدست میاد. میشه n/2+3*n/6+9*n/27+... که میشه از مرتبه nlgn.اگه اولی از مستر حل بشه میشه
سوال دوم رو میشه اینجوری نوشت:
t(n)=t(n-1)+2lgn
(t(n-1)=2t(n-2)+2lg(n-1
...
t(2)=2t(1)+2lg1
نتیجه میگیریم:
t(n)=2lgn+2lg(n-1)+2lg(n-2)+...+2lg2
میدونیم lgn=lg(n/2)+1 و n تا جمله داریم. پس از مرتبه nlgn میشه.
f(n)=n/2 و n^log3 با پایه ۳ که میشه n
n از n/2 بزرگتره و جواب میشه از مرتبه n
اگه بخوام جوابم مثل شما بشه باید n=n/2 در نظر بگیرم که جوابم در اونصورت nlogn میشه!!
کجارو دارم غلط میگم که جوابم اشتباه بدست میاد؟
واسه دومی هم میشه یکم در مورد اینکه lgn=lg(n/2)+1 رو چه طور به حل ربط دادید یه کم بیشتر توضیح بدید؟
خیلی ممنون
۰
ارسال: #۴
تابع بازگشتی
سوال ۱ حالت خاص قضیه مستره. توی این حالت مستر جواب نمیده.
سوال ۲ مجموع n/2 جمله اول میشه:
نصف دیگه جملات که از این مقدار کمترن.
سوال ۲ مجموع n/2 جمله اول میشه:
[tex]n\lg n\geq\lg n \lg(n-1) ... \lg(n/2)\geq (\lg n-1)\times \frac{n}{2}=\frac{n\lg n}{2}-\frac{n}{2}\in \theta(n\times\lg n)[/tex]
نصف دیگه جملات که از این مقدار کمترن.
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
| تابع مولد | ss311 | ۰ | ۱,۳۳۶ |
۲۶ اردیبهشت ۱۳۹۹ ۱۲:۴۹ ب.ظ آخرین ارسال: ss311 |
|
| درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) | Saman | ۶ | ۶,۹۴۵ |
۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ آخرین ارسال: saeed_vahidi |
|
| تابع ورودی فلیپ فلاپ | naghmeh70 | ۳ | ۲,۸۸۴ |
۲۷ فروردین ۱۳۹۷ ۰۶:۵۹ ب.ظ آخرین ارسال: عزیز دادخواه |
|
| تابع منطقی | naghmeh70 | ۲ | ۲,۴۶۵ |
۲۷ فروردین ۱۳۹۷ ۱۱:۰۴ ق.ظ آخرین ارسال: naghmeh70 |
|
| تابع خروجی pla | naghmeh70 | ۲ | ۲,۹۶۶ |
۲۱ اسفند ۱۳۹۶ ۰۱:۴۶ ق.ظ آخرین ارسال: naghmeh70 |
|
| رسم درخت بازگشتی برای t(n)=9t(n/3)+n | jumper | ۶ | ۶,۱۲۰ |
۱۷ دى ۱۳۹۶ ۰۶:۱۶ ب.ظ آخرین ارسال: jumper |
|
| حل روابط بازگشتی درجه ۳ | rahkaransg | ۲ | ۲,۷۷۲ |
۱۴ دى ۱۳۹۶ ۰۵:۲۴ ب.ظ آخرین ارسال: rahkaransg |
|
| جواب رابطه های بازگشتی | rahkaransg | ۰ | ۱,۶۹۹ |
۱۴ دى ۱۳۹۶ ۱۲:۲۴ ق.ظ آخرین ارسال: rahkaransg |
|
| محاسبه تابع جرم احتمال | whynot2 | ۱ | ۳,۳۰۹ |
۱۵ آبان ۱۳۹۶ ۰۲:۳۴ ب.ظ آخرین ارسال: BBumir |
|
| روابط بازگشتی | amir_ghanati | ۴ | ۳,۷۳۰ |
۰۴ شهریور ۱۳۹۶ ۰۳:۲۳ ق.ظ آخرین ارسال: amir_ghanati |
|
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close