AEDII-aula02

Prévia do material em texto

1
Aula 02 – Custos de um algoritmo e 
funções de complexidade
MC3305
Algoritmos e Estruturas de Dados II
Prof. Jesús P. Mena-Chalco
jesus.mena@ufabc.edu.br
2Q-2014
2
Custo de um algoritmo e funções de 
complexidade
Introdução baseada nas aulas do Prof. Antonio A. F. Loureiro (UFMG)
3
Algoritmos
Os algoritmos fazem parte do dia-a-dia das pessoas:
Receita culinária.
Indicações de como montar um aparelho.
Instruções para o uso de medicamento.
Algoritmo: 
Sequência de passos ou ações executáveis para a obtenção 
de uma solução para um determinado tipo de problema.
4
Estrutura de dados
Estrutura de dados e algoritmos estão intimamente ligados:
Não se pode estudar ED sem considerar os algoritmos 
associados a elas;
Asssim como a escolha dos algoritmos (em geral) depende 
da representação e da ED.
5
Programas
Programar é basicamente:
Estruturar dados, e 
Construir algoritmos.
Programas:
Representam uma classe especial de algoritmos capazes de 
serem seguidos por computadores.
6
Medida do tempo de execução de um programa
Algoritmos são encontrados em todas as áreas de 
Computação.
O projeto de algoritmos é influenciado pelo estudo de seus 
comportamentos.
Os algoritmos podem ser estudados considerandos, entre 
outros, dois aspectos:
Tempo de execução.
Espaço ocupado (quantidade de memória).
7
(1) Análise de um algoritmo particular
Qual é o custo de usar um dado algoritmo para resolver 
um problema específico?
Características que devem ser investigadas:
Tempo de execução.
Quantidade de memória.
8
(2) Análise de uma classe de algoritmos 
Qual é o algoritmo de menos custo possível para resolver um 
problema particular?
Toda uma familia de algoritmos é investigada.
Procura-se identificar um que seja o melhor possível.
Colocam-se limites para a complexidade computacional dos 
algoritmos pertencentes à classe.
9
Custo de um algoritmo
Se conseguirmos determinar o menor custo possível 
para resolver problemas de uma dada classe,
então teremos a
medida da dificuldade inerente para resolver o problema.
10
Custo de um algoritmo
Se conseguirmos determinar o menor custo possível 
para resolver problemas de uma dada classe,
então teremos a
medida da dificuldade inerente para resolver o problema.
Quando um algoritmo é igual ao menor custo possível, o 
algoritmo é ótimo para a medida de custo considerada.
11
Custo de um algoritmo
Se conseguirmos determinar o menor custo possível 
para resolver problemas de uma dada classe,
então teremos a
medida da dificuldade inerente para resolver o problema.
Quando um algoritmo é igual ao menor custo possível, o 
algoritmo é ótimo para a medida de custo considerada.
Podem existir vários algoritmos para resolver um mesmo 
problema.
12
Custo de um algoritmo
Se conseguirmos determinar o menor custo possível 
para resolver problemas de uma dada classe,
então teremos a
medida da dificuldade inerente para resolver o problema.
Quando um algoritmo é igual ao menor custo possível, o 
algoritmo é ótimo para a medida de custo considerada.
Podem existir vários algoritmos para resolver um mesmo 
problema.
→ Se a mesma medida de custo é aplicada a diferentes 
algoritmos então é possível compará-los e escolher o mais 
adequado.
13
Medida de custo pela execução de um 
programa em uma plataforma real
14
(1) medida de custo pela execução de um 
programa em uma plataforma real
Tais medidas são bastante inadequadas e os resultados 
jamais devem ser generalizados:
Os resultados são dependentes do compilador que pode favorecer 
algumas construções em detrimento de outras;
Os resultados dependem de hardware;
Quanto grandes quantidades de memória são utilizadas, as medidas de 
tempo podem depender deste aspecto.
15
(1) medida de custo pela execução de um 
programa em uma plataforma real
Tais medidas são bastante inadequadas e os resultados 
jamais devem ser generalizados:
Os resultados são dependentes do compilador que pode favorecer 
algumas construções em detrimento de outras;
Os resultados dependem de hardware;
Quanto grandes quantidades de memória são utilizadas, as medidas de 
tempo podem depender deste aspecto.
Apesar disso, há argumentos a favor de se obterem medidas 
reais de tempo:
Exemplo: Quando há vários algoritmos distintos para resolver o 
problema;
Assim, são considerados tanto os custos reais das operações como os 
custos não aparentes, tais como alocação de memória, indexação, 
carga, dentre outros.
16
Medida de custo por meio de um 
modelo matemático
17
(2) medida de custo por meio de um modelo 
matemático
Usa um modelo matemático baseado em um computador 
idealizado.
Deve ser especificado o conjunto de operações e seus 
custos de execuções.
É mais usual ignorar o custo de algumas das operações e 
considerar apenas as mais significantes.
Em algoritmos de ordenação:
Consideramos o conjunto de comparações entre os elementos do 
conjunto a ser ordenado e ignoramos as operações aritméticas, de 
atribuição e manipulação de índices, caso existam.
18
Função de complexidade
19
Função de complexidade
Para medir o custo de execução de um algoritmo, é comum 
definir uma função de custo ou função de complexidade f.
20
Função de complexidade
Para medir o custo de execução de um algoritmo, é comum 
definir uma função de custo ou função de complexidade f.
Função de complexidade de tempo: 
 mede o tempo necessário para executar um algoritmo 
