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

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

ارسال:
  

Mojtaba پرسیده:

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

با سلام
لطفا بنده را در حل این بازگشتی کمک کنید .قبلا از همکاریتون کمال تشکر را دارم .ممنون[/font][/align]
T(n)=T(n/2+√n)+n

۰
ارسال:
  

- rasool - پاسخ داده:

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

----------------------------- ان شاء الله حل کامل و درستش رو اینجا قرار خواهم داد.

ارسال:
  

Mojtaba پاسخ داده:

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

بابت جوابی که دادین خیلی ممنونم.ان شاالله هر جا هستید موفق و پیروز باشید و در کنکور هم یک رتبه عالی کسب کنید.
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

sasanlive پاسخ داده:

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

(۰۳ آبان ۱۳۹۰ ۰۵:۰۴ ب.ظ)yaali نوشته شده توسط:  ابتدا استفاده از تغییر متغیر m=logn یعنی n=2^m در نتیجه داریم:

[tex]T(n)=T(\frac{n}{2} \sqrt{n}) n\Rightarrow T(2^{m})=T(2^{m-1} 2^{\frac{m}{2}}) 2^{m}\Rightarrow S(m)=S(m-1 \frac{m}{2}) m\Rightarrow S(m)=S(\frac{3m}{2}-1) m\approx S(m)=S(\frac{3m}{2}) m[/tex]

که با قضیه اصلی که حلش کنیم می شه(O(m که در نهایت پس از جایگزینی می شه (O(Logn

yaali جان در یکجای محاسباتت اشتباه کردی.
تابع S تنها تابع درون پرانتزه T رو تبدیل میکنه , نه مقادیر بیرونشو. برای همین وقتی که تابع T رو به S تبدیل کردی , نباید [tex]2^{m}[/tex] رو به [tex]m[/tex] تبدیل میکردی. [tex]2^{m}[/tex] را تا زمانی که میخواهی m رو به n تبدیل کنی تغییر نده.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

- rasool - پاسخ داده:

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

sasanlive عزیز

از تذکر شما متشکرم.

جوابم رو اصلاح کردم.( ارسال دوم)

ارسال:
  

sasanlive پاسخ داده:

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

(۰۴ آبان ۱۳۹۰ ۰۲:۴۲ ب.ظ)yaali نوشته شده توسط:  sasanlive عزیز

از تذکر شما متشکرم.

جوابم رو اصلاح کردم.( ارسال دوم)

خواهش میکنم دوست عزیز.
یه اشکالی به نظر میاد تو جواب آخر این سوال باشه.
برای استفاده از قضیه اصلی باید b>1 باشه(طبق کتاب clrs )اما در پایان بعد جایگذاری b=2/3 شده که کوچکتر از ۱ هست[tex]S(\frac{3m}{2})=S(\frac{m}{\frac{2}{3}})[/tex]. واسه همین فکر نکنم بشه از قضیه اصلی استفاده کرد.

فکر کنم روند حل سوال رو باید از اول تغییر بدی و به نوعی دیگه حل کنی.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

- rasool - پاسخ داده:

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

آفرین.
حق با شماست.
پیگیری می کنم.
ان شاء الله

۰
ارسال:
  

unification پاسخ داده:

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

میشه لطف کنید درباره تا بع S توضیح بدید. ممنون میشم .

ارسال:
  

Mojtaba پاسخ داده:

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

علی جان دستت درد نکنه‌، من فقط شکل کلی حل را می خواستم بفهمم و همان دیروز که پاسخت را خواندم متوجه اون قسمت که تصحیح شده بود شدم ولی متاسفانه نتوانستم بنا به دلایلی برات پیام بگذارم (آخه من سربازم خیر سرم).از لطفت خیلی ممنون.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۰
  

- rasool - پاسخ داده:

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

فکر می کنم اینطوری بشه:

چون (T(n یک تابع اکیدا صعودی است پس برای n های به اندازه کافی بزرگ داریم:

[tex]T(\frac{n}{2})<T(\frac{n}{2} \sqrt{n})<T(\frac{3n}{4})\Rightarrow T(\frac{n}{2}) n<T(\frac{n}{2} \sqrt{n}) n<T(\frac{3n}{4}) n[/tex]


حالا اگه مرتبه‌ی اون عبارت سمت راست نامساوی رو حل کنیم با قضیه اصلی می شه‌: n

پس مرتبه‌ی عبارت وسطی نامساوی‌، که مد نظر ما هم هست‌: می شه‌: (O(n



یک جورایی هم قضیه ساندویچ خودشو توی این سوال نشون می ده. فتدبر!



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) 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
  روابط بازگشتی amir_ghanati ۴ ۱,۳۰۸ ۰۴ شهریور ۱۳۹۶ ۰۳:۲۳ ق.ظ
آخرین ارسال: amir_ghanati

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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