[ ساختمان داده ] مشکل در فرمول سیگما برای حل پیچیدگی زمانی

[ ساختمان داده ] مشکل در فرمول سیگما برای حل پیچیدگی زمانی - نسخه‌ی قابل چاپ

[ ساختمان داده ] مشکل در فرمول سیگما برای حل پیچیدگی زمانی - mehrdad66 - 01 شهریور ۱۳۹۱ ۰۹:۵۱ ب.ظ

توی کتاب پوران پژوهش فصل اول صفحه ۴ فرمول های سیگما رو اینطور نوشته
[تصویر: 120235_1_1379089981.png]

گزینه ۴ رو بکل مشکل دارم
گزینه ۵ رو کامل میدونم

اگر امکان داره کسی برام فرمول ۶ و۷ رو در حد یه راهنمایی کوچیک هم باشه توضیح بده

[ ساختمان داده ] مشکل در فرمول سیگما برای حل پیچیدگی زمانی - Jooybari - 01 شهریور ۱۳۹۱ ۱۰:۰۶ ب.ظ

سلام. ۴ که چیزی نداره. سمت چپ تساوی هست مجموع (f(m تا (f(n و سمت چپ هم هست مجموع (f(m-k+k تا (f(n-k+k که فقط یه عدد ثابت ازش کم شده و دوباره اضافه شده.. n-k+k=n و m-k+k=m.
۶ و ۷ رو با استقرا باید ثابت کرد. برای n=1 برقراره. فرض کنید برای n=k درسته و این نتیجه برسید که برای n=k+1 هم رابطه برقراره.

RE: [ ساختمان داده ] مشکل در فرمول سیگما برای حل پیچیدگی زمانی - menrabb - 01 شهریور ۱۳۹۱ ۱۰:۳۲ ب.ظ

(۰۱ شهریور ۱۳۹۱ ۰۹:۵۱ ب.ظ)mehrdad66 نوشته شده توسط: توی کتاب پوران پژوهش فصل اول صفحه ۴ فرمول های سیگما رو اینطور نوشته

گزینه ۴ رو بکل مشکل دارم
گزینه ۵ رو کامل میدونم

اگر امکان داره کسی برام فرمول ۶ و۷ رو در حد یه راهنمایی کوچیک هم باشه توضیح بده

اثبات ۵ و ۶ و ۷ با استقرا هست. بعنوان نمونه بنده ۷ رو با استقرا ثابت میکنم؛ امیدوارم یه آشنایی جزیی با استقرا داشته باشید (اثبات ۵ و ۶ راحت تر هست).
رابطه ۷ برای [tex]n=1[/tex] بوضوح برقراره (پایه استقرا). حالا فرض کنید این رابطه برای [tex]n=k[/tex] برقرار باشه(یعنی [tex]\sum_{i=1}^{k}i^3=\Big(\frac{k(k 1)}{2}\Big)^2[/tex]). ثابت می‌کنیم رابطه برای [tex]n=k 1[/tex] نیز برقراره:

[tex]\sum_{i=1}^{k 1}i^3=\sum_{i=1}^{k}i^3 (k 1)^3=(\frac{k(k 1)}{2})^2 (k 1)^3=(\frac{k 1}{2})^2\times(k^2 4(k 1))[/tex]
[tex]=(\frac{k 1}{2})^2\times(k 2)^2=(\frac{(k 1)(k 2)}{2})^2[/tex]

[ ساختمان داده ] مشکل در فرمول سیگما برای حل پیچیدگی زمانی - mehrdad66 - 02 شهریور ۱۳۹۱ ۰۵:۳۹ ق.ظ

دوستان واقعا ممنون اونم جواب دادن توی ۲۰ دقیقه بعد از ارسال سوال

رفتم درباره استقرا اطلاعاتی جمع کردم تا روش حل این سیگما رو یاد بگیرم گفتم شاید دوستانی بعد از من هم این مشکل براشون پیش بیاد ، اطلاعات جمع آوری شده رو ضمیمه کردم

[ ساختمان داده ] مشکل در فرمول سیگما برای حل پیچیدگی زمانی - hadiseh67 - 16 شهریور ۱۳۹۱ ۱۰:۴۹ ب.ظ

آیا !logn محدود به چند جمله ای است؟
nlogn=logn!
من این دوتارو نفهمیدم

RE: [ ساختمان داده ] مشکل در فرمول سیگما برای حل پیچیدگی زمانی - Mohammad-A - 17 شهریور ۱۳۹۱ ۰۲:۴۱ ب.ظ

(۱۶ شهریور ۱۳۹۱ ۱۰:۴۹ ب.ظ)hadiseh67 نوشته شده توسط: آیا !logn محدود به چند جمله ای است؟
nlogn=logn!
من این دوتارو نفهمیدم

اگر این تابع بخواد محدود به چند جمله‌ای باشه٬ باید:

[tex]\\ log(f(n))=O(logn) \\ log(n!) \approx \Theta(nlogn) \\ log(\Theta(nlogn)) \approx log(nlogn) = logn loglogn n \\ \to log(n!)=O(logn)[/tex]

[ ساختمان داده ] مشکل در فرمول سیگما برای حل پیچیدگی زمانی - mfXpert - 17 شهریور ۱۳۹۱ ۰۲:۵۶ ب.ظ

(۱۶ شهریور ۱۳۹۱ ۱۰:۴۹ ب.ظ)hadiseh67 نوشته شده توسط: آیا !logn محدود به چند جمله ای است؟
nlogn=logn!
من این دوتارو نفهمیدم

تو Instructor Manual کتاب CLRS حل شده