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

حل رابطه بازگشتی

ارسال:
  

ahmadnouri پرسیده:

حل رابطه بازگشتی

دوستان در حل روابط زیر لطفا کمک کنین
[tex]T(n)=T(n-1) lgn[/tex]
[tex]T(n)=T(n-2) 2lgn[/tex]

۰
ارسال:
  

mfXpert پاسخ داده:

RE: حل رابطه بازگشتی

اولیش با یه نگاه حل میشه! از مرتبه بیگ اوی nlgn هستش.
از روش جایگذاری داریم:
[tex]T(n)=lg(n) lg(n-1) lg(n-2) ... lg(1)=lg(n*(n-1)*(n-2)*...*1)=lg(n!)[/tex]
و میدونیم که تابع [tex]lg(n!)[/tex] از مرتبه [tex]nlgn[/tex] هستش.پس مرتبه تابع برابر هست با تتای nlgn

دومی هم حلش نباید خیلی سخت باشه.اما الان حال حل کردنش رو ندارم

۰
ارسال:
  

deledivouneh پاسخ داده:

RE: حل رابطه بازگشتی

یه نکته تو کتاب پوران پژوهش هست که گفته
T(n)=T(n-a)+a lgn
هر رابطه به این شکل عبارت است از:
T(n)=nlgn

۰
ارسال:
  

ahmadnouri پاسخ داده:

RE: حل رابطه بازگشتی

ببخشید اگه من جواب میدم

بجای [tex]\frac{T(n)}{n}=f(m)[/tex]
بنابرای میشه نوشت [tex]\frac{T(\sqrt{n})}{\sqrt{n}}=\frac{T(n^{\frac{1}{2}})}{n^{\frac{1}{2}}} =f(\frac{m}{2})[/tex]



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  نظر در رابطه با استاد داور علیصا ۰ ۱,۴۳۴ ۱۴ مهر ۱۴۰۰ ۰۶:۰۵ ب.ظ
آخرین ارسال: علیصا
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) Saman ۶ ۶,۸۱۳ ۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ
آخرین ارسال: saeed_vahidi
  رابطه n~1 Mr.R3ZA ۰ ۱,۷۲۳ ۲۰ خرداد ۱۳۹۷ ۰۱:۳۵ ق.ظ
آخرین ارسال: Mr.R3ZA
  توصیه های مهم در رابطه با انتخاب رشته (مهم) Happiness.72 ۰ ۱,۹۳۲ ۱۹ خرداد ۱۳۹۷ ۱۲:۳۶ ق.ظ
آخرین ارسال: Happiness.72
  رابطه چند به یک somayeh afsh ۰ ۱,۵۳۹ ۰۷ خرداد ۱۳۹۷ ۱۲:۲۸ ب.ظ
آخرین ارسال: somayeh afsh
  رسم درخت بازگشتی برای t(n)=9t(n/3)+n jumper ۶ ۶,۰۳۸ ۱۷ دى ۱۳۹۶ ۰۶:۱۶ ب.ظ
آخرین ارسال: jumper
  حل رابطه جایگذاری با تکرار rahkaransg ۱ ۱,۹۴۲ ۱۷ دى ۱۳۹۶ ۱۱:۲۹ ق.ظ
آخرین ارسال: rahkaransg
  حل روابط بازگشتی درجه ۳ rahkaransg ۲ ۲,۷۰۴ ۱۴ دى ۱۳۹۶ ۰۵:۲۴ ب.ظ
آخرین ارسال: rahkaransg
  جواب رابطه های بازگشتی rahkaransg ۰ ۱,۶۶۸ ۱۴ دى ۱۳۹۶ ۱۲:۲۴ ق.ظ
آخرین ارسال: rahkaransg
  تقسیم در جبر رابطه ای Ella ۱ ۲,۰۰۹ ۲۸ آذر ۱۳۹۶ ۱۲:۰۰ ق.ظ
آخرین ارسال: Ella

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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