n/3
∑(n-3i+2) = n(n+1)/6
i=1
这个式子是怎么得出的呢?
没看懂啊,求指教下.
一个时间复杂度的式子,也不知道去哪问....
n/3
∑(n-3i+2) = n(n+1)/6
i=1
这个式子是怎么得出的呢?
没看懂啊,求指教下.
一个时间复杂度的式子,也不知道去哪问....
n/3
∑(n-3i+2) = (n-3*1+2)+(n-3*2+2)+(n-3*3+2)+..+(n-3*n/3+2)
i=1
=n*n/3 -3*(1+2+3+..+n/3)+2*n/3
=n*n/3 - 3*(1+n/3)*n/3/2 + 2n/3
=n*n/3 - (n*n + 3n)/6 + 2n/3
=(2n*n - n*n - 3n - 4n)/6
=n(n+1)/6