من نمیدونم برا چیه که خیلی به این پیچیدگی‌ها گیر دادم.این پیچیدگی رو کسی حل کرده؟؟
T(n)=T(n/2+√n)+1
من هم جواب رو تتای n آوردم لطفا دوستان در مورد درستی حلم نظر بدن
[tex]T(n)=T(\frac{n}{2} \sqrt{n}) 1\rightarrow T(\frac{n}{\sqrt{n}})=T(\frac{n}{2\sqrt{n}} 1) 1\rightarrow H(m)=H(\frac{m}{2}) 1\rightarrow \theta (lgm)=\theta(lg\frac{n}{\sqrt{n}})=\theta(lgn)[/tex]
مرسی بچه‌ها .
من خودم این راه حل رو دارم.درسته به نظرتون؟
فکر می کنم اینطوری بشه:
چون (T(n یک تابع اکیدا صعودی است پس برای n های به اندازه کافی بزرگ داریم:
[tex]T(\frac{n}{2})<T(\frac{n}{2} \sqrt{n})<T(\frac{3n}{4})\Rightarrow T(\frac{n}{2}) 1<T(\frac{n}{2} \sqrt{n}) 1<T(\frac{3n}{4}) 1[/tex]
حالا اگه مرتبه‌ی اون عبارت سمت راست نامساوی رو حل کنیم با قضیه اصلی می شه: Logn
پس مرتبه‌ی عبارت وسطی نامساوی، که مد نظر ما هم هست: می شه
O(Lognیک جورایی هم قضیه ساندویچ خودشو توی این سوال نشون می ده. فتدبر!