تالار گفتمان مانشت
سئوال از مرتبه اجرایی - نسخه‌ی قابل چاپ
سئوال از مرتبه اجرایی - vijay - 20 دى ۱۳۹۰ ۱۰:۰۳ ق.ظ

[/align]
چه طوری شده o(nبه توان ۲) ؟؟؟؟
[تصویر: 62195_1_1379096101.png]

RE: مرتبه - homa - 20 دى ۱۳۹۰ ۱۲:۲۶ ب.ظ

(۲۰ دى ۱۳۹۰ ۱۰:۰۳ ق.ظ)vijay نوشته شده توسط:  [/align]
چه طوری شده o(nبه توان ۲) ؟؟؟؟
[تصویر: 62209_1_1379096101.png]
اگه این عبارت رو بازش کنی میشه دنباله ایی به صورت زیر:
[tex](n-2) (n-4) (n-6) (n-8)...... 1[/tex]
و اگه مقدار زوج باشه مقدار آخر عبارت بالا به جای ۱ میشه صفر.
ولی مهم اینه که چون در هر بار مقدار n به اندازه‌ی ۲ کم میشه پس ما تقریبا به تعداد n/2 جمله داریم که با هم جمع میشن...یعنی n/2 تا مقدار n با هم جمع میشن منهای دنباله‌ی اعداد ۲+۴+۶+۸+....:

[tex]\frac{n}{2}*n-(2 4 6 8 ....)=\frac{n^{2}}{2}-(2 4 6 8...)[/tex]

عبارت بالا نشون میده که مرتبه میشه: [tex]O(n^{2})[/tex]

RE: مرتبه - sasanlive - 20 دى ۱۳۹۰ ۰۱:۵۲ ب.ظ

(۲۰ دى ۱۳۹۰ ۱۰:۰۳ ق.ظ)vijay نوشته شده توسط:  [/align]
چه طوری شده o(nبه توان ۲) ؟؟؟؟
[تصویر: 62221_1_1379096101.png]

چون میخوایم مرتبه رو حساب کنیم n رو زوج فرض میکنیم تا کارمون راحت شه که تو محاسبه مرتبه تاثیری خاصی نمیذاره.
این رابطه دنباله زیرو بصورت بازگشتی حساب میکنه. ۱=(T(0 فرض میکنیم.

[tex]1 2 4 6 8 10 ... n=1 [\sum_{i=1}^{\frac{n}{2}}2i]=1 [2*\frac{\frac{n}{2}(\frac{n}{2} 1)}{2}]=1 \frac{n^{2}}{4} \frac{n}{2}=O(n^{2})[/tex]

RE: مرتبه - sasanlive - 20 دى ۱۳۹۰ ۰۷:۲۰ ب.ظ

(۲۰ دى ۱۳۹۰ ۰۲:۴۶ ب.ظ)vijay نوشته شده توسط:  ممنون از جوابهاتون.
یعنی اگه داشته باشیم t(n-3)+n میشهn*n/3= O(n^2)


همینطوری نمیتونی به دنباله مقدار بدی باید جوابت بتونه مجموع مقادیر دنباله رو حساب کنه.
البته بازم مقدار مرتبه همونه.
n رو مضرب ۳ فرض میکنیم.
۱=(T(0 فرض میکنیم.

[tex]1 3 6 9 12 15 ... n=1 [\sum_{i=1}^{\frac{n}{3}}3i]=1 [3*\frac{\frac{n}{3}(\frac{n}{3} 1)}{2}]=1 \frac{n^{2}}{6} \frac{n}{2}=O(n^{2})[/tex]