O این کد چنده؟؟
(می دونم آسونه، دچاره تناقض شدم)
)for (i=1;1<=n;i++
{
for(j=1;j<=n;j++)
x++;
n=n/2;
}
ببینید حلقهی داخلی n بار اجرا میشه بعد n نصف میشه دفعا بعد حلقه داخلی ۲/n بار اجرا میشه و به همین ترتیب میشه نوشت
[tex]n \frac{n}{2} \frac{n}{4} \frac{n}{8} ...=n(1 \frac{1}{2} \frac{1}{4} \frac{1}{8} ...)=n\sum_{i=0}^{lgn}(\frac{1}{2^{i}})=2n=\bigcirc (n)[/tex]
اگه تعداد اجراها رو حساب کنیم می شه:
[tex]\large n \frac{n}{2} \frac{n}{4} ... (One Expression1)=n(1 \frac{1}{2} \frac{1}{4} ... One Expression2)\approx 2n=O(n)[/tex]
دقت بفرمایید که برای n=16 فقط تعداد ۱۶ و ۸ و ۴ بار اجرا رو داریم .