Considere a série para o número
.
Obtenha a complexidade do seu algoritmo fornecendo o número de adições (incluindo subtrações), multiplicações e divisões em função do número
.
Obtenha a complexidade do seu algoritmo fornecendo o número de adições (incluindo subtrações), multiplicações e divisões em função do número
Passo 1
Beleza, o enunciado pede pra gente olhar na série
e assumir que a gente vai somar só até um termo
. A matéria é Análise de Algoritmos (complexidade) e o que vamos precisar é contar quantas operações de adição, multiplicação e divisão aparecem quando calculamos cada termo
“na unha” e adicionamos tudo.
Passo 2
Vamos usar o método ingênuo: para cada
de 0 até
- Calcular
do zero (fazendo ); - Dividir
por esse ; - Somar ao total.
Aí só contam as operações básicas.
Passo 3
Contagem:
- Para cada
o cálculo de faz multiplicações. Como não precisa, somamos de a : - Para todo
a gente faz uma divisão , logo - Para somar cada termo ao acumulador, a gente faz uma adição a partir do segundo termo (ou seja,
adições):
Resposta
Número de adições:
Número de multiplicações:
Número de divisões:
Número de multiplicações:
Número de divisões: