30 مهر 1390, 01:26 ب.ظ
30 مهر 1390, 03:26 ب.ظ
ببینید حلقهی داخلی 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]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]
01 آبان 1390, 10:57 ب.ظ
اگه تعداد اجراها رو حساب کنیم می شه:
[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 فقط تعداد 16 و 8 و 4 بار اجرا رو داریم .
[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 فقط تعداد 16 و 8 و 4 بار اجرا رو داریم .