سلام
بچه ها میشه لطفا بگید مرتبه زمانی این الگوریتم را چطوری باید محاسبه کنم؟( ایتن سوال صفحه ۶ کتاب ساختمان پوران)
(++for (i=1; i<=n; i
(++for (j=1; j<=n; j
}
;x=x+1
;n=n-1
{
اگر مرتبه زمانی تعداد دفعات اجرای ۱ + X = X مد نظر قرار گیرد خواهیم داشت :
[tex]\frac{n}{2} \frac{n}{4} \frac{n}{8} \frac{n}{16} ...[/tex]
[tex]=\frac{n}{2}(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} ...)[/tex]
[tex]=\frac{n}{2}(\frac{1}{1-\frac{1}{2}})=\frac{n}{2}(2)=n[/tex]
بنابراین مرتبه زمانی می شود :
[tex]\theta(n)[/tex]
(۱۳ مرداد ۱۳۹۳ ۰۵:۵۷ ب.ظ)Morris نوشته شده توسط: اگر مرتبه زمانی تعداد دفعات اجرای ۱ + X = X مد نظر قرار گیرد خواهیم داشت :
[tex]\frac{n}{2} \frac{n}{4} \frac{n}{8} \frac{n}{16} ...[/tex]
[tex]=\frac{n}{2}(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} ...)[/tex]
[tex]=\frac{n}{2}(\frac{1}{1-\frac{1}{2}})=\frac{n}{2}(2)=n[/tex]
بنابراین مرتبه زمانی می شود :
[tex]\theta(n)[/tex]
دوست عزیز خیلی ممنون از پاسختون.
چرا اینجوری حل میشه? چرا اینطوری حل نمیشه که حلقه اول n+1 بار اجرا میشه حلقه دوم (n(n+1 بار اجرا میشه و درون اونها n به توان و درنتیجه از مرتبه n به توان دو میشه .
(۱۳ مرداد ۱۳۹۳ ۰۶:۰۹ ب.ظ)shayesteb نوشته شده توسط:(13 مرداد ۱۳۹۳ ۰۵:۵۷ ب.ظ)Morris نوشته شده توسط: اگر مرتبه زمانی تعداد دفعات اجرای ۱ + X = X مد نظر قرار گیرد خواهیم داشت :
[tex]\frac{n}{2} \frac{n}{4} \frac{n}{8} \frac{n}{16} ...[/tex]
[tex]=\frac{n}{2}(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} ...)[/tex]
[tex]=\frac{n}{2}(\frac{1}{1-\frac{1}{2}})=\frac{n}{2}(2)=n[/tex]
بنابراین مرتبه زمانی می شود :
[tex]\theta(n)[/tex]
دوست عزیز خیلی ممنون از پاسختون.
چرا اینجوری حل میشه? چرا اینطوری حل نمیشه که حلقه اول n+1 بار اجرا میشه حلقه دوم (n(n+1 بار اجرا میشه و درون اونها n به توان و درنتیجه از مرتبه n به توان دو میشه .
چون با هربار اجرای حلقه ی دوم، مقدار n داره یه واحد کم میشه، و این هربار توی جفت حلقه ها اثر میزاره، این مدل سوالا که شرط خود حلقه داره تغییر میکنه، حتما باید trace بشن، روشی که میگی برای سوالاییه که هم حلقه ها وابسته نباشن و هم شرط دچار تغییر نشه
به این دلیل که دقت کن که توی اجرای حلقه ها هربار مقدار n یه واحد کم میشه که جز دستورات اصلی هم هستش پس مطمئنا نه حلقه اول ۱+n بار اجرا میشه نه حلقه دوم n بار
(۱۳ مرداد ۱۳۹۳ ۰۶:۲۳ ب.ظ)miladcr7 نوشته شده توسط: به این دلیل که دقت کن که توی اجرای حلقه ها هربار مقدار n یه واحد کم میشه که جز دستورات اصلی هم هستش پس مطمئنا نه حلقه اول ۱+n بار اجرا میشه نه حلقه دوم n بار
دوستای عزیز ممنون از توضیحایی که دادین . بله کاملا درسته. فقط میشه بگید چطوری برای i=1 جمله x=x+1 حلقه n/2 بار اجرا میشه ؟
اره.اینجوریه:
[tex]i=1\longrightarrow(\frac{n}{2})[/tex]
[tex]i=2\longrightarrow(\frac{n}{4})[/tex]
[tex]i=3\longrightarrow(\frac{n}{8})[/tex]
.
.
.
.
همینجوری ادامه داره...
(۱۳ مرداد ۱۳۹۳ ۰۶:۳۷ ب.ظ)miladcr7 نوشته شده توسط: اره.اینجوریه:
[tex]i=1\longrightarrow(\frac{n}{2})[/tex]
[tex]i=2\longrightarrow(\frac{n}{4})[/tex]
[tex]i=3\longrightarrow(\frac{n}{8})[/tex]
همون n/2 ( اولین اجرا) را چطوری به دست آوردین؟
برای هر عددی دوست داری یه امتحان کن ببین n/2 میشه.اگه هم خواستی بگو یه مثال برات میزنم
(۱۳ مرداد ۱۳۹۳ ۰۶:۴۰ ب.ظ)shayesteb نوشته شده توسط:(13 مرداد ۱۳۹۳ ۰۶:۳۷ ب.ظ)miladcr7 نوشته شده توسط: اره.اینجوریه:
[tex]i=1\longrightarrow(\frac{n}{2})[/tex]
[tex]i=2\longrightarrow(\frac{n}{4})[/tex]
[tex]i=3\longrightarrow(\frac{n}{8})[/tex]
همون n/2 ( اولین اجرا) را چطوری به دست آوردین؟
برای اینکه وقتی هربار یه واحد از n کم بشه، یعنی شرط وسطیه حلقه فقط تا نصف جلو میره
(۱۳ مرداد ۱۳۹۳ ۰۶:۴۵ ب.ظ)miladcr7 نوشته شده توسط: برای هر عددی دوست داری یه امتحان کن ببین n/2 میشه.اگه هم خواستی بگو یه مثال برات میزنم
از همگی ممنونم . حل شد
