سلام.قبلش بگم از اوردن این مثالا اینجا اصلا قصدم خدایی نکرده توهین به معلوماتتون نیست ولی به نظرم میتونه دید خوبی راجب حل مرتبه اجرایی الگوریتم ها باشه.


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

[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]

---

حالا سوال اصلی:
ببین زمان اجرای حلقه دوم و سوم [tex]\lg(n)[/tex] نمیشه چون به ازای هر [tex]j[/tex] توی حلقه دوم مقدار [tex]k[/tex] توی حلقه سوم فرق داره درسته؟
یعنی وقتی j مقدارش ۱ باشه حلقه سوم ۱ بار اجرا میشه و وقتی [tex]j=2[/tex] باشه حلقه سوم ۲ بار اجرا میشه و وقتی [tex]j=4[/tex] باشه حلقه سوم ۴ بار اجرا میشه پس لگاریتمی تغییر نمیکنه.
حالا این تریس رو داشته باش:

[tex]j=1\longrightarrow1[/tex]

[tex]j=2\longrightarrow2[/tex]

[tex]j=4\longrightarrow4[/tex]

[tex]j=8\longrightarrow8[/tex]

و همینطوری ادامه بده.حال قبول داری [tex]j[/tex] داره به صورت [tex]۲p[/tex] تغییر میکنه.[tex]p[/tex] از صفر شروع میشه.حالا این اجرا تا چه وقتی ادامه پیدا میکنه؟
تا وقتی که [tex]۲p<n[/tex] درسته؟یعنی وقتی که [tex]۲p 1>n[/tex] دیگه حلقه اجرا نمیشه.درسته؟
پس ما میتونیم یه تقریب بزنیم به این صورت که:[tex]۲p≅n[/tex] درست؟
حالا مجموع زمان اجراها رو محاسبه میکنیم:
[tex]۲^۰ ۲^۱ ۲^۲ ۲^۳ ... ۲^p=\frac{2^{p 1}-1}{2-1}=2^{p 1}-1\cong n=\theta(n)[/tex]

حلقه اول هم که [tex]\lg(n)[/tex] پس زمان اجرای کل:[tex]n.\lg(n)[/tex]


ببخشید خیلی طولانی شد