سلام میشه لطفا یکی اینو برای من توضیح بده
سلام. شرط همگرایی تو بازگشتی اینه که مخرج رابطه بازگشتی بزرگتر از یک باشه. به نظرم هیچ گزینه ای چنین تضمینی نداره. فقط در شرایطی که تمام مقادیر در گزینه ۴ بزرگتر از ۱ باشن درسته.
این تست غلطه چون گزینه صحیح نداره اما بهترین گزینه موجود گزینه ۴ است.
چون گفته مقادیر ai ها صحیح و مثبته پس وقتی k تا عدد صحیح و مثبت با هم جمع بشن مسلما حاصلش از k و ۱ بیشتره(چونk هر عددی می تونه باشه مثلا جمع سه تا عدد صحیح و مثبت حتما بزگتر مساوی ۳ است پس گزینه ۱ نادرسته)
پس گزینه های ۱ و ۳ غلطند
بررسی گزینه دو:
جمع k تا عدد صحیح و مثبتت تنها در صوریتی k می شود که تک تک اعداد ۱ باشند
که در این صورت اصلا رابطه بازگشتی نخواهد بود و حل ندارد.
چون مثلا اگر k=2 باشد رابطه ی [tex]T(n)=T(n) T(n) \theta(n)[/tex] بی معناست چون اگر مثلا T(1)=1 فرض کنیم و دوباره همین رابطه را روی آن اعمال کنیم مقدار T(1) مدام تغییر می کند
گزینه های ۱ و ۲ و ۳ به وضوح غلطندو گزینه ی ۴ گزینه ی همواره درستی نیست یعنی شرط ذکر شده در گزینه چهار کافی نیست .
توضیح گزینه چهار:
طبق قضیه مستر می دانیم که در رباطه ی [tex]T(n)=aT(\frac{n}{b}) \theta(n)[/tex] صورتی پیچیدگی این رابطه [tex]\theta(n)[/tex] خواهد بود که رشد [tex]n^{\log_b^a}[/tex] از n کمتر باشد واین در صورتی رخ می دهد که a<b باشد یعنی کسر a/b کوچکتر از ۱ باشد
پس مسلمه که در [tex]T(n)=SigmaT(\frac{n}{a_i}) \theta(n)[/tex] باید مجموع اعداد مخرج از k بیشتر باشد. اما این شرط کافی نیست یعنی صرف برقرار بودن این شرط نمی اند [tex]\theta(n)[/tex] بودن رابطه را تضمین کند
مثلا در حالتی که K=2 و [tex]a_1=a_2=3[/tex] باشد رابطه [tex]\theta(n)[/tex] است
اما در حالتی که K=2 و [tex]a_1=a_2=2[/tex] باشد رابطه [tex]\theta(n)[/tex] نیست.