شمارش طول گام if...else

[hossein71]

سلام
نحوه شمارش طول گام دستور شرطی if...else چطوریه؟
به عنوان مثال در کد زیر بگید چطوری طول گام رو شمارش میکنن

if(x<y)
{
s=s+1;
y=s+y;
z=y+3;
}
else
{
w=w+1;
}

[سعیدسعید]

با سلام
دستور if دارای دو قسمت هست: 1- قسمتی که شرط درسته و 2- قسمتی که شرط علط هست یعنی قسمت else
حالا برای شمارش طول گام کل دستور if به صوزت زیر عمل میکنیم:

- اول طول گام هر کدام از قسمت ها را به صورت جدا از هم می شماریم. در مثال بالا طول گام قسمت if برابر 3 هست و طول گام قسمت else برابر 1 هست.
- بعد طول گام کل دستور if برابر با حداکثر این دو مقدار خواهد بود. در مثال بالا طول گام کل دستور if برابر 3 است. چون 3>1 است.

دلیل اینکه مقدار بزرگتر را انتخاب میکنیم این است که یا شرط درست هست یا غلط. پس یکی از این قسمت ها اجرا خواهد شد. ما در بدترین حالت قسمتی را انتخاب میکنیم که بیشترین زمان را مصرف کند.



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

[hossein71]

ضمن تشکر از شما
در جایی برنامه زیر گذاشته بود و گفته بود که طول گامش رو شمارش کنیم.

for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
{
int x;
}

شمارش طول گام حلقه داخلی با توجه به اینکه کوچکتر مساوی i است چگونه است؟

آیا این که من میگم درسته؟
n((n(n+1)/2)+n)

[سعیدسعید]

سلام خدمت شما
اول از همه عذر خواهی میکنم که دیر جواب میدم
هر بار که در حلفه اول i برابر 1 است حلفه دوم 1 بار اجرا می شود.
وقتی i برابر 2 است حلفه دوم 2 بار اجرا می شود (در حقیقت دستور int x دو بار اجرا می شود)
حال وقتی که i برابر n است حلقه دوم n بار اجرا می شود.
پس تعداد اجرا های حلقه دوم در هر یار عبارت است از:
1+2+3+...+n
می دانیم که حاصل عبارت فوق برابر خواهد بود با :
n(n+1)/2
حال باید تکلیف دستورهای for را مشخص کنیم:
دستور for اول (for i) به تعداد n+1 بار اجرا می شود
اما دستور for دوم (for j) وقتی که i برابر 1 است 2 بار اجرا می شود
وقتی که i برابر 2 است 3 بار اجرا می شود
وقتی که i برابر n است n+1 بار اجرا می شود
بنابراین تعداد اجرای دستور for دوم برابر زیر است:
2+3+4+...+(n+1)
حاصل عبارت فوق برابر با مقدار زیر است :
(n(n+1)/2)+n
حال برای محاسبه طول گام کل باید هر سه مفدار بدست آمده فوق را باهم جمع کنیم:
(n+1)+(n(n+1)/2)+n+(n(n+1)/2)
که در نهایت مرتبه اجرایی این مثال O(n^2) خواهد بود.
توجه کنید که در محاسبه طول گام زمان اجرای دستورها در آخر باهم جمع می شوند.