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

پیچیدگی زمانی - nana0 - 06 شهریور ۱۳۹۱ ۱۱:۲۹ ب.ظ

سلام
چرا به این سوال وقتی به n عدد میدم جواب میشه n(n+1)/2 ولی با سیگما حل میکن ماین میشه جوابش؟؟؟//Huh

[attachment=6314]
[attachment=6316]

پیچیدگی زمانی - mfXpert - 06 شهریور ۱۳۹۱ ۱۱:۳۶ ب.ظ

سیگما رو غلط حل کردید. جواب همون n(n+1)/2 میشه

RE: پیچیدگی زمانی - zeinab - 07 شهریور ۱۳۹۱ ۱۲:۰۵ ق.ظ

(۰۶ شهریور ۱۳۹۱ ۱۱:۳۶ ب.ظ)mfXpert نوشته شده توسط:  سیگما رو غلط حل کردید. جواب همون n(n+1)/2 میشه

آره! تو جمع و تفریق آخری اشتباه کردی!

RE: پیچیدگی زمانی - farhadk - 07 شهریور ۱۳۹۱ ۱۲:۴۵ ق.ظ

(۰۶ شهریور ۱۳۹۱ ۱۱:۲۹ ب.ظ)nana0 نوشته شده توسط:  سلام
چرا به این سوال وقتی به n عدد میدم جواب میشه n(n+1)/2 ولی با سیگما حل میکن ماین میشه جوابش؟؟؟//Huh

[tex]\sum_{k=0}^{n-1}\sum_{i=1}^{n-k}1=\sum_{k=0}^{n-1}(n-k)[/tex]


مقدار در k=0 را جدا حساب میکنیم و به بقیه اضافه میکنیم:

[tex]\sum_{k=0}^{n-1}(n-k)=n \sum_{k=1}^{n-1}(n-k)=n n\left ( n-1 \right )-\frac{\left ( n-1 \right )n}{2}=\frac{2n 2n^{2}-2n-n^{2} n}{2}=\frac{n^{2} n}{2}[/tex]

پیچیدگی زمانی - nana0 - 07 شهریور ۱۳۹۱ ۰۳:۲۸ ب.ظ

مرسی دوستاااان