با سلام
لطفا بنده را در حل این بازگشتی کمک کنید .قبلا از همکاریتون کمال تشکر را دارم .ممنون[/font][/align]
T(n)=T(n/2+√n)+n
----------------------------- ان شاء الله حل کامل و درستش رو اینجا قرار خواهم داد.
بابت جوابی که دادین خیلی ممنونم.ان شاالله هر جا هستید موفق و پیروز باشید و در کنکور هم یک رتبه عالی کسب کنید.
(۰۳ آبان ۱۳۹۰ ۰۵:۰۴ ب.ظ)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 تبدیل کنی تغییر نده.
sasanlive عزیز
از تذکر شما متشکرم.
جوابم رو اصلاح کردم.( ارسال دوم)
(۰۴ آبان ۱۳۹۰ ۰۲:۴۲ ب.ظ)yaali نوشته شده توسط: sasanlive عزیز
از تذکر شما متشکرم.
جوابم رو اصلاح کردم.( ارسال دوم)
خواهش میکنم دوست عزیز.
یه اشکالی به نظر میاد تو جواب آخر این سوال باشه.
برای استفاده از قضیه اصلی باید b>1 باشه(طبق کتاب clrs )اما در پایان بعد جایگذاری b=2/3 شده که کوچکتر از ۱ هست[tex]S(\frac{3m}{2})=S(\frac{m}{\frac{2}{3}})[/tex]. واسه همین فکر نکنم بشه از قضیه اصلی استفاده کرد.
فکر کنم روند حل سوال رو باید از اول تغییر بدی و به نوعی دیگه حل کنی.
آفرین.
حق با شماست.
پیگیری می کنم.
ان شاء الله
میشه لطف کنید درباره تا بع S توضیح بدید. ممنون میشم .
علی جان دستت درد نکنه، من فقط شکل کلی حل را می خواستم بفهمم و همان دیروز که پاسخت را خواندم متوجه اون قسمت که تصحیح شده بود شدم ولی متاسفانه نتوانستم بنا به دلایلی برات پیام بگذارم (آخه من سربازم خیر سرم).از لطفت خیلی ممنون.
فکر می کنم اینطوری بشه:
چون (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
یک جورایی هم قضیه ساندویچ خودشو توی این سوال نشون می ده. فتدبر!