28
1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado [email protected]

1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado [email protected]

Embed Size (px)

Citation preview

Page 1: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

1

Analise de Algoritmos e Notação Assintótica

Alex Fernandes da Veiga Machado

[email protected]

Page 2: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

2

Algoritmo é uma sequencia ordenada e finita de operações bem definidas e eficazes que, quando executadas por um computador, sempre termina num determinado período de tempo, produzindo uma solução ou indicando que a solução não pode ser obtida.

(Procedimento passo a passo para obtenção de um fim)

AlgoritmoAlgoritmo

Page 3: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

3

Análise de AlgoritmosAnálise de Algoritmos Análise de Algoritmo

tempo de processamento em função dos dados de entrada; espaço de memória total requerido para os dados; comprimento total do código; correcta obtenção do resultado pretendido (convervência); robustez (como comporta-se com as entradas inválidas ou não

previstas).

Análise de Algoritmos é medição de complexidade de algoritmo quantidade de "trabalho" necessária para a sua execução,

expressa em função das operações fundamentais, as quais variam de acordo com o algoritmo, e em função do volume de dados.

Page 4: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

4

Complexidade

Porquê o estudo da Complexidade? Performance

Escolher entre vários algoritmos o mais eficiente para implementar;

Desenvolver algoritmos mais eficientes (melhorar os algoritmos), devido ao aumento constante do "tamanho" dos problemas a serem resolvidos.

Complexidade Computacional - torna possível determinar se a implementação de determinado algoritmo é viável.

Page 5: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

5

Complexidade Tipos de Complexidade

Espacial Este tipo de complexidade representa, por

exemplo, o espaço de memória usado para executar o algoritmo.

Temporal Este tipo de complexidade é o mais usado podendo

dividir-se em dois grupos: Tempo (real) necessário à execução do algoritmo.

(como podemos medir?) Número de instruções necessárias à execução.

Page 6: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

6

Medidas de Análise Devem ser independentes da tecnologia

(hardware/software) Modelos Matemáticos simplificados baseados nos

factores relevantes: Tempo de Execução

Uma função que relaciona o tempo de execução com o tamanho de entrada:

t = F(n) Conjunto de operações a serem executadas. Custo associado à execução de cada operação.

Ocupação de Espaço em Memória

Analise de Algoritmos

Page 7: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

7

Complexidade

Exemplo Sejam 5 algoritmos A1 a A5   para resolver um mesmo problema, de

complexidades diferentes. (Supomos que uma operação leva 1 ms para ser efetuada.)  

Tk(n) é a complexidade ou seja o número de operações que o algoritmo efectua para n entradas

n A1 T1(n)= n

A2 T2(n)=nlog n

A3 T3(n)=n2

A4 T4(n)=n3

A5 T5(n)=2n

16 0.016s 0.064s 0.256s 4s 1m4s32 0.032s 0.16s 1s 33s 46 Dias

512 0.512s 9s 4m22s 1 Dia 13h 10137 Séculos

 

tempo necessário para o algoritmo em função de n entradas

Page 8: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

8

Operações primitivas

Atribuição de valores a variáveis Chamadas de métodos Operações aritméticas Comparação de dois números Acesso a elemento de um array Seguir uma referência de objeto (acesso a objeto) Retorno de um método

Page 9: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

9

Algoritmo do exemplo em pseudocódigoarrayMax(A, n):

Entrada: array A com n>=1 elementos inteiros

Saida: o maior elemento em A

tmpMax <- A[0]

for i<-1 to n-1 do

if tmpMax < A[i] then

tmpMax <- A[i]

return tmpMax

Page 10: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

10

Algoritmo em operações primitivas tmpMax <- A[0] 2

for i <- 1 to n-1 do 1+n (comparação i<n) Corpo do ciclo

if tmpMax < A[i] then 4(n-1) ou 6 (n-1), se trocar max

tmpMax <- A[i] return tmpMax 1

Total1= 2+1+n+4(n-1)+1= 5n (melhor caso) Total2= 2+1+n+6(n-1)+1= 7n -2 (pior caso)

Page 11: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

11

Simplificamos a análise

Este nível de detalhe é necessário?

Na analise de algoritmos é importante concentrar-se na taxa de crescimento do tempo de execução como uma função do tamanho de entrada n, obtendo-se um quadro geral do comportamento.

Assim para o exemplo basta saber que o tempo de execução de algoritmo cresce proporcionalmente a n. (O tempo real seria n*factor constante, que depende de SW e HW).

Page 12: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

12

Notação Assintótica Notação O (big O)

Definição: Considere uma função f(n) não negativa para todos os inteiros n≥0.

Dizemos que “f(n) é O(g(n))” e escrevemos f(n) = O(g(n)), se existem um inteiro n0 e uma constante c>0, tais que para todo o inteiro n≥n0, f(n) ≤ cg(n)

Caracteriza o comportamento assintótico de uma função,

estabelecendo um limite superior quanto à taxa de crescimento da função em relação ao crescimento de n.

Permite ignorar fatores constantes e termos de menor ordem, centrando-se nos componentes que mais afetam o crescimento de uma função.

Page 13: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

13

Diagrama

Definição do Grande O

Page 14: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

14

Notação Assintótica

Terminologia de classes mais comuns de funções:

Logarítmica - O(log n) Linear - O(n) Quadrática - O(n2) Polinomial – O(nk), com k≥1 Exponencial – O(an), com a>1

Page 15: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

15

Ordens mais comuns

Fonte: Sahni, "Data Structures, Algorithms and Applications in C++"

log n

n

n22n

n

f

n log n

1

(linear)

(quadrática)(exponencial)

(logarítmica)

(constante)

Page 16: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

16

Teoremas1. Comportamento assintótico da soma de duas funções

cujos comportamentos assintóticos particulares são conhecidos:

Se f1(n) = O(g1(n)) e f2(n) = O(g2(n)), então:

f1(n) + f2(n) = O(max(g1(n)) , g2(n)))

1. O(k f(n)) = O(f(n))

2. O(f(n)) O(g(n)) = O(f(n) g(n))

Page 17: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

17

Eficiência de um Algoritmo, mais um exemplo

Três algoritmo para calcular 1 + 2 + … n para um n > 0

Page 18: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

18

Eficiência de um Algoritmo

Número de operações necessárias

O(n) O(n2) O(1)

Page 19: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

19

Eficiência de um Algoritmo

O número de operações em função de n

Page 20: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

20

Eficácia

O(n)

Page 21: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

21

Eficácia

O(n2)

Page 22: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

22

Eficácia

Outro algoritmo de O(n2)

Page 23: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

Complexidade de Algoritmos

Existem três escalas de complexidade:Melhor Caso

Caso Médio

Pior Caso

Nas três escalas, a função f(N) retorna a complexidade de um algoritmo com entrada de N elementos

Page 24: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

Complexidade de Algoritmos – Melhor CasoDefinido pela letra grega Ω (Ômega)

É o menor tempo de execução em uma entrada de tamanho N

É pouco usado, por ter aplicação em poucos casos.

Ex.:Se tivermos uma lista de N números e quisermos encontrar

algum deles assume-se que a complexidade no melhor caso é f(N) = Ω (1), pois assume-se que o número estaria logo na cabeça da lista.

Page 25: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

Complexidade de Algoritmos – Caso Médio

Page 26: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

Complexidade de Algoritmos – Pior Caso

Será o caso utilizado durante esse cursoRepresentado pela letra grega O (O maiúsculo.

Trata-se da letra grega ômicron maiúscula) É o método mais fácil de se obter. Baseia-se no

maior tempo de execução sobre todas as entradas de tamanho N

Ex.:Se tivermos uma lista de N números e quisermos

encontrar algum deles, assume-se que a complexidade no pior caso é O (N), pois assume-se que o número estaria, no pior caso, no final da lista. Outros casos adiante

Page 27: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

Complexidade de Algoritmos

Mas como saber qual é a complexidade de um determinado algoritmo implementado?

Para resolver esse problema, dividiu-se os algoritmos em “Classes de Problemas”, de acordo com o parâmetro que afeta o algoritmo de forma mais significativa

Page 28: 1 Analise de Algoritmos e Notação Assintótica Alex Fernandes da Veiga Machado alexcataguases@hotmail.com

Alguns Exemplos - RecursividadeNo caso da recursividade, depende da quantidade de

iterações que se pode chegarEx.: se eu quiser saber os N primeiros termos de um

fatorial, a complexidade é N

Function Fatorial (N: Integer): Integer;Begin

If n=0 then Fatorial := 1 Else

Fatorial := N + Fatorial (N-1)End;