۰
subtitle
ارسال: #۱
سئوال از پیچیدگی
من نمیدونم برا چیه که خیلی به این پیچیدگی‌ها گیر دادم.این پیچیدگی رو کسی حل کرده؟؟
T(n)=T(n/2+√n)+1
T(n)=T(n/2+√n)+1
۰
ارسال: #۲
پیچیدگی
فکر می کنم اینطوری بشه:
چون (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
یک جورایی هم قضیه ساندویچ خودشو توی این سوال نشون می ده. فتدبر!
چون (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یک جورایی هم قضیه ساندویچ خودشو توی این سوال نشون می ده. فتدبر!
۰
ارسال: #۳
RE: پیچیدگی
من هم جواب رو تتای 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]
[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]
۰
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close