Aula1-Recursividade e Complexidade 2

Prévia do material em texto

• ESTRUTURAS DE DADOS E 
PROGRAMAÇÃO 
 
 
 
• Prof: Ekler Paulino de Mattos 
• ekler.mattos@gmail.com 
• CPCX/UFMS 
 
(c) Ekler Paulino de Mattos 1 
Agenda: 
 
Algoritmos Recursivos; 
 
Complexidade de Algoritmos; 
 
(c) Ekler Paulino de Mattos 2 
Algoritmos e Estruturas de Dados 
 Algoritmo: 
 Processo sistemático para a resolução de um problema [1]. 
 
Estruturas de Dados: 
 Na Ciência da Computação, uma estrutura de dados é um 
modo particular de armazenamento e organização de dados em 
um computador de modo que possam ser usados 
eficientemente [2][3]. 
 
 
(c) Ekler Paulino de Mattos 3 
Algoritmos e Estruturas de Dados 
Conceitos: 
 Representação do modelo matemático em uma estrutura de 
dados. 
 
 Estruturas diferem uma das outras pela disposição ou 
manipulação de seus dados. A disposição dos dados em uma 
estrutura obedece a condições preestabelecidas e caracteriza 
a estrutura. 
 
 Na resolução de um problema: A escolha correta da estrutura 
depende diretamente do conhecimento de algoritmos para 
manipular a estrutura de maneira eficiente. 
 
 (c) Ekler Paulino de Mattos 4 
Algoritmos e Estruturas de Dados 
Atividades: 
 
 Desenvolva um algoritmo que calcule o Fatorial. 
 
 
 Desenvolva um algoritmo que calcule a sequência de Fibonacci. 
 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … 
 
 
(c) Ekler Paulino de Mattos 5 
Algoritmos e Estruturas de Dados 
Cálculo da sequência de Fibonacci: 
 
(c) Ekler Paulino de Mattos 6 
Recursividade 
 
 Procedimento que contém, em sua descrição, uma ou 
mais chamadas a si mesmo (chamadas recursivas). 
 
 
 Um procedimento não recursivo ou não possui uma 
chamada a externa. 
 
 
 Entretanto, um procedimento não recursivo possui 
todas as suas chamadas são externas. 
 
 (c) Ekler Paulino de Mattos 7 
Recursividade 
 Vantagens: 
 São mais concisos do que um procedimento não recursivo 
correspondente. 
 
 Relação direta entre um procedimento recursivo e uma prova 
por indução matemática. 
Simplicidade na verficação da correção. 
 
 Desvantagens: 
 Na prática, um algoritmo não recursivo equivalente pode ser 
mais eficaz. 
 
 
(c) Ekler Paulino de Mattos 8 
Recursividade 
 
 
 
• Exemplo: Cálculo do Fatorial. 
(c) Ekler Paulino de Mattos 9 
Cálculo do Fatorial 
 
 
 
 
(c) Ekler Paulino de Mattos 10 
Recursividade: Cálculo do Fatorial 
 
 
 
 
(c) Ekler Paulino de Mattos 11 
Recursividade: Cálculo do Fatorial 
 
 
 
 
(c) Ekler Paulino de Mattos 12 
Recursividade: Cálculo do Fatorial 
 
 
 
 
(c) Ekler Paulino de Mattos 13 
Exemplo: Divisão por dois 
• Exemplo de uma função recursiva que faça a divisão de um número real 
por dois até atingir o valor 0,125. Impressão das iterações. 
 
 
(c) Ekler Paulino de Mattos 14 
L1 - Lista de Exercícios 1 
1. Implemente uma função recursiva que calcule uma Progressão Geométrica (PG) de 
razão q = 2 até chegar a 2048. Uma PG de razão q = 2; (1,2,4,8,16,32,64...). 
 
2. Implemente uma função recursiva que calcule uma PG de razão q = 1/2 até chegar a 
1/64. (1,1/2,1/4,1/8,1/16,... 1/64). 
 
3. Crie uma função recursiva que faça o incremento de dois de um número inteiro até 
que chegue ao valor 500. Imprima na tela a quantidade de interações. 
 
4. Defina uma função recursiva que exiba, em ordem crescente, os números do 
intervalo [1, n] na saída padrão. 
 
5. Defina uma função recursiva que faça a contagem regressiva a parti de qualquer 
valor parametrizado. 
 
6. Defina uma função recursiva ex2, sendo em que e = 2,7128. 
 
7. Implemente um algoritmo recursivo que define a série de Fibonacci. 
 
(c) Ekler Paulino de Mattos 15 
Complexidade de Algoritmos 
• Característica do algoritmo é o seu tempo de 
execução: 
 
 Possibilidade de determinar através de métodos 
empíricos; 
 
Possibilidade de dar uma ordem de grandeza - 
Mensurar; 
 
Objetivo: obter uma expressão matemática que 
traduza o tempo de execução de um algoritmo em 
geral. 
Não é simples. 
 
 
 
(c) Ekler Paulino de Mattos 16 
Complexidade de Algoritmos 
 
• É necessário definir a variável em relação à qual a 
expressão matemática avaliará o tempo de execução. 
 
• Solução: 
– Um algoritmo opera a partir da entrada para 
produzir uma saída, dentro de um tempo que 
deseja avaliar: 
 
– Exprimir o tempo de execução em função da 
entrada. 
 
 (c) Ekler Paulino de Mattos 17 
Complexidade de Algoritmos 
 
• O processo de execução de um algoritmo pode ser 
dividido pelos seguintes passos: 
 
1. execução de um número fixo de operações básicas 
em que os tempos de execução são considerados 
constantes. 
 
2. A operação básica de maior frequência é 
conhecida como operação dominante. 
 
 
(c) Ekler Paulino de Mattos 18 
Complexidade de Algoritmos 
 
 
 Algoritmos do livro: 
 Algoritmo 1.1; 
 Algoritmo 1.5; 
 Algoritmo 1.6 
 
 
 
(c) Ekler Paulino de Mattos 19 
Complexidade de Algoritmos 
 
• Existem níveis de complexidade: 
– Complexidade de pior, melhor e médio caso: 
• Pior caso: máximo de passos são efetuadas para uma entrada de dados; 
 
• Melhor caso: mínimo de passos são efetuadas para uma entrada de 
dados; 
 
• Médio caso: existe uma probabilidade de um passo ser executado; 
 
 
• Complexidade de tempo de pior caso corresponde ao número 
de passos que o algoritmo efetua no seu pior caso de execução, 
isto é, para a entrada mais desfavorável. 
 
• Mais importante das três mencionadas. 
 
 
 
(c) Ekler Paulino de Mattos 20 
Complexidade de Algoritmos 
(c) Ekler Paulino de Mattos 21 
A Notação O 
 
 Para algoritmos recursivos: 
1. A - Calcular o número total de chamadas ao procedimento 
recursivo. 
2. B - Calcular a complexidade da execução correspondente a 
uma única chamada, sem que se considerem as chamadas 
recursivas encontradas. 
 
 A complexidade total será: o produto do número de chamadas 
pela complexidade da computação de uma chamada isolada. 
 CompTotal = A * B; 
 
 Qual é a complexidade do fatorial recursivo (algoritmo 1.2)? 
 
 
 
(c) Ekler Paulino de Mattos 22 
A Notação O 
Complexidade do Fatorial Recursivo: 
 
 Para calcular o fatorial de n > 0, de forma recursiva, o algoritmo 
1.2 efetua u total de n chamadas ao procedimento fat. 
 
 A complexidade da computação correspondente a uma chamada 
é constante,isto é, O(1). 
 
 De fato, para n > 1, apenas um produto é efetuado e, quando n 
<= 1, apenas uma atribuição é executada. Logo, a complexidade 
final do algoritmo é O(n). 
 
 
(c) Ekler Paulino de Mattos 23 
Algoritmos e Estruturas de Dados 
 
• Referências Bibliográficas: 
 
• [1] Markenzon L.; Szwarcfiter J. L.; Estruturas de Dados e Seus Algoritmos, Rio de 
Janeiro: LTC-Livros Técnicos e Científicos Ed., 1994. Editora ETC. 
 
• [2] Paul E. Black (ed.), Data structure. Dictionary of Algorithms and Data Structures. 
U.S. National Institute of Standards and Technology, 2004. 
 
• [3] Data structure. Encyclopædia Britannica, 2009. 
 
 
 (c) Ekler Paulino de Mattos 24