455365337

ED_0202 Análise de Algoritmos :
Tempo de Processamento,
Consumo de Memória,
Eficiência de Algoritmos,
Notação Assintótica.

Algorítmo

- Método para resolução de Problemas

Estrutura de Dados - Método para Armazenar Dados

Algoritmos + Estrutura de Dados
=
Programa de Computador (Software)

Algoritmos + Estrutura de Dados

Otimizados

Tempo de Processamento Menor

Otimizadas

Menor Consumo de Memória

Algoritmos + Estrutura de Dados

Otimizados

Tempo de Processamento Menor

Otimizadas

Menor Consumo de Memória

Problema resolvido de forma mais Eficiente

Tempo de Processamento

Dependia da velocidade que se girava esta Manivela

Engenho Analítico - Charles Babbage 1864

Quantas Instruções são executadas para uma Variável de Entrada N ? int contador= 0; for (int i = 0; i < N; i++) contador++; Operação

Frequência

Declaração de Variáveis

2

Atribuição

2

Comparação (Menor que)

N+1

Soma

N

Incremento (Soma)

N

Equação de Custo de Processamento T(N)

Neste caso a equação que representa o processamento em função da
Variável de Entrada N é :
T(N) = N + N + N + 1 + 2 + 2 = 3N + 5

O Custo de Processamento T(N) tenta prever o Custo de
Processamento a partir das Variáveis de Entrada.
* se o algoritmo for uma multiplicação N será o tamanho dos números; se for uma ordenação será o no. de elementos a serem ordenados, se for um Grafo será o no. de Nós e Vértices etc.

Notação Assintótica

Algo 1

Eficiência 1

Algo 2

Eficiência 2

Problema

Eficiência 1 = Eficiência 2 p/ um pequeno volume/no. de dados de entrada N
Mas, e para um grande volume de dados ?

* Eficiência aqui significa T(N), a equação de Custo de Processamento.

Notação Assintótica

2

T (n) = n + 100n + log n + 1000
Vamos examinar o comportamento desta Equação.

Notação Assintótica n n**2

100n

logn

1000

1

1

100

0,00

1000

2

4

200

0,30

1000