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

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

ارسال:
  

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

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

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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  دریافت مدارک تحصیلی به صورت آنلاین امکان داره ؟ MohsenRezaei ۱ ۲۰۷ ۰۹ دى ۱۴۰۲ ۰۴:۰۲ ب.ظ
آخرین ارسال: MohsenRezaei
  جزوه خلاصه نکات مهم فصول ابتدایی درس مهندسی نرم افزار Happiness.72 ۱ ۳,۴۸۷ ۱۳ خرداد ۱۴۰۱ ۰۶:۲۸ ب.ظ
آخرین ارسال: M o h m m @ d
Video دانلود رایگان نکته و تست شبکه های کامپیوتری Farzamm ۱۱ ۱۷,۶۰۶ ۰۷ بهمن ۱۴۰۰ ۰۱:۰۳ ب.ظ
آخرین ارسال: M.rahimi20
  تصمیم گیری مهم درباره مکان سرور سایت admin ۴ ۴,۳۲۱ ۲۸ دى ۱۴۰۰ ۰۳:۵۹ ب.ظ
آخرین ارسال: mahsa3323
  نظر در رابطه با استاد داور علیصا ۰ ۱,۴۳۳ ۱۴ مهر ۱۴۰۰ ۰۶:۰۵ ب.ظ
آخرین ارسال: علیصا
  سوال مهم از کمتازیا jamshid51 ۰ ۱,۷۵۸ ۲۹ مهر ۱۳۹۹ ۱۰:۰۷ ب.ظ
آخرین ارسال: jamshid51
  درخواست فیلم نکته تست نظریه دکتر کارگهی juyaye danesh ۰ ۱,۸۰۳ ۲۵ تیر ۱۳۹۹ ۰۱:۰۸ ب.ظ
آخرین ارسال: juyaye danesh
Video دانلود رایگان نکته و تست احتمال و آمار مهندسی Farzamm ۰ ۳,۵۷۲ ۱۸ خرداد ۱۳۹۹ ۰۱:۲۹ ب.ظ
آخرین ارسال: Farzamm
  دوره آموزشی آنلاین Hadoop و Apache Spark به زبان فارسی Happiness.72 ۰ ۲,۲۳۴ ۰۲ خرداد ۱۳۹۹ ۱۰:۳۸ ب.ظ
آخرین ارسال: Happiness.72
  انتخاب فیلم یا کتاب نکته و تست sima84 ۴ ۳,۶۹۴ ۱۶ اردیبهشت ۱۳۹۹ ۰۸:۳۴ ب.ظ
آخرین ارسال: sima84

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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