(۱۳ مرداد ۱۳۹۳ ۰۵:۵۷ ب.ظ)Morris نوشته شده توسط:  اگر مرتبه زمانی تعداد دفعات اجرای ۱ + X = X مد نظر قرار گیرد خواهیم داشت :

$\frac{n}{2} \frac{n}{4} \frac{n}{8} \frac{n}{16} ...$
$=\frac{n}{2}(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} ...)$
$=\frac{n}{2}(\frac{1}{1-\frac{1}{2}})=\frac{n}{2}(2)=n$

بنابراین مرتبه زمانی می شود :

$\theta(n)$

(۱۳ مرداد ۱۳۹۳ ۰۶:۳۷ ب.ظ)miladcr7 نوشته شده توسط:  اره.اینجوریه:
$i=1\longrightarrow(\frac{n}{2})$
$i=2\longrightarrow(\frac{n}{4})$
$i=3\longrightarrow(\frac{n}{8})$

(۱۳ مرداد ۱۳۹۳ ۰۶:۰۹ ب.ظ)shayesteb نوشته شده توسط:  

(13 مرداد ۱۳۹۳ ۰۵:۵۷ ب.ظ)Morris نوشته شده توسط:  اگر مرتبه زمانی تعداد دفعات اجرای ۱ + X = X مد نظر قرار گیرد خواهیم داشت :

$\frac{n}{2} \frac{n}{4} \frac{n}{8} \frac{n}{16} ...$
$=\frac{n}{2}(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} ...)$
$=\frac{n}{2}(\frac{1}{1-\frac{1}{2}})=\frac{n}{2}(2)=n$

بنابراین مرتبه زمانی می شود :

$\theta(n)$

دوست عزیز خیلی ممنون از پاسختون.
چرا اینجوری حل میشه? چرا اینطوری حل نمیشه که حلقه اول n+1 بار اجرا میشه حلقه دوم (n(n+1 بار اجرا میشه و درون اونها n به توان و درنتیجه از مرتبه n به توان دو میشه .

(۱۳ مرداد ۱۳۹۳ ۰۶:۴۰ ب.ظ)shayesteb نوشته شده توسط:  

(13 مرداد ۱۳۹۳ ۰۶:۳۷ ب.ظ)miladcr7 نوشته شده توسط:  اره.اینجوریه:
$i=1\longrightarrow(\frac{n}{2})$
$i=2\longrightarrow(\frac{n}{4})$
$i=3\longrightarrow(\frac{n}{8})$

همون n/2 ( اولین اجرا) را چطوری به دست آوردین؟

(۱۳ مرداد ۱۳۹۳ ۰۶:۲۳ ب.ظ)miladcr7 نوشته شده توسط:  به این دلیل که دقت کن که توی اجرای حلقه ها هربار مقدار n یه واحد کم میشه که جز دستورات اصلی هم هستش پس مطمئنا نه حلقه اول ۱+n بار اجرا میشه نه حلقه دوم n بار

(۱۳ مرداد ۱۳۹۳ ۰۶:۴۵ ب.ظ)miladcr7 نوشته شده توسط:  برای هر عددی دوست داری یه امتحان کن ببین n/2 میشه.اگه هم خواستی بگو یه مثال برات میزنم