(۰۵ دى ۱۳۹۳ ۰۱:۱۲ ق.ظ)abji22 نوشته شده توسط:  
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

لطفا این دوسوالو توضیح بدید

سلام

در مورد عکس اولتون:
پیچیدگی زمانی این تکه کد به اون حلقه وابسته است. کافی است تعداد تکرار این حلقه رو بدست بیارید تا پیچیدگی مشخص شود.این حلقه تا زمانی تکرار می شود که i<=n باشه. همونطور که توی حلقه مشاهده میکنید i در هر بار اجرای حلقه تغییر میکنه.پس نیاز داریم که یک جدول رسم کنیم و این تغییرات و ثبت کنیم و با استفاده از این جدول به یک جواب مشخصی برسیم. با توجه به جدول، فرض می کنیم حلقه t باراجرا شود در نهایت باید شرط حلقه در بار t ام برقرار باشد که شرط حلقه نوشته شده و با استفاده از لگاریتم گیری به جواب نهایی رسیده.

در مورد عکس دوم هم اگه این دو سیگما رو نمیفهمی زیاد مهم نیست.باید مفهومی بفهمی.ببین حلقه اول n-1 اجرا میشه و به ازای هر بار اجرای حلقه ی اول، حلقه ی دوم تعدادی تکرار میشه که این تعدادی رو باید به دست بیاریم. مثل عکس قبلی یه جدول بکش و چیزی که میگیو رو کاغذ بنویس و سعی کن ازش استفاده کنی.من برات میفرستم تا بیشتر متوجه بشی. با این کار ، هر حلقه ای رو بهت بدن میتونی به راحتی پیچیدگی زمانیشو بدست بیاری.




امیدوارم خوب توضیح داده باشم.
موفق باشی.

ممنون ولی خیلی سختن

سلام.جواب سوالتون رو که گرفتید.من قبلا یه پاسخی برای یه سوال درباره مرتبه زمانی داده بودم که توش چند تا مثال رو حل کردم.براتون میذارم امیدوارم کمکتون کنه

این مثالا رو داشته باش

این حلقه رو در نظر بگیر:

[tex]for\: (int\: i=0\: ;\: i<n\: ;\: i )[/tex]
}
[tex]x ;[/tex]
{

حالا زمان اجرا:قبول داری حلقه [tex][tex]n[/tex][/tex] بار دستور اصلی ( که همون [tex]x ;[/tex] هستش ) رو اجرا میکنه که این [tex][tex]n[/tex][/tex] بار همون تعداد اجرای شمارنده حلقه( [tex][tex]i[/tex][/tex] ) هم هست درسته؟پس زمان اجرا میشه:[tex]\theta(n)[/tex]

________________________________________________________________________________​______________________-

حالا این حلقه رو در نظر بگیر:

[tex]for\: (int\: i=0\: ;\: i<n\: ;\: i )[/tex]

}
[tex]for\: (int\: j=0\: ;\: j<n\: ;\: j )[/tex]
}
[tex]x ;[/tex]
{
{

حالا زمان اجرا:قبول داری به ازای هر [tex][tex]i[/tex][/tex] حلقه دومی به اندازه [tex][tex]n[/tex][/tex] بار اجرا میشه و متعاقبا جمله اصلی هم [tex][tex]n[/tex][/tex] بار
تکرار میشه؟
ولی یه مسئله ای که باید بهش دقت کنی اینه که به ازای هر [tex][tex]i[/tex][/tex] از حلقه اول، حلقه دومی داره به اندازه ثابتی اجرا میشه درسته؟
پس برای همین ما میتونیم بگیم که طبق اصل شمارش تعداد اجرای دستور اصلی میشه:
به ازای هر [tex][tex]i[/tex][/tex] ،جمله اصلی [tex][tex]n[/tex][/tex] بار تکرار میشه پس به ازای [tex][tex]n[/tex][/tex] بار میشه :[tex]n\ast n[/tex] که
زمان اجرا میشه :[tex]\theta(n^2)[/tex]

ببین حالا نکته اینجاست:وقتی مثلا دو حلقه تو در تو داریم زمانی میتونی تعداد اجرای حلقه بیرونی رو مستقل از حلقه دوم بگی( مثلا بگی حلقه بیرونی [tex][tex]n[/tex][/tex] بار اجرا میشه و حلقه تویی [tex]\lg(n)[/tex] بار) که به ازای هر [tex][tex]i[/tex][/tex] توی حلقه اول، حلقه دوم به تعداد [tex]\lg(n)[/tex] بار اجرا بشه که نیازی نباشه مجموع بگیری ولی اگه به ازای هر [tex][tex]i[/tex][/tex] از حلقه اولی ،حلقه دوم به تعداد متغیری اجرا شد دیگه نمیتونی زمان اجرای حلقه اول رو همینطوری مستقل بگی میدونی چرا؟مثال زیر رو داشته باش


[tex]for\: (int\: i=0\: ;\: i<n\: ;\: i )[/tex]

}
[tex]for\: (int\: j=0\: ;\: j<i\: ;\: j )[/tex]
}
[tex]x ;[/tex]
{
{


خب حالا سوال من اینه : حلقه اول [tex][tex]n[/tex][/tex] بار اجرا میشه درسته؟ ولی ایا میتونی برای محاسبه تعداد دفعات اجرای جمله اصلی بیای
از این روش بری که بگی حلقه اول [tex][tex]n[/tex][/tex] بار تکرار میشه ؟نه نمیتونی چون به ازای هر [tex][tex]i[/tex][/tex] توی حلقه اول ،حلقه دوم داره به یه مقدار متغیر اجرا میشه مثلا به ازای [tex]i=1[/tex] حلقه دوم ۱ بار و به ازای [tex]i=2[/tex] حلقه دوم ۲ بار و همینجوری.خب الان اگه برای به دست اوردن تعداد دفعه اجرای جمله اصلی بیایم بگیم حلقه اول [tex][tex]n[/tex][/tex] بار اجرا میشه اون وقت برای حلقه دوم چی بگیم؟مگه نباید توی این روش تعداد دفعه اجرای حلقه دوم رو توی تعداددفعه اجرای حلقه اول ضرب کنیم؟ولی میبینی نمیتونیم این کار رو انجام بدیم چون تعداد دفعه اجرای حلقه دوم به ازای هر بار اجرای حلقه اول متغیره اکی؟
پس مجبوریم مجموع تعداد دفعات اجرای حلقه دوم رو به ازای هر بار اجرای حلقه اول محاسبه کنیم که تو این مثال داریم:

به ازای هر [tex][tex]i[/tex][/tex] حلقه دوم از ۱ تا [tex]j[/tex] متغیره و [tex][tex]i[/tex][/tex] بار تکرار میشه.
یعنی به ازای [tex]i=1[/tex] حلقه دوم ۱ بار و به ازای [tex]i=2[/tex] حلقه دوم ۲ بار و همینجوری پس زمان اجرا:

[tex]1 2 3 ... n=\frac{n\ast(n 1)}{2}=\theta(n^2)[/tex]


________________________________________________________________________________​________________

[tex]for\: (int\: i=0\: ;\: i<=n\: ;\: i )[/tex]

}
[tex]for\: (int\: j=0\: ;\: j<=n\: ;\: j )[/tex]
}
[tex]x ;[/tex]
[tex]n--;[/tex]
{


حالا توی این مثال اگه بگی حلقه اول [tex]\lg(n)[/tex] بار داره تکرار میشه برای حلقه دوم چی میگی؟
در ضمن برای حلقه دوم هم دقت کن نمیتونیم بگیم زمان اجراش [tex]\theta(n)[/tex] چون هر بار [tex][tex]n[/tex][/tex] داره عوض میشه پس باید بیایم مجموع این تعداد اجراها رو به دست بیاریم یعنی به ازای [tex]i=1[/tex] حلقه دوم چند بار اجرا میشه و به ازای [tex]i=2[/tex] حلقه دوم چند بار تکرار میشه.ما از این روش استفاده کردیم چون به ازای هر [tex][tex]i[/tex][/tex] تو حلقه اول ،حلقه دوم به مقدار متغیری داره اجرا میشه پس باید مجموع این اجراها رو به دست بیاریم.ولی اگه بگیم حلقه اول [tex]\lg(n)[/tex] بار داره تکرار میشه اون وقت تعداد اجرای حلقه دوم رو نداریم یه بار [tex]\frac{n}{2}[/tex] بار اجرا میشه و یه بار [tex]\frac{n}{4}[/tex] و ....
وقتی هم داریم مجموع این تعداد اجراها رو به دست بیاریم در واقع زمان اجرای کل رو داریم به دست میاریم

________________________________________________________________________________​________________

[tex]for\: (int\: i=0\: ;\: i<=n\: ;\: i )[/tex]

}
[tex]for\: (int\: j=0\: ;\: j<=n\: ;\: j =i)[/tex]
}
[tex]x ;[/tex]
{
اولش برای اینکه بهتر مسئله رو درک کنیم من محدودش میکنم و فرض میکنم [tex]n=8[/tex]
خب؟؟؟؟
حالا این تریس رو داشته باش(میدونیم جمله اصلی [tex]x=x 1[/tex] هستش)

[tex]i=1[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم یکی یکی جلو میره پس جمله اصلی ۸ بار اجرا میشه
[tex]i=2[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم دوتا دوتا جلو میره پس جمله اصلی ۴ بار اجرا میشه
[tex]i=3[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم سه تا سه تا جلو میره پس جمله اصلی ۲ بار اجرا میشه
[tex]i=4[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم چهارتا چهارتا جلو میره پس جمله اصلی ۲ بار اجرا میشه
[tex]i=5[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم پنج تا پنج تا جلو میره پس جمله اصلی ۱ بار اجرا میشه
[tex]i=6[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم شش تا شش تا جلو میره پس جمله اصلی ۱ بار اجرا میشه
[tex]i=7[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم هفت تا هفت تا جلو میره پس جمله اصلی ۱ بار اجرا میشه
[tex]i=8[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم هشت تا هشت تا جلو میره پس جمله اصلی ۱ بار اجرا میشه

و الان میتونیم تعداد اجرای جمله اصلی رو اینجوری به دست بیاریم(تعداد اجراهای هر مرحله رو با هم جمع میزنیم):
[tex]8 4 2 2 1 1 1 1[/tex]
جمه بالا رو میتونیم اینجوری هم بنویسیم(حاصل تقسیم رو کف در نظر بگیر)
[tex]\frac{8}{1} \frac{8}{2} \frac{8}{3} \frac{8}{4} \frac{8}{5} \frac{8}{6} \frac{8}{7} \frac{8}{8}[/tex]
خب حالا اگه عدد رو به [tex][tex]n[/tex][/tex] تعمیم بدیم داریم:
[tex]n \frac{n}{2} \frac{n}{3} \frac{n}{4} \frac{n}{5} \frac{n}{6} ... \frac{n}{n}=n(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} ... \frac{1}{n})=\theta(nLog(n))[/tex]

امیدوارم کمکتون کنن اینا

ممنون تمرین بایدبکنم بازم سختن