Смотрите решение ниже, я хотел бы получить конструктивный отзыв.
каково время работы в O (n) ниже.
int a = 0;
int k = n*n*n; //n^3
while(k > 1)
{
for (int j=0; j<k; j++) //runs from 0->k
{ a--; }
k = k/2; //divides by 2 each iteration
}
каждый раз, когда цикл for выполняется, он дает константу x k.
= 0xn^3 + 1x (n^3/2) + 2x(n^3/4) +...+ nx(n^3/2^n)
= n^3 (0 + 1/2 + 2/4 +...+ n/2^n) ‹- кто-нибудь знает, как я могу упростить это еще больше?
Изменить: я предполагаю, что мы каким-то образом будем использовать арифметический ряд....