para um problema de tamanho n.
Função de complexidade de espaço: 
 mede a memória necessária para executar um algoritmo 
para um problema de tamanho n.
21
Função de complexidade
Para medir o custo de execução de um algoritmo, é comum 
definir uma função de custo ou função de complexidade f.
Função de complexidade de tempo: 
 mede o tempo necessário para executar um algoritmo 
para um problema de tamanho n.
Função de complexidade de espaço: 
 mede a memória necessária para executar um algoritmo 
para um problema de tamanho n.
Utilizaremos f para denotar uma função de complexidade de tempo daqui para frente.
Na realidade, f não representa tempo diretamente, mas o número de vezes que 
determinada operação (considerada relevante) é realizada.
22
Exemplo: Maior elemento
Considere o algoritmo para encontrar o maior elemento de 
um vetor de inteiros 
23
Exemplo: Maior elemento
24
Exemplo: Maior elemento
Seja f uma função de complexidade tal que é o número 
de comparações entre os elementos de A.
Logo: 
25
Exemplo: Maior elemento
26
Tamanho da entrada de dados
A medida do custo de execução de um algoritmo depende 
principalmente do tamanho de entrada dos dados.
É comum considerar o tempo de execução de um programa 
como uma função do tamanho de entrada.
27
Tamanho da entrada de dados
A medida do custo de execução de um algoritmo depende 
principalmente do tamanho de entrada dos dados.
É comum considerar o tempo de execução de um programa 
como uma função do tamanho de entrada.
→ No caso da função para determinar o máximo, o custo é 
unifome (n-1) sobre todos os problemas de tamanho n.
→ Já para um algoritmos de ordenação isso não ocorre: se 
os dados de entrada estiverem quase ordenados, então o 
algoritmo pode ter que trabalhar menos.
28
Melhor caso, pior caso e caso médio
Melhor caso:
Menor tempo de execução sobre todas as entradas de 
tamanho n.
Pior caso:
Maior tempo de execução sobre todas as entradas de 
tamanho n.
Caso médio (caso esperado):
Média dos tempos de execução de todas as entradas de 
tamanho n.
Aqui supoe-se uma distribuição de probabilidades sobre o conjunto de entradas 
de tamanho n.
29Exemplo: Busca de um registro
Considere o problema de acessar os registros de um 
arquivo (cada registro tem chave única).
O problema:
Dada uma chave qualquer, localize o registro que contenha 
esta chave
→ Considere o algoritmo de busca/pesquisa sequencial
30
Exemplo: Busca de um registro
31
Exemplo: Busca de um registro
32
Exemplo: Busca de um registro
Seja f uma função de complexidade tal que f(n) é o número 
de registros consultados. 
Melhor caso: Quando o elemento procurado é o primeiro consultado
33
Exemplo: Busca de um registro
Seja f uma função de complexidade tal que f(n) é o número 
de registros consultados. 
Melhor caso: 
Pior caso: 
Quando o elemento procurado é o primeiro consultado
Quando o elemento procurado é o último consultado
34
Exemplo: Busca de um registro
Seja f uma função de complexidade tal que f(n) é o número 
de registros consultados. 
Melhor caso: 
Pior caso: 
Caso médio:
Quando o elemento procurado é o primeiro consultado
Quando o elemento procurado é o último consultado
35
Exemplo: Busca de um registro (caso médio)
Consideremos que toda pesquisa recupera um elemento.
Para recuperar o i-ésimo elemento são necessárias 
i comparações.
36
Exemplo: Busca de um registro (caso médio)
Consideremos que toda pesquisa recupera um elemento.
Para recuperar o i-ésimo elemento são necessárias 
i comparações.
Seja a probabilidade de que o i-ésimo elemento seja 
procurado:
37
Exemplo: Busca de um registro (caso médio)
Consideremos que toda pesquisa recupera um elemento.
Para recuperar o i-ésimo elemento são necessárias 
i comparações.
Seja a probabilidade de que o i-ésimo elemento seja 
procurado:
Se cada elemento tiver a mesma probabilidade de ser escolhido que 
todos os outros, então 
Uma pesquisa examina aproximadamente metade dos elementos
38
Maior e Menor elementos
Consideremos diferentes versões para o maior e o menor 
elemento de um vetor de n inteiros, para n>=1.
A:=
0   1   2   3   4   5   6 
39
Maior e Menor elementos (versão 1)
Identifique a função de complexidade f(n) para o vetor A de n elementos:
- Melhor caso:
- Pior caso:
- Caso médio:
40
Maior e Menor elementos (versão 1)
Identifique a função de complexidade f(n) para o vetor A de n elementos:
- Melhor caso:
- Pior caso:
- Caso médio:
41
Maior e Menor elementos (versão 2)
Identifique a função de complexidade f(n) para o vetor A de n elementos:
- Melhor caso:
- Pior caso:
- Caso médio:
42
Maior e Menor elementos (versão 2)
Identifique a função de complexidade f(n) para o vetor A de n elementos:
- Melhor caso:
- Pior caso:
- Caso médio:
Quando os elementos estão em ordem crescente.
43
Maior e Menor elementos (versão 2)
Identifique a função de complexidade f(n) para o vetor A de n elementos:
- Melhor caso:
- Pior caso:
- Caso médio:
Quando os elementos estão em ordem crescente.
Quando os elementos estão em ordem decrescente.
44
Maior e Menor elementos (versão 2)
Identifique a função de complexidade f(n) para o vetor A de n elementos:
- Melhor caso:
- Pior caso:
- Caso médio:
Quando os elementos estão em ordem crescente.
Quando os elementos estão em ordem decrescente.
Quando metade das vezes max>=A[i]
45
Maior e Menor elementos (versão 3)
A:=
0   1   2   3   4   5   6 
46
Maior e Menor elementos (versão 3)
A:=
0   1   2   3   4   5   6 
7 3
0   1   2   3   4   5   6 
Min = 3
Max = 7
47
Maior e Menor elementos (versão 3)
A:=
0   1   2   3   4   5   6 
7 3
0   1   2   3   4   5   6 
60 5
0   1   2   3   4   5   6 
>
Min = 3
Max = 7
Min = 3
Max = 60
48
Maior e Menor elementos (versão 3)
A:=
0   1   2   3   4   5   6 
7 3
0   1   2   3   4   5   6 
60 5
0   1   2   3   4   5   6 
>
Min = 3
Max = 7
Min = 3
Max = 60
­1 90
0   1   2   3   4   5   6 
<
Min = -1
Max = 90
49
Maior e Menor elementos (versão 3)
A:=
0   1   2   3   4   5   6 
7 3
0   1   2   3   4   5   6 
60 5
0   1   2   3   4   5   6 
>
Min = 3
Max = 7
Min = 3
Max = 60
­1 90
0   1   2   3   4   5   6 
<
Min = -1
Max = 90
­2
0   1   2   3   4   5   6 
­2 Min = -2Max = 90
50
Maior e Menor elementos (versão 3)
A:=
0   1   2   3   4   5   6 
7 3
0   1   2   3   4   5   6 
60 5
0   1   2   3   4   5   6 
>
Min = 3
Max = 7
Min = 3
Max = 60
­1 90
0   1   2   3   4   5   6 
<
Min = -1
Max = 90
­2
0   1   2   3   4   5   6 
­2
Comparações =10
1
3
3
3
Min = -2
Max = 90
51
Versão 3
Identifique a função de
complexidade f(n) para o 
vetor A de n elementos:
- Melhor caso
- Pior caso
- Caso médio
52
Versão 3
Identifique a função de
complexidade f(n) para o 
vetor A de n elementos:
- Melhor caso
- Pior caso
- Caso médio
1 comparação
(n-2)/2comparações
(n-2)/2 + (n-2/2) comparações
53
Versão 3
Identifique a função de
complexidade f(n) para o 
vetor A de n elementos:
- Melhor caso
- Pior caso
- Caso médio
1 comparação
(n-2)/2comparações
(n-2)/2 + (n-2/2) comparações
54
Maior e Menor elementos
55
Maior e Menor elementos
0
500
1000
1500
2000
2500
maxmin1
maxmin2
maxmin3
n
f(n
)
Melhor caso
56
Funções de complexidade
Não existe algoritmo que identifique o maior e o menor 
elemento de um vetor de n elementos com uma função 
menor a:
57
Comportamento assintótico de funções
O parâmetro n fornece uma medida da dificuldade para se 
resolver o problema.
A escolha de um algoritmo não é um problema crítico para 
problemas de tamanho pequeno.
A análise de algoritmos é realizada para valores grandes 
de n.
58
Comportamento assintótico de funções
Estudaremos o comportamento assintótico das funções de 
custo (comportamento de suas funções de custo para 
valores grande de n).
O comportamento assintótico de f(n) representa o limite do 
comportamento de custo, quando n cresce.
59
Notação assintótica de funções
60
Atividade para casa: Hierarquia de funções
Estabelecer uma herarquia de funções, para um valor de n 
muito grande.
61
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 51
	Slide 52
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61