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

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

ارسال:
  

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

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

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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Video دانلود رایگان نکته و تست شبکه های کامپیوتری Farzamm ۴ ۶۲۰ ۱۹ مرداد ۱۳۹۹ ۰۴:۰۷ ب.ظ
آخرین ارسال: poyaadami
  درخواست فیلم نکته تست نظریه دکتر کارگهی juyaye danesh ۰ ۱۳۴ ۲۵ تیر ۱۳۹۹ ۰۱:۰۸ ب.ظ
آخرین ارسال: juyaye danesh
Video دانلود رایگان نکته و تست احتمال و آمار مهندسی Farzamm ۰ ۲۴۶ ۱۸ خرداد ۱۳۹۹ ۰۱:۲۹ ب.ظ
آخرین ارسال: Farzamm
  انتخاب فیلم یا کتاب نکته و تست sima84 ۴ ۳۳۳ ۱۶ اردیبهشت ۱۳۹۹ ۰۸:۳۴ ب.ظ
آخرین ارسال: sima84
Question یک نکته ابهام marvelous ۶ ۸۶۴ ۰۹ دى ۱۳۹۸ ۰۱:۳۰ ب.ظ
آخرین ارسال: marvelous
  طراحی و چاپ کاتالوگ - اصول مهم و کاربردی طراحی بنر aframehr ۰ ۳۸۱ ۲۵ تیر ۱۳۹۸ ۱۲:۵۳ ق.ظ
آخرین ارسال: aframehr
  ۶ نکته در خرید تجهیزات آشپزخانه های صنعتی roshaa ۰ ۵۰۱ ۰۸ خرداد ۱۳۹۸ ۰۳:۵۶ ب.ظ
آخرین ارسال: roshaa
  [دانلود] جزوه و ویس جلسه نکته تست ساختمان داده والگوریتم استاد یوسفی زمستان ٩٣ software94 ۲۳ ۱۵,۸۳۹ ۰۲ فروردین ۱۳۹۸ ۱۲:۳۲ ق.ظ
آخرین ارسال: honiehs
  با ۲۸ نکته کلیدی سایت خود را سئو کنید melinaa ۰ ۵۹۴ ۰۴ شهریور ۱۳۹۷ ۱۰:۳۶ ق.ظ
آخرین ارسال: melinaa
  ۱۴۷ ای تی ___انتخاب رشته مهم مهم _خواهشا کمکم کنید وقت ندارم Rezaprince ۱ ۷۲۲ ۱۲ مرداد ۱۳۹۷ ۰۶:۱۷ ب.ظ
آخرین ارسال: Happiness.72

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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