سلام
یک تاپیک جواب دادم اگر خوب متوجه نشدید پیام بدید راهنمایی میکنم
https://barnamenevis.org/showthread.php?405543
سلام
ببینید دوست من برای محاسه پیچیدگی زمانی حلقه ها از فرمول مربوط به خودش استفاده مینکنیم
توجه کنید که حلقه های تودرتو در یکدیگر تاثیر دارند پس اول باید اسکوپ حلقه مشخص بشه
حلقه for یک بدنه داره و یک دستور
for(i=1;i<=10;i++) دستور حلقه
2*i بدنه حلقه
مثال شما
for i = 1 to n do
for j = 1 to i do
a++;
برای محاسه از فرمول زیر استفاده میکنیم
برای محاسبه پیچیدگی دستور حلقه: 1+(1+حدپایین-حد بالا)
حالا منظور از حد بالا و پایین چیه؟
منظور از حد پایین :مقدار شروع حلقه یعنی i=1 و یعنی عدد 1 هست
پس حد پایین مساوی 1
منظور از حد بالا میشه عددی که در شرط دستور حلقه i to n قرار داده شده یعنی n هست
پس حد بالا هم شد n
حالا اگر در فرمول جایگذاری کنیم پیچیدگی بدست میاد 1+ ( 1+ 1 - n)
حاصل :اگر عدد 1- و 1+ درون پرانتر را با هم ساده کنیم فقط n میمونه پس جواب دستور حلقه با براکت دورش خط میکشم[(n)+1]
اگر دقت کنیم در حلقه ها جواب درون پرانتر در بدنه حلقه ضرب میشه منظورن (n) هست که باید در بدنه ضرب بشه
چون این خلقه تو درتو هست عدد طبق قرمول پیچیدگی دستور for دوم هم بدست میاریم1+(1+حدپایین-حد بالا)
حد بالا میشه i
حد پایین میشه j=1 و در نهایت عدد 1
جاصل دستور حلقه دوم: 1+(i-1+1) و جواب ساده شده=(i)+1
گفتیم که حاصل حلقه ها در بدنه تاثیر گذار هست پس nپرانتر حلقه اولی رو هم در جواب حلقه دوم ضرب میکنیم
[(i+1)*n]
میمونه بدنه حلقه که a++ هست و در طراحی الگوریتم به عبارت ++ امتیاز 1 داده میشود
برای بدست آوردن پیچیدگی بدنه حلقه:
حالا کاری که باید بکنیم بیایم جوابهای درون پرانتر هر دو دستور حلقه (n)و (i) که بدست آوردیم در جواب بدنه حلقه ( a++) یعنی عدد 1 بدست آمده ضرب کنیم
حاصل جواب بدنه حلقه میشه
[1*n*i]
تا اینجا جوابهای دوتا حلقه for و بدنه بدست اوردیم و هر کدومشون گذاشتیم داخل براکت مشخص کردم
در نهایت باید این جوابها را با هم جمع بکنبم
T(n)=(n+1)+(i+1*n)+(1*n*i)
نقل قول: نحوه‌ی محاسبهی پیچیدگی زمانی
استادش گفته از لگاریتم و سیگما داخل هم لازمه استفاده بشه برای زمان اجرای الگوریتم بلد نیستم
قوانین ایجاد تاپیک در تالار
پاسخ با نقل قول