Какова сложность времени выполнения следующего кода?

Question

void foo(int n){ 
    int i = 1, sum = 1; 
    while (sum <= n) { 
    i++; 
    sum+=i; 
    } 
} 

Что я чувствую, цикл прекратится, только если сумма станет больше аргумента n. И Sum на j-й итерации: S(j) = S(j-1) + j

S(1) = S(0) + 1 
S(2) = S(1) + 2 
S(3) = S(2) + 3 
... 
S(n) = S(n-1) + n 

Как я должен идти дальше? Я застрял в этом повторении.

Петля прекращается, когда 1 + 2 + 3 + ... + j раз становится больше n. Но я не уверен, если все в порядке.

Answer 1

Вы почти сделали это. Последнее, что вы должны отметить, это то, что 1 + 2 + 3 + ... + j является (1 + j) * j/2, или O(j^2). Это известная формула математики (арифметическая прогрессия).

Answer 2

Он сломается после k итераций при

1 + 2 + .... + k > n 

k*(k+1)/2 > n 

k*k + k - 2*n >0 

k придет k = (-1 + sqrt(1+8n))/2 (отделяемого отрицательное значение)

Следовательно, сложность Время sqrt(n).

Answer 3

Классический способ доказать это, чтобы написать серию дважды, в обоих заказов, то есть:

S(n) = 1 + 2 +  3 + ...+ n-2 + n-1 + n 
S(n) = n + (n-1) + (n-2) + ...+ 3 + 2 + 1 

Если суммировать эти почленно вы получаете

2S(n)= n+1 + n+1 + n+1 + ... + n+1 

С n точки

поэтому

S(n) = n*(n+1)/2 

(Результат, предположительно обнаруженный Гаусс как школьником)

Из этого следует, что он выполняет итерации O (sqrt (n)).