روش اول: سیگما
∑ni=1∑nj=i∑j−1r=11
چرا کران بالای r برابر شده با j-1? چون r با k که مقدار j رو گرفته مقایسه میشه و چون تا زمانی که r<k مقایسه میشه پس به ازای r=j-1=k-1 هم درست هست و اجرا میشه.
چرا یک؟ چون مرتبه ی اجرای x++ برابر هست با ۱
ادامه ش:
∑ni=1∑nj=i∑j−1r=11=∑ni=1∑nj=i(j−1)
مقدار داخلی ترین سیگما میشه از یک تا j-1 تا اجرا با هزینه ی ۱ که میشه j-1 تا اجرا با هزینه ی ۱
∑ni=1∑nj=i∑j−1r=11=∑ni=1∑nj=i(j−1)=∑ni=1[(i−1)+(i+1−1)+(i+2−1)+(i+3−1)+...+(n−1)]=∑ni=1[(i−1)+(i)+(i+2)+...+(n−1)]=∑ni=1[n−1−(i−1)+1][n−1+(i−1)]2=∑ni=1[n−i+1][n+i−2]2
∑ni=1[n−i+1][n+i−2]2=∑ni=1[n2+ni−2n−ni−i2−2+n+i+2i]2=12∑ni=1[n2−i2−n+3i−2]=[12∑n2−n−2−∑i2+3∑i]=12[n×(n2−n−2)−n(n+1)(2n+1)2+3n(n+1)2]
12[n3−n2−2n−2n36−3n26−n6+3n22+3n2]=112[6n3−6n2−12n−2n3−3n2−n+9n2+9n]=112[4n3−4n]=(n3−n)3
روش دوم:
سوال تبدیل میشه به:
for i=1 to n
for j=i to n
for r=1 to j-1
i=1
اصلا اجرا نمیشه چون شرط whileبرقرار نیست.
i=2
یک بار اجرا میشه
i=3
j=3>1 پس دو بار اجرا یعنی از ۱ تا ۲
j=4>1 پس سه بار اجرا یعنی از ۱ تا ۳
.
.
j=n>1 پس n-1 بار اجرا از ۱ تا n-1
برای i=1 تعداد ۱+۲+۳+…+ n-1 بار اجرا میشه که برابر هست با n(n-1)/2 بار
برای i=2 تعداد ۱+۲+۳+…+n-1 بار
برای i=3 تعداد ۲+۳+…+n-1 بار
.
.
.
یکی کم میشه از سمت پایین دنباله ی جمع.
مجموع اینا ∑nk=012[(n−k)⋅(n−1+k)]=12∑(n2−n+nk−kn+k−k2)=
.
12∑nk=0(n2−n+k−k2)=12[n3−n2]+12∑nk=0k+12∑k2=(n3−n2)2+(n+1)(n+2)4−(n+1)(2n+3)(n+2)12=[6n3−6n2+3n2+9n+9n2−12n−n−3n2−2n3]12=[4n3−4n]12=[n3−n]3
