نیاز به راهنمایی در مورد محاسبه‌ی پیچیدگی زمانی یک الگوریتم

[DumanNazeri]

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


For i = 1 to n
For j = 1 to i
For k = 1 to i
Write('*');


اگر حلقه‌ی سوم نبود بلد بودم چطوریه٬ اما با وجود حلقه‌ی سوم نمی‌دونم باید چی کار کنم.. ممنون می‌شم اگر راهنمایی‌م کنید..

[golbafan]

شما اینجا باید یک مکعب مستطیل رو فرض کنید با اضلاع n , i , i تا بتونید تجسم درستی داشته باشید از الگوریتم :تشویق:

[DumanNazeri]

می‌شه بیشتر راهنمایی‌م کنید؟! :(

[rahnema1]

می‌شه بیشتر راهنمایی‌م کنید؟! :(

1^2 + 2^2 + 3^2 + ... + n^2

[DumanNazeri]

ببینید من تا اینجا نوشتم٬ بعد این نمی‌دونم سیگما رو چطوری باید محاسبه کنم؟!


128631

[rahnema1]

شما باید یک هرم 4 وجهی تو ذهنتون تصور کنید ( مثل اهرام مصر)
از قله شروع می کنیم می آییم پایین
این هرم n تا طبقه داره
هر طبقه هم i * i هست
که جواب میشه مجموع مربع اعداد طبیعی از 1 تا n که فرمول خلاصه ترش میشه

1^2 + 2^2 + 3^2 + ... + n^2
= n(n+1)*(2*n + 1) / 6
= (n^3)/ 3 + (n^2) / 2 + n / 6

[golbafan]

سیگما i*i از i=1 تا n

در نتیچه: n*i*i میشه

[golbafan]

که جواب میشه مجموع مربع اعداد طبیعی از 1 تا n که فرمول خلاصه ترش میشه

1^2 + 2^2 + 3^2 + ... + n^2
= n(n+1)*(2*n + 1) / 6
= (n^3)/ 3 + (n^2) / 2 + n / 6


ببخشید اگر n=5 باشه چطوری میشه n/6 ??

[rahnema1]

سیگما i*i از i=1 تا n

در نتیچه: n*i*i میشه

i که ثابت نیست در قله هرم برابر با یک و همین طور زیاد میشه تا برسیم به قاعده هرم

[rahnema1]

ببخشید اگر n=5 باشه چطوری میشه n/6 ??

خودتون یکبار به صورت دستی فرمول را حساب کنید می بینید که برابرند

[golbafan]

درسته من اشتباه برداشت کردم :قهقهه:
البته شما هم باید در پرانتز میگزاشتید اینطوری

((n^3)/ 3 + (n^2) / 2 + n) / 6

[rahnema1]

درسته من اشتباه برداشت کردم :قهقهه:
البته شما هم باید در پرانتز میگزاشتید اینطوری

((n^3)/ 3 + (n^2) / 2 + n) / 6

بازم نشد . :چشمک:
پرانتز لازم نیست