پیچیدگی زمانی

[sourcecode]

من دارم کتاب مقسمی رو می خونم ( مبحث پیچیدگی زمانی ) - مشکلی که دارم اینه که یه سوال داده نمی دونم چطور حل شده.
سوال اینه که برنامه زیر چند بار اجرا میشود؟


for(i=1;i<=m;i++)
for(j=1;i<=n;j++)
x=x+1;


جوابش اینه : t(n)=(m+1)+m(n+1)+mn

[BORHAN TEC]

سلام

توضیحش این میشه:
حلقه خارجی چند بار اجرا میشه؟ m+1 بار : به عبارتی دفعه آخر شرط حلقه چک میشه ولی چون شرط برقرار نیست داخل حلقه اجرا نمیشه و اون عدد 1 هم بخاطر همینه!
حلقه داخلی چند بار اجرا میشه؟ m(n+1) بار : توضیحش مثل قبلیه.
دستور x=x+1 چند بار اجرا میشه؟ mn بار : واضحه که تعداد اجرای این دستور از حاصلضرب تعداد اجرای بدنه حلقه های خارجی بدست میاد.

موفق باشید...

[sourcecode]

سلام
دوست عزیز استدلال من از این سوال اینه که حلقه i,m+1 بار اجرا میشه و حلقه j,n+1 و x=x+1; هم n بار. که میشه m+1*(n+1+n);
دوست عزیز اگه جوابم اشتباهه , کمی جزیی تر توضیح بدید تا متجه بشم.
ممنون.

[BORHAN TEC]

سلام
استدلال شما کاملاً اشتباهه!
اینجا صحبت حلقه های تو در تو است. یک حلقه تکی مثل این m+1 بار اجرا میشه(دلیل نوشتن عدد یک رو هم در پست قبل گفتم):
for (i=1;i<=m;i++)
{

}
حالا اگه دو تا حلقه تو درتو مثل این داشته باشیم، اگر حلقه خارجی را مد نظر قرار ندهیم حلقه داخلی n+1 بار اجرا می شود:
for (i=1;i<=m;i++)
{
for (j=1;j<=n;j++)
{

}
}
ولی از آنجایی که ما در اینجا یک حلقه خارجی هم داریم تعداد تکرار برابر m(n+1) می شود. خوب شاید بپرسید که چرا جواب تا به اینجا (n+1)(m+1) نشده؟ جواب: به خاطر اینکه در آخرین تکرار حلقه خارجی شرط مربوطه چک می شود و از آنجایی که شرط برقرار نیست دستورات داخل حلقه اجرا نمی شود.
در آخر هم بنا به جمله قبل دستور داخلی mn بار تکرار می شود. که از جمع کل موارد یاد شده خواهیم داشت:
t(n)=(m+1)+m(n+1)+mn

این هم یک مثال دیگه:
پیچیدگی زمانی حلقه زیر چی میشه:
for (i=1;i<=m;i++)
{
for (j=1;j<=n;j++)
{
for (b=1;b<=a;b++)
{
x = x+1;
}

}
}
جواب:

t(n)=(m+1)+m(n+1)+mn(a+1)+mna
موفق باشید...