مرتبه اجرایی یه قطعه کد

[shecarchi]

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


for(int i=0 ; i< N-i ; ++i)
for(int j=0 ; j<N-j ; ++j)
{
//process a
}

[m.soleimani]

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


for(int i=0 ; i< N-i ; ++i)
for(int j=0 ; j<N-j ; ++j)
{
//process a
}

با توجه به این حلقه تو در تو که شما داری حلقه اول شما به تعداد i کمتر از N که خودت براش مشخص می‌کنی تکرار می‌شه و در هر بار انجامش حلقه دوم به تعداد j کمتر از N که باز خودت براش مشخص می‌کنی اون پروسس را اجرا می‌کنه پس تعداد N اولت ضرب در تعداد N دومت البته منهای j , i فراموش نشه می‌شه نتیجه شما موفق باشید./

[shecarchi]

یعنی میشه n-i * n-j ؟

[مسعود اقدسی فام]

حلقه بیرونی به مقدار N / 2 بار، اجرا می‌شه. چون در هر اجرا هم مقدار i یکی افزایش پیدا می‌کنه، هم از انتهای محدوده یکی کم می‌شه. عملا می‌شه فرض کرد فاصله صفر تا N با گام دو پیمایش می‌شه.
همینطور در مورد حلقه داخلی هم این مساله درسته.
با توجه به این که این دو حلقه تو در تو هستن، تعداد کل تکرارها ( N / 2 ) * ( N / 2 ) می‌شه که از مرتبه ( O( N ^ 2 حواهد بود.