مرتبه اجرای الگوریتم

[hercool]

سلام دوستان می خوام بدست اوردن مرتبه اجرای الگوریتم رو در این دو بدونم چجور حاصل میشه یعنی بیشتر مشکل من در حلقه ها است که اصل موضوع هم برای بدست اوردن بر همین حلقه هاست


x=0;
for(i=0;i<n;i++)
x++;


میزان حلقه شده n+1



x=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
x++;


میزان سطر 4 ام شده n*n


int factorial (int n)
{
int fact=1;
for(int i=2;i<=n;i++)
fact*=i;
return fact;

}


اما در اینجا مقدار حلقه n و مقدار عمل حسابی n-1 شده

ممنون میشم دوستان در رابطه با بدست اوردن مقادیر حلقه در شرایط متفاوت راهنماییم کنن که چطور به این شکل در میاد و در اخرین مثال چطور عمل حساب فکتوریل شده n-1
با تشکر

[سعیدسعید]

سلام دوست عزیز
بیا اول در مورد این حلقه که ساده هست باهم صحبت کنیم
x=0;
for(i=0;i<n;i++)
x++;
خوب ببین دستور ++x دستور بدنه حلقه است و دستور for خود حلقه. حالا همه می دونیم که تعداد اجرای بدنه حلقه برابر است با:
1+(حد پایین - حدنهایی) = تعداد اجرای دستور بدنه حلقه
در این حلقه حد نهایی برابر 1-n است (چون n علامت مساوی ندارد) و حد پایین برابر 0 است. پس با توجه به فرمول بالا میزان اجرای دستور حلقه (++x) برابر می شود با:
n-1-0+1 که این هم برابر می شود با n
اما یک نکته رو همیشه باید یادت باشه که خود دستور for همیشه یک واحد بیشتر از بدنه اجرا میشه. پس حلقه می شود n+1


حالا بریم سراغ مثال دوم:
مثال دوم دو تا حلقه تو در تو هست. اگر تعدادی حلقه تودرتو باشند زمان اجرای آنها به همدیگر ضرب می شود ولی اگر حلقه ها پشت سر هم باشند زمان اجرای انها باهم جمع می شوند

x=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
x++;

حالا با توجه به نحوه محاسبه در مثال یک دستور داخل for اول (یعنی for دوم) برابر n بار اجرا می شود حالا این دستور خودش هم یک for است. for دوم. دستور داخل for دوم هم n بار اجرا می شود. اما چون این دو حلقه تو در تو هستند پس داخلی ترین دستور یعنی ++xبرابر حاصلضرب اجرای اینها می شود که می شود : n*n


مثال سوم:

int factorial (int n)
{
int fact=1;
for(int i=2;i<=n;i++)
fact*=i;
return fact;

}

خوب حالا باز هم با اون فرمول اولمون حساب می کنیم
مقدار نهایی برابر n است چون دارای علامت مساوی است
مقدار پایین برابر 2 است
بنابراین مقدار اجرای دستور داخل حلقه یعنی fact*=i برابر می شود با:
n-2+1 که این هم برابر می شود با n-1
حالا همانطور که خدمتت عرض کردم خود دستور for یک واحد بیشتر از دستور داخلش اجرا می شود بنابراین اگر n-1 را با 1 جمع کنیم می شود n
n-1+1 برابر د می شود


امیدوارم که بهت کمکی کرده باشم :لبخندساده:

[hercool]

ممنون اما یکم میشه توضیح درباره حد پایینی و بالایی در این حلقه ها و علامت های مساوی دار بودن یا بزرگ و کوچک بودن توضیح بدی
ممنون

[hercool]

شرمنده ولی گیج شدم
ببینید درست میگم یا نه
ما می تونیم برای بدست اوردن دستور حلقه حالا برای مثال ++x هست حد بالا رو منهای حد پایین کنیم
و برای بدست اوردن زمان خود حلقه حد بالا منهای حد پایین را با عدد 1 جمع کنیم درسته؟
من مثال ها رو یکی یکی میرم جلو
در مثال یک
خود حلقه میشود n+1
دستور حلقه میشود n
مثال دوم
حلقه اول میشه n+1
حلقه دوم هم میشه n+1
که چون تو در تو هستند میشه n^2+2n+1
و خود دستور میشه n*n
مثال سوم
خود حلقه میشه n-1
ودستور حلقه میشه n-2

اگر ایراد داشت لطفا راهنمایی کنید
بعدش اگر مثلا <= یا => هر دو علامت را داشت چجوری باید حساب کرد ممنون میشم بازم راهنماییم کنید

[hercool]

دوستان ممنون میشم در این رابطه منو راهنمایی کنید
یه خورده گیج شدم
در رابطه با حلقه ها و while ها هم یه مثال بزنید ممنون میشم

[hercool]

سلام دوست عزیز
بیا اول در مورد این حلقه که ساده هست باهم صحبت کنیم
x=0;
for(i=0;i<n;i++)
x++;
خوب ببین دستور ++x دستور بدنه حلقه است و دستور for خود حلقه. حالا همه می دونیم که تعداد اجرای بدنه حلقه برابر است با:
1+(حد پایین - حدنهایی) = تعداد اجرای دستور بدنه حلقه
در این حلقه حد نهایی برابر 1-n است (چون n علامت مساوی ندارد) و حد پایین برابر 0 است. پس با توجه به فرمول بالا میزان اجرای دستور حلقه (++x) برابر می شود با:
n-1-0+1 که این هم برابر می شود با n
اما یک نکته رو همیشه باید یادت باشه که خود دستور for همیشه یک واحد بیشتر از بدنه اجرا میشه. پس حلقه می شود n+1


حالا بریم سراغ مثال دوم:
مثال دوم دو تا حلقه تو در تو هست. اگر تعدادی حلقه تودرتو باشند زمان اجرای آنها به همدیگر ضرب می شود ولی اگر حلقه ها پشت سر هم باشند زمان اجرای انها باهم جمع می شوند

x=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
x++;

حالا با توجه به نحوه محاسبه در مثال یک دستور داخل for اول (یعنی for دوم) برابر n بار اجرا می شود حالا این دستور خودش هم یک for است. for دوم. دستور داخل for دوم هم n بار اجرا می شود. اما چون این دو حلقه تو در تو هستند پس داخلی ترین دستور یعنی ++xبرابر حاصلضرب اجرای اینها می شود که می شود : n*n


مثال سوم:

int factorial (int n)
{
int fact=1;
for(int i=2;i<=n;i++)
fact*=i;
return fact;

}

خوب حالا باز هم با اون فرمول اولمون حساب می کنیم
مقدار نهایی برابر n است چون دارای علامت مساوی است
مقدار پایین برابر 2 است
بنابراین مقدار اجرای دستور داخل حلقه یعنی fact*=i برابر می شود با:
n-2+1 که این هم برابر می شود با n-1
حالا همانطور که خدمتت عرض کردم خود دستور for یک واحد بیشتر از دستور داخلش اجرا می شود بنابراین اگر n-1 را با 1 جمع کنیم می شود n
n-1+1 برابر د می شود


امیدوارم که بهت کمکی کرده باشم :لبخندساده:

چجوری حد نهایی حلقه شده n-1 ؟قسمت قرمز شده
اگر بجای 0 بود 2 چطور؟
و اگر مساوی داشت چی؟یا علامت بزرگتر کوچکتر فرق می کرد

[hercool]

من یک جا رو پیدا کردم

http://blogs.msdn.com/b/nmallick/archive/2010/03/30/how-to-calculate-time-complexity-for-a-given-algorithm.aspx

اگر میشه دوستان در رابطه با مسائلی که گفتم راهنماییم کنن در شرایط متفاوت چه اتفاقی می افته (پست بالا)