Considere a série para o número e=sumn=0^infty 1n!.
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 t.

Passo 1

Beleza, o enunciado pede pra gente olhar na série
e ;=;sumn=0^infty1n!
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é
  1. Calcular do zero (fazendo );
  2. Dividir por esse ;
  3. Somar ao total.
    Aí só contam as operações básicas.

Passo 3

Contagem:
  • Para cada mu o cálculo de divs ;=;t+1 faz ads ;=;t 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:

Exercícios relacionados