با سلام
مرتبه زمانی تکه برنامه زیر چیست
[tex]for(i=1;i\leq n ; i ) for(j=1;j\leq n; j =i) x=x 1;[/tex]
در پاسخش نوشته
[tex]n n\2 n/4 ... n/n[/tex]
ولی من اصلا نفهیمدم این دو خط چیکار می کنه سوال از صفحه ۶ ساختمان داده پوران پژوهش ورداشتم
ممنون میشم راهنماییم کنید(البته ۲ تا for زیر هم هستند من بد تایپ کردم و کلا ۳ خط زیر هم هستند)
(۱۰ مهر ۱۳۹۱ ۰۳:۱۰ ب.ظ)*angle* نوشته شده توسط: با سلام
مرتبه زمانی تکه برنامه زیر چیست
[tex]for(i=1;i\leq n ; i ) for(j=1;j\leq n; j =i) x=x 1;[/tex]
در پاسخش نوشته
[tex]n n\2 n/4 ... n/n[/tex]
ولی من اصلا نفهیمدم این دو خط چیکار می کنه سوال از صفحه ۶ ساختمان داده پوران پژوهش ورداشتم
ممنون میشم راهنماییم کنید(البته ۲ تا for زیر هم هستند من بد تایپ کردم و کلا ۳ خط زیر هم هستند)
سلام.
مثال میزنم:
به ازای i=1 هر بار مقدار گام J برابر ۱ می شه یا به عبارتی همون j++ . -------- پس به ازای i = 1 مقدار j تا n/2 میره.
به ازای i=2 هربار مقدار گام j به اضافه ۲ میشه یعنی ۱و۳و۵و۷و ... ---------- پس به ازای i = 2 مقدار j تا n/3 میره.
به ازای i=3 هربار مقدار گام j به اضافه ۳ میشه یعنی ۱و۴و۷و۱۰و ... ---------- پس به ازای i = 3 مقدار j تا n/4 میره.
...
و به همین صورت ادامه پیدا می کنه که مقدار j تا n/n بره. یعنی هربار با گام j یک واحد اضافه می شه و این باعث میشه که تعداد اجرای حلقه for تقسیم بر گام اجرا بشه.
واما در آخر n/2 + n/3 + n/4 + n/5 + ...+ n/n که اگه از n فاکتور بگیریم، میشه n* 1/2+1/3+1/4+...+1/n .
جواب اون تقسیم ها میشه logn و اگه اون n درش ضرب بشه میشه nlogn.
----------------------------------
درضمن اون جوابی که خودتون نوشتین مال سوال قبلیشه.
مرسی دوست عزیز از توضیحت.البته همون پاسخ من درست هست و به ازای i=1 مقدار j تا n جلو می رود چون n تغییری نمی کند به سوال توحه کن حرف شما وقتی درست هست که داشته باشیم
n=n-1 ولی در سوال داریم x=x+1
(۱۶ مهر ۱۳۹۱ ۱۲:۴۳ ق.ظ)*angle* نوشته شده توسط: مرسی دوست عزیز از توضیحت.البته همون پاسخ من درست هست و به ازای i=1 مقدار j تا n جلو می رود چون n تغییری نمی کند به سوال توحه کن حرف شما وقتی درست هست که داشته باشیمارسال شماره ۲ درسته. دربار اول تکرار حلقه بیرونی، شمارنده حلقه درونی یکی یکی اضافه میشه. در دور دوم اجرای حلقه بیرونی، شمارنده حلقه درونی دو تا دو تا افزایش پیدا می‌کنه و به همین ترتیب.
n=n-1 ولی در سوال داریم x=x+1
سلام دوست عزیز
همون پاسخی که شما نوشتید درسته و مرتبه زمانی (O(log n داره اگه به جوابی که خودتون نوشتید نگاه کنید کسر جواب بصورت صعودی توانی از ۲ میباشد در هر بار که i یک واحد کم میشود n/2 بار حلقه داخلی اجرا میشود
(۲۱ مهر ۱۳۹۱ ۰۴:۴۸ ب.ظ)MojtabaArab نوشته شده توسط: سلام دوست عزیز
همون پاسخی که شما نوشتید درسته و مرتبه زمانی (O(log n داره اگه به جوابی که خودتون نوشتید نگاه کنید کسر جواب بصورت صعودی توانی از ۲ میباشد در هر بار که i یک واحد کم میشود n/2 بار حلقه داخلی اجرا میشود
پاسخی که تو پست شماره اول داده شده، اشتباه است. اون پاسخ مربوط به سوال قبلی در کتاب پوران پژوهش هست.
بار اول n بار اجرا میشه.
بار دوم n/2 بار اجرا میشه.
بار سوم n/3 بار اجرا میشه.
...
بار آخر n/n بار اجرا میشه.
اگه بنویسیم : n + n/2 + n/3 + n/4 + ... + n/n میشه از یک n فاکتور گرفت و جواب میشه n * 1/2 + 1/3 + 1/4 + ... + 1/n (توجه کن که اون * n در همه ضرب شده پرانتزهاشو ننوشتم). حالا سری ۱/۲ + ۱/۳ + ۱/۴ + ... + ۱/n جوابش میشه logn که اگه اون n رو درش ضرب کنیم میشه nlogn.