طریقه محاسبه پیچیدگی زمانی

[sourcecode]

http://barnamenevis.org/images/icons/icon12.png پیچیدگی زمانی


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


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


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

[sourcecode]

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

[developing]

با سلام

بهتره قبل از این جور سوالات کتابهای مرتبط با اونها رو مطالعه کنید.
اگه مطالعه کردید و به این جواب رسیدید که باید بگم وضع شما تاسف بار است (یا شاید هم وضع دانشگاه های ما)

پیچیدگی زمانی توابع در کتابهای طراحی الگوریتم به صورت کامل بیان شده است.
حلقه برای تکرار یک سری کار نوشته می شود مثلا:
for (int i=1;i<=10; i++)
cout << i;
و مثال دوم:
for int j= 1 ; j<=20 ; j++)
cout << j;
در مثال اول دستور cout ده بار اجرا می شود.
و در مثال دوم دستور cout بیست بار اجرا می شود.
حال وقتی که دو حلقه را تو در تو بنویسیم مثل زیر:

for(int i = 1; i<=10; i++)
for(int j=1; j<20; j++)
cout << i << j;

دستور cout ، به تعداد 20*10 بار اجرا می شود.

جواب سوال شما هم می شه m*n بار

[omidshaman]

این سوالی که شما پرسیدی اگر دقیقا همینیه که گزاشتی که کلا سوال اشتباهه!(چند جور برداشت متفاوت میشه ازش کرد...)

[chris66001]

ببین اون جوابی که نوشتی از نظر منم اشتباهه (تو 3 حالت میشه بررسی کرد ایزوله و نیمه ایزوله و ایزوله نشده)

ویرایش : جواب کتاب درسته من اون "=" رو پشت n , m ندیدم

الان دو تا حلقه تو در تو هست و یک خط اجرا

در همه حالات دستور چاپ فقط و فقط یک بار اجرا میشود

دستورات حلقه هم اگر از صفر شروع شده باشد تا n

for(int i=0;i<m;i++)
پیچیدگی زمانی میشه n بار + یک بار آخر که شرط رو چک میکنه .

طبق این تفاسیر حلقه بیرونی (m) که خودش اجرا میشه و بعد از اجرای آخر میاد یک بار دیگه چک میکنه ببینه بازم ادامه بده یا نه پس میشه

[(m)+1] = m+1


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

(m)[(n)+1] = m(n+1)


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

[(m)(n)]



جواب کل هم میشه جمع عبارات بالا یعنی :

(m+1)+m(n+1)+mn

[omidshaman]

شماهم که اشتباه نوشتی...
1 دونه +1 برای همشون کم گزاشتی جواب کتاب درسته
البته به شرطی که تعداد دفعات تکرار I++و j++وi=1وj=1 رو در نظر نگیریم

[chris66001]

شماهم که اشتباه نوشتی...
1 دونه +1 برای همشون کم گزاشتی جواب کتاب درسته
البته به شرطی که تعداد دفعات تکرار I++و j++وi=1وj=1 رو در نظر نگیریم


منم که همین رو گفتم :

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

یعنی دیگه اون -1 ها رو نمیخواد بزاریم ولی این چون از یک شروع شده من یک رو کم کردم.

[omidshaman]

سوال گفته j<=n نه j<n
یعنی لازم نیست که 1 رو کم کنین.

[chris66001]

سوال گفته j<=n نه j<n
یعنی لازم نیست که 1 رو کم کنین.

بله بله کاملا درسته من اون "=" رو ندیدم . الان پست رو درست میکنم

[الناز محمدی]

خیلیییییییییییییییییییییی ییییییییییییییییییییییییی یییییی سخته

[ali_md110]

for(i=1;i<=m;i++)
برای حل این سوال از فرمول زیر استفاده میکنیم

(n-k+1)+1
n حد بالا یا شرط حلقه که در اینجا m هست
k حد پایین یا مقدار شروع بدنه حلقه هست که در اینجا مقدار 1 مربوط به i=1 هست
پس جواب خط اول میشه

(m-1+1)+1
و ساده تر میکنیم عبارت داخل پرانتر میشه:*

(m)
که این (m) در حلقه دوم و بدنه تاثیر گذار هست
و جواب نهایی حلقه اول برابر است با :**

(m+1)

مرحله دوم سراغ حلقه دومی رفته

for(j=1;j=<n;j++)
باز فرمول را پیاده میکنیم

(n-1+1)+1
جواب درون پرانتر ساده تر میشه:*
1-با +1 زده میشه و n تنها میمونه

(n)
و این (n) در بدنه تاثیر گذاره
و جواب این حلقه میشه :**

(n+1)*(m)
این (m) در واقع همون جواب داخل پرانتر حلقه اول که با یک تک ستاره * مشخص شده هست

مرحله سوم سراغ بدنه حلقه میریم
x=x+1
جوابش میشه 1 و اون (n) و (m) که با تک ستاره علامت گذاشتم هم میاد در بدنه تاثیر میگذاره و جواب بدنه میشه **

(1*m*n)

حالا( t(n
برابر هست با جمع تمام عباراتی که با دوتا ستاره علامتگذاری کردم

t(n)=(m+1)+(n+1)*(m)+(1*m*n)
اگر این عبارت رو مرتب تر بنویسیم جواب پیچیدگی بدست میاد

(m+1)+m(n+1)+(mn)

[zahra1372]

من که اخر سردرنیاوردم ! :/

[rahnema1]

اگه n بزرگتر یا مساوی m باشه جواب می شه:

n*(n+1)/2 -(n-m)*(n-m+1)/2 =
m*n - 0.5*m^2 + 0.5* m

در غیر این صورت جواب می شه

0.5 * n^2 + 0.5 * n