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

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

ارسال:
  

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

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

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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال مهم از کمتازیا jamshid51 ۰ ۴۹۴ ۲۹ مهر ۱۳۹۹ ۱۰:۰۷ ب.ظ
آخرین ارسال: jamshid51
Video دانلود رایگان نکته و تست شبکه های کامپیوتری Farzamm ۷ ۵,۲۳۲ ۱۹ مهر ۱۳۹۹ ۰۲:۵۵ ق.ظ
آخرین ارسال: Behnam‌
  درخواست فیلم نکته تست نظریه دکتر کارگهی juyaye danesh ۰ ۵۷۰ ۲۵ تیر ۱۳۹۹ ۰۱:۰۸ ب.ظ
آخرین ارسال: juyaye danesh
Video دانلود رایگان نکته و تست احتمال و آمار مهندسی Farzamm ۰ ۹۷۹ ۱۸ خرداد ۱۳۹۹ ۰۱:۲۹ ب.ظ
آخرین ارسال: Farzamm
  دوره آموزشی آنلاین Hadoop و Apache Spark به زبان فارسی Happiness.72 ۰ ۸۱۵ ۰۲ خرداد ۱۳۹۹ ۱۰:۳۸ ب.ظ
آخرین ارسال: Happiness.72
  انتخاب فیلم یا کتاب نکته و تست sima84 ۴ ۱,۰۲۹ ۱۶ اردیبهشت ۱۳۹۹ ۰۸:۳۴ ب.ظ
آخرین ارسال: sima84
  آنیل کوک raha701 ۰ ۷ ۱۴ اسفند ۱۳۹۸ ۰۵:۵۲ ب.ظ
آخرین ارسال: raha701
  وب کنفرانس و کلاس آنلاین faraz_linux ۰ ۵۴۰ ۱۰ اسفند ۱۳۹۸ ۰۷:۲۲ ب.ظ
آخرین ارسال: faraz_linux
Question یک نکته ابهام marvelous ۶ ۱,۶۵۲ ۰۹ دى ۱۳۹۸ ۰۱:۳۰ ب.ظ
آخرین ارسال: marvelous
  ۶ نکته در خرید تجهیزات آشپزخانه های صنعتی roshaa ۰ ۹۸۱ ۰۸ خرداد ۱۳۹۸ ۰۳:۵۶ ب.ظ
آخرین ارسال: roshaa

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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