زمان کنونی: ۲۵ شهریور ۱۳۹۸, ۰۲:۴۲ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

حل یه رابطه بازگشتی و نکته مهم آن

ارسال:
  

پشتکار پرسیده:

حل یه رابطه بازگشتی و نکته مهم آن

سلام بچه ها
در کتاب پوران نوشته اگر داشته باشیم:
[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]

به نظرم سی ال درست گفته چون می شه از روش جایگذاری حل کرد ولی پوران درست نیست. تازه این بعنوان تست یه بار در تستهای پارسه بوده
کسی می تونه مشکلشو بگه؟Huh

۰
ارسال:
  

ahmadnouri پاسخ داده:

RE: حل یه رابطه بازگشتی و نکته مهم آن

خب گفته هر دو درسته توجه کنید در
[tex]T(n)=aT(n-b) c[/tex]
c عدد ثابتیه در حالیکه در رابطه بازگشتی که در Clrs گفته شده c نداریم بلکه n داریم
خب نتیجه اینکه دو تا رابطع بازگشتی با هم متفاوتند و گفته نویسنده دو کتاب هم درسته
شما میتونین رابطه ای که در کتاب پوران گفته شده رو هم ثابت کنید وببینید که درستهCool

۰
ارسال:
  

ahmadi_development پاسخ داده:

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]

به نظرم سی ال درست گفته چون می شه از روش جایگذاری حل کرد ولی پوران درست نیست. تازه این بعنوان تست یه بار در تستهای پارسه بوده
کسی می تونه مشکلشو بگه؟Huh
سلام این جا دو تا نکته متفاوت ودرست وجود داره
اگر
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]

مرسی
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال از بازگشتی Aurora ۷ ۳,۲۹۰ ۱۷ شهریور ۱۳۹۱ ۱۱:۴۰ ب.ظ
آخرین ارسال: azad_ahmadi
  (کمک در حل تست) تابع بازگشتی مربوط به برج هانوی samaneh_aftab ۴ ۵,۵۰۶ ۰۵ تیر ۱۳۹۱ ۰۱:۰۴ ب.ظ
آخرین ارسال: Parva
Lightbulb درخواست راهنمایی در حل رابطه بازگشتی - rasool - ۵۱ ۵,۵۸۷ ۲۴ بهمن ۱۳۹۰ ۰۷:۱۷ ق.ظ
آخرین ارسال: sasanlive
Lightbulb روابط بازگشتی دو متغیره - rasool - ۳ ۲,۰۴۸ ۰۶ دى ۱۳۹۰ ۰۵:۲۷ ب.ظ
آخرین ارسال: homa
  یه سوال بازگشتی از قضیه اصلی پشتکار ۱۱ ۳,۴۹۲ ۰۹ آبان ۱۳۹۰ ۱۲:۱۲ ق.ظ
آخرین ارسال: sasanlive
Smile حل رابطه بازگشتی Mojtaba ۹ ۲,۲۶۶ ۰۶ آبان ۱۳۹۰ ۱۱:۰۵ ب.ظ
آخرین ارسال: - rasool -
  جواب رابطه بازگشتی زیر چیست؟ پشتکار ۷ ۲,۳۳۷ ۲۸ مهر ۱۳۹۰ ۱۱:۲۸ ق.ظ
آخرین ارسال: si.mozhgan
Question سوال از روابط بازگشتی livane_abi ۱۲ ۵,۶۶۹ ۱۹ مهر ۱۳۹۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: Masoud05
  مرتبه اجرایی تابع بازگشتی khavar_1365 ۶ ۷,۱۱۷ ۱۴ مهر ۱۳۹۰ ۱۱:۰۱ ب.ظ
آخرین ارسال: summer_66

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close