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

اگه این عبارت رو بازش کنی میشه دنباله ایی به صورت زیر:
$(n-2) (n-4) (n-6) (n-8)...... 1$
و اگه مقدار زوج باشه مقدار آخر عبارت بالا به جای ۱ میشه صفر.
ولی مهم اینه که چون در هر بار مقدار n به اندازه‌ی ۲ کم میشه پس ما تقریبا به تعداد n/2 جمله داریم که با هم جمع میشن...یعنی n/2 تا مقدار n با هم جمع میشن منهای دنباله‌ی اعداد ۲+۴+۶+۸+....:

$\frac{n}{2}*n-(2 4 6 8 ....)=\frac{n^{2}}{2}-(2 4 6 8...)$

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

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

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

$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})$