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

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

ارسال:
  

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



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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال از بازگشتی Aurora ۷ ۳,۲۰۰ ۱۷ شهریور ۱۳۹۱ ۱۱:۴۰ ب.ظ
آخرین ارسال: azad_ahmadi
  (کمک در حل تست) تابع بازگشتی مربوط به برج هانوی samaneh_aftab ۴ ۵,۴۰۴ ۰۵ تیر ۱۳۹۱ ۰۱:۰۴ ب.ظ
آخرین ارسال: Parva
Lightbulb درخواست راهنمایی در حل رابطه بازگشتی - rasool - ۵۱ ۵,۴۸۰ ۲۴ بهمن ۱۳۹۰ ۰۷:۱۷ ق.ظ
آخرین ارسال: sasanlive
Lightbulb روابط بازگشتی دو متغیره - rasool - ۳ ۱,۹۷۲ ۰۶ دى ۱۳۹۰ ۰۵:۲۷ ب.ظ
آخرین ارسال: homa
  یه سوال بازگشتی از قضیه اصلی پشتکار ۱۱ ۳,۳۳۱ ۰۹ آبان ۱۳۹۰ ۱۲:۱۲ ق.ظ
آخرین ارسال: sasanlive
  جواب رابطه بازگشتی زیر چیست؟ پشتکار ۷ ۲,۲۴۳ ۲۸ مهر ۱۳۹۰ ۱۱:۲۸ ق.ظ
آخرین ارسال: si.mozhgan
  حل یه رابطه بازگشتی و نکته مهم آن پشتکار ۴ ۲,۲۴۷ ۲۵ مهر ۱۳۹۰ ۱۱:۵۲ ب.ظ
آخرین ارسال: ahmadi_development
Question سوال از روابط بازگشتی livane_abi ۱۲ ۵,۵۱۰ ۱۹ مهر ۱۳۹۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: Masoud05
  مرتبه اجرایی تابع بازگشتی khavar_1365 ۶ ۶,۹۶۳ ۱۴ مهر ۱۳۹۰ ۱۱:۰۱ ب.ظ
آخرین ارسال: summer_66

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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