Como encontrar a complexidade temporal de um algoritmo de uma série? - algoritmo, complexidade de tempo, série

Como posso encontrar a complexidade do seguinte algoritmo que produz a soma de uma série.

série: 1+ (1 + 2) + (1 + 2 + 3) + ....... + (1 + 2 + 3 + ... + n)

algoritmo:

 for(i=1; i<=n; i++){
for(j=1; j<=i; j++){
sum = sum + j;
}
}

Respostas:

0 para resposta № 1

Encontrar complexidade do tempoVamos analisar quantas vezes o núcleo (dentro dos loops) é executado.

O loop externo é executado n vezes, então a complexidade é finalmente Em).

O loop interno é executado

• uma vez quando eu = 1
• duas vezes quando eu = 2
• ... n vezes quando i = n

Assim, o número total de vezes que ele será executado é a soma de inteiros entre 1 e n: (n * (n + 1)) / 2 = n ^ 2/2 + n / 2, que é O (n ^ 2).

Complexidade do espaço por outro lado, é mais simples neste caso. Como os requisitos de memória não dependem do tamanho da entrada, a complexidade do espaço do algoritmo acima é O (1) (ou seja, a quantidade de memória necessária é a mesma (basicamente o tamanho sum) independentemente de n, e o tempo em que o resultado se encaixa sum).

Note que para a mesma tarefa, diferentes algoritmospode ter complexidades diferentes. Como o @AxelKemper observou corretamente em seu comentário, você pode expressar a solução como um único polinômio de n, então a solução mais eficiente teria a complexidade de O (1). No entanto, o algoritmo acima não funciona dessa maneira e tem uma complexidade maior.

---

0 para resposta № 2

A soma

1+ (1 + 2) + (1 + 2 + 3) + ....... + (1 + 2 + 3 + ... + n)

é igual a

1/2 (1 + 1) + 2/2 (2 + 1) + 3/2 (3 + 1) + ....... + n / 2 (n + 1)

Isso pode ser reescrito como

1/2 (1 + 2 + ... + n) + 1/2 (1 + 4 + 9 + .... + n * n)

Isso, por sua vez, leva a

n / 4 (n + 1) + 1/12 (2n ^ 3 + 3n ^ 2 + n)

que pode ser simplificado para

n ^ 3/6 + n ^ 2/2 + n / 3

Ignorando o comprimento de palavra de n, a complexidade para avaliar este polinômio não depende de n.

Portanto, a complexidade do tempo do problema é O(1)

A complexidade do tempo do algoritmo mostrado é O(n^2) como explicado na resposta aceita.

---