![]() |
سئوال از پیچیدگی - نسخهی قابل چاپ |
سئوال از پیچیدگی - deledivouneh - 06 آبان ۱۳۹۰ ۰۵:۳۵ ب.ظ
من نمیدونم برا چیه که خیلی به این پیچیدگیها گیر دادم.این پیچیدگی رو کسی حل کرده؟؟ T(n)=T(n/2+√n)+1 |
RE: پیچیدگی - ahmadnouri - 06 آبان ۱۳۹۰ ۰۷:۴۵ ب.ظ
من هم جواب رو تتای 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] |
RE: پیچیدگی - deledivouneh - 06 آبان ۱۳۹۰ ۰۸:۲۰ ب.ظ
مرسی بچهها . من خودم این راه حل رو دارم.درسته به نظرتون؟ |
پیچیدگی - - rasool - - 06 آبان ۱۳۹۰ ۱۱:۱۷ ب.ظ
فکر می کنم اینطوری بشه: چون (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 پس مرتبهی عبارت وسطی نامساوی، که مد نظر ما هم هست: می شه ![]() یک جورایی هم قضیه ساندویچ خودشو توی این سوال نشون می ده. فتدبر! |