۰
subtitle
ارسال: #۱
حل یه رابطه بازگشتی و نکته مهم آن
سلام بچه ها
در کتاب پوران نوشته اگر داشته باشیم:
[tex]T(n)=aT(n-b) c[/tex]
پس می تونیم نتیجه بگیریم:
[tex]T(n)=\Theta (a^{\frac{n}{b}})[/tex]
اما در کتاب CLRS گفته اگه داشته باشیم
[tex]T(n)=aT(n-b) n[/tex]
داریم:
[tex]O(n^{2})[/tex]
به نظرم سی ال درست گفته چون می شه از روش جایگذاری حل کرد ولی پوران درست نیست. تازه این بعنوان تست یه بار در تستهای پارسه بوده
کسی می تونه مشکلشو بگه؟
در کتاب پوران نوشته اگر داشته باشیم:
[tex]T(n)=aT(n-b) c[/tex]
پس می تونیم نتیجه بگیریم:
[tex]T(n)=\Theta (a^{\frac{n}{b}})[/tex]
اما در کتاب CLRS گفته اگه داشته باشیم
[tex]T(n)=aT(n-b) n[/tex]
داریم:
[tex]O(n^{2})[/tex]
به نظرم سی ال درست گفته چون می شه از روش جایگذاری حل کرد ولی پوران درست نیست. تازه این بعنوان تست یه بار در تستهای پارسه بوده
کسی می تونه مشکلشو بگه؟
۰
ارسال: #۲
RE: حل یه رابطه بازگشتی و نکته مهم آن
خب گفته هر دو درسته توجه کنید در
[tex]T(n)=aT(n-b) c[/tex]
c عدد ثابتیه در حالیکه در رابطه بازگشتی که در Clrs گفته شده c نداریم بلکه n داریم
خب نتیجه اینکه دو تا رابطع بازگشتی با هم متفاوتند و گفته نویسنده دو کتاب هم درسته
شما میتونین رابطه ای که در کتاب پوران گفته شده رو هم ثابت کنید وببینید که درسته
[tex]T(n)=aT(n-b) c[/tex]
c عدد ثابتیه در حالیکه در رابطه بازگشتی که در Clrs گفته شده c نداریم بلکه n داریم
خب نتیجه اینکه دو تا رابطع بازگشتی با هم متفاوتند و گفته نویسنده دو کتاب هم درسته
شما میتونین رابطه ای که در کتاب پوران گفته شده رو هم ثابت کنید وببینید که درسته
۰
ارسال: #۳
RE: حل یه رابطه بازگشتی و نکته مهم آن
(۲۵ مهر ۱۳۹۰ ۱۱:۰۸ ق.ظ)پشتکار نوشته شده توسط: سلام بچه هاسلام این جا دو تا نکته متفاوت ودرست وجود داره
در کتاب پوران نوشته اگر داشته باشیم:
[tex]T(n)=aT(n-b) c[/tex]
پس می تونیم نتیجه بگیریم:
[tex]T(n)=\Theta (a^{\frac{n}{b}})[/tex]
اما در کتاب CLRS گفته اگه داشته باشیم
[tex]T(n)=aT(n-b) n[/tex]
داریم:
[tex]O(n^{2})[/tex]
به نظرم سی ال درست گفته چون می شه از روش جایگذاری حل کرد ولی پوران درست نیست. تازه این بعنوان تست یه بار در تستهای پارسه بوده
کسی می تونه مشکلشو بگه؟
اگر
T(n)=aT(n-b)+c
به شرط اینکه a,b,c مقادیر ثابت باشند انگاه خواهیم داشت
{t(n)=a^(n/m
اما اون چیزی که توی clrs گفته اینه که
T(n)=T(n-b)+g(n)
که g(n) بایستی چند جمله ای باشه و b عددی ثابت باشد در این صورت
[tex]O(n*g(n))[/tex]
که در سوال شما میشه
[tex]O(n*{n})[/tex]
ارسال: #۴
RE: حل یه رابطه بازگشتی و نکته مهم آن
(۲۵ مهر ۱۳۹۰ ۰۳:۱۷ ب.ظ)ahmadi_development نوشته شده توسط: سلام این جا دو تا نکته متفاوت ودرست وجود داره
اگر
T(n)=aT(n-b)+c
به شرط اینکه a,b,c مقادیر ثابت باشند انگاه خواهیم داشت
{t(n)=a^(n/m
اما اون چیزی که توی clrs گفته اینه که
T(n)=T(n-b)+g(n)
که g(n) بایستی چند جمله ای باشه و b عددی ثابت باشد در این صورت
[tex]O(n*g(n))[/tex]
که در سوال شما میشه
[tex]O(n*{n})[/tex]
منظورتون از عبارت { t(n)=a^(n/m
عبارت [tex]T(n)=\Theta (a^{\frac{n}{b}})[/tex] هست؟
بعدش اگه داشته باشیم:
[tex]T(n)=a.T(n-b) g(n)[/tex]
حالا باید چکار کرد؟
همینطور واسه عبارت [tex]T(n)=a.T(n b) g(n)[/tex]
مرسی
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close