Métodos Computacionais 2021: Aula 6 - Exercícios resolvidos e Outros

 

Abaixo temos os exemplos apresentados em sala de aula:

Medição empírica da complexidade computacional

Referências Adicionais para essa aula:

Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein [Capítulo 3]

Introduction to the Design and Analysis of Algorithms - Anany Levitin [Capítulo 2]

Soluções da série de exercícios:

1. Como calcular a complexidade computacional das implementações recursivas da série de fibonacci?

2. Qual a complexidade computacional de um algoritmo recursivo que satisfaz a relação de recorrência?

3. Qual a complexidade computacional dessas relações de recorrência de acordo com o Teorema Mestre (master theorem)?

4. Capı́tulo 3 ”Runtime analysis of recursive algorithms“ do livro ”Introduction to
Recursive Programming“

3.1 

3.1 

3.2 

3.3 

3.4

3.5 

3.6 

3.7 

3.8 

3.10

3.11 

3.12 

3.13 

3.14

3.17 

3.18 (a)

3.18 (d)

3.18 (f)