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

اگه این عبارت رو بازش کنی میشه دنباله ایی به صورت زیر:
[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]

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

چون میخوایم مرتبه رو حساب کنیم 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]