1

Classificação e Pesquisa

Análise de Algoritmos- Complexidade

Prof. Rodrigo Rochaprof.rodrigorocha@yahoo.com http://www.bolinhabolinha.com

Onde EstamosEmenta• Pesquisa de Dados

SeqüencialBinária

• Métodos de ordenaçãoseleção e trocadistribuiçãoinserçãoIntercalação

• ÁrvoresPesquisaPesquisaBináriaAVLPatrícia

• B-Tree• Tabelas hash

Estática e Dinâmica

2

Introdução“Um algoritmo é um procedimento, consistindo de um conjunto de regras não ambíguas, as quais especificam, para cada entrada, uma seqüência finita de operações, terminando com uma saída correspondente.Um algoritmo resolve um problema quando, para qualquer entrada, produz uma resposta correta, se forem concedidos tempo e memória suficientes para sua execução.Os recursos de espaço e tempo requeridos têm grande importância em casos práticos.Às vezes, o algoritmo mais imediato está longe de ser razoável em termos de eficiência ”razoável em termos de eficiência.”

(Do livro Complexidade de Algoritmos – Laira V. Toscani & Paulo S. Veloso. 2ª edição. Sagra-Luzzatto, 2005)

Introdução

Um programa codifica um algoritmo para ser executado em um computador, resolvendo assim um problemaassim um problema

Base matemática é necessária para respondermos algumas questões?• O problema tem solução ? (Existe um algoritmo?)p ç ( g )• Classe de complexidade de um problema. (O

algoritmo é eficiente?)

3

Análise de algoritmo

Características de performance (uso dos recursos)• tempo memória banda etctempo, memória, banda, etc ...• foco: tempo de execução

Por que analisar os algoritmos?• escolher o algoritmo mais eficiente para

solucionar um problema• o tempo de execução e razoável para aplicações

práticas ?• O algoritmo é ótimo ?

Análise de algoritmos

O fato de um algoritmo resolver um problema não implica que ele seja aceitável na prática.• Exemplo: Achar o determinante de uma matriz n xExemplo: Achar o determinante de uma matriz n x

n

4

Análise de algoritmos

Mesmo com máquinas cada vez mais rápidas devo me preocupar com o desempenho do algoritmo ?algoritmo ?

Revisão estrutura de dados

Estrutura de Dados• um caminho sistemático para organizar e acessar

dadosdados• tipos:

vetorespilhafilalistalistaárvoregrafotabela de hashing

5

ArrayARRAY

• Coleção de itens do mesmo tipo• Tempo de acesso constante• Controlado pelo índice• Controlado pelo índice• Remoção custosa se não quisermos ter espaços

vazio• Exercício:

Implementar a remoção de um elemento, eliminado o espaço deixado por ele.

Pilha (Stack)

Características• LIFO Last In First Out

último elemento inserido será o primeiro removidoúltimo elemento inserido será o primeiro removido

a-) pilha S com 4 elementos, b-) PUSH(S,17) e PUSH(S,3) c-) Pilha após POP(S)

STACK-EMPTY(S)1 if top[S] = 0

2 then return TRUE 3 else return FALSE

PUSH(S, x)1 top[S] ← top[S] + 1

2 S[top[S]] ← x

POP(S) 1 if STACK-EMPTY(S)

2 then error "underflow" 3 else top[S] ← top[S] - 1

4 return S[top[S] + 1]

6

Fila (Queue)

Características• FIFO – First In First Out

primeiro elemento inserido e o primeiro removidoprimeiro elemento inserido e o primeiro removido

ENQUEUE(Q, x)1 Q[tail[Q]] ← x

2 if tail[Q] = length[Q] 3 then tail[Q] ← 1

4 else tail[Q] ← tail[Q] + 1

a-) fila com 5 elementos Q[7..11] b-) enqueue(Q,17), enqueue(Q,3) e enqueue(Q,5)c-) Pilha após dequeue(Q)

4 else tail[Q] ← tail[Q] + 1

DEQUEUE(Q)1 x ← Q[head[Q]]

2 if head[Q] = length[Q] 3 then head[Q] ← 1

4 else head[Q] ← head[Q] + 1 5 return x

Exercícios10.1-1 (Cormen) Ilustre o resultado de cada operação na seqüência PUSH(S, 4), PUSH(S, 1), PUSH(S, 3), POP(S), PUSH(S, 8), e POP(S) em uma pilha S implementada em um vetor S[1..6].

10.1-3 (Cormen) Ilustre o resultado de cada operação na seqüência ENQUEUE(Q, 4), ENQUEUE(Q, 1), ENQUEUE(Q, 3), DEQUEUE(Q), ENQUEUE(Q, 8), e DEQUEUE(Q) em uma fila Q implementada em um vetor Q[1 .. 6].

7

Lista Ligada

elementos em sequenciadiferente do vetor:

não é tem número de elementos fixos• não é tem número de elementos fixos• ordem no vetor é pelo índice, já na lista e pelo

ponteiro que indica o próximo elemento

Lista duplamente ligadaCada nó possui: • chave, apontador para o próximo e apontador para o

anterior

a-) lista duplamente encadeade 9,16,4,1 b-) LIST-INSERT(L, x), onde key[x] = 25 c-) LIST-DELETE(L, x), onde x aponta para o objeto com chave 4.

LIST-SEARCH(L, k) 1 x ← head[L]

2 while x ≠ NIL and key[x] ≠ k3 do x ← next[x]

4 return x

LIST-INSERT(L, x)1 next[x] ← head[L] 2 if head[L] ≠ NIL

3 then prev[head[L]] ← x4 head[L] ← x

5 prev[x] ← NIL

LIST-DELETE(L, x) 1 if prev[x] ≠ NIL

2 then next[prev[x]] ← next[x] 3 else head[L] ← next[x]

4 if next[x] ≠ NIL 5 then prev[next[x]] ← prev[x]

8

Lista duplamente ligada

com “sentinela”

Árvores

Uma estrutura de dados não linear composta de um nó raiz e vários elementos ligados a estaestasó pode ter um nó raiznós ligados a raiz são chamados filhosnós sem filhos são chamados de folhas

9

Arvoré bináriaUma árvore em que:Cada um dos nós tem somente dois filhos

Exercício (Cormen 10 4 1):Exercício (Cormen 10.4-1):Desenhe a árvore binária, que tem raiz noindice 6 e é representada pelos seguintes

campos:

Grafo

um conjunto de pontos (vértices) ligados por retas (as arestas)Uso:Uso:• mapa de estradas

10

Tabela HashAssocia chaves de pesquisa (hash) a valoresbusca rápidafunção de espalhamento• gera indica a partir de uma chavegera indica a partir de uma chave• entradas A e B geram saídas diferentes, senão geram colisão• colisão intolerável, hash de criptografia

Usos:• cache, indexação de base de dados

Indução Matemática

O Método de Indução Matemática é um método de demonstração elaborado com base no Princípio de Indução Finita,base no Princípio de Indução Finita, frequentemente utilizado para provar que certas propriedades são verdadeiras para todos os números naturais. (fonte: e-escola)

Passos:• base da indução• hipótese da indução• passo da indução

11

ExercíciosBase da indução: Para qualquer inteiro positivo

• n < 2n

• Provando: para n=1 1<21 1<2 temos a base verdadeira

Hipótese da indução: suponhamos que seja verdade para qualquer k inteiro positivo:positivo:

• k < 2k

Passo indução: Para o sucessor de k (k+1), desejamos provar que:• 2k < 2.2k = 2k+1

• (k+1) < 2k+1

• (k+1) < 2k e 2k<2k+1

• (k+1) < 2k+1

Crescimento de funções

1 - constantel l ít ilog2n - logarítmican - linearn log2n - linearítmican2 - quadrática

3 úbin3 - cúbica2n - exponencialn! - fatorial

12

ExercícioRepresente graficamente as seguintes funçõesX f(x)=log2x f(x)=x f(x)=x+2 f(x)=xlog2x f(x)=x^2 f(x)=2^x0 0,00 0 2 0,0 0 11 0,00 1 3 0,0 1 22 1 00 2 4 2 0 4 4

25,00

30,00

35,00

f( ) l

2 1,00 2 4 2,0 4 43 1,58 3 5 4,8 9 84 2,00 4 6 8,0 16 165 2,32 5 7 11,6 25 32

-5,00

0,00

5,00

10,00

15,00

20,00

0 1 2 3 4 5 6

f(x)=logxf(x)=xf(x)=x+2f(x)=xlogxf(x)=x^2f(x)=2 x

Gráfico das funções

Logaritmica• logba= c• exemplo:• exemplo:

13

Gráfico das funções

Linear (1º Grau)• y=f(x)=ax+b, com era, bER e a<>0• reta• reta• exemplo:

Gráfico das funções

Quadrática (2º Grau)• y = f(x) = ax² + bx + c, onde a, b e c são

constantes reais e a<>0constantes reais e a 0• parábola• exemplo:

14

Gráfico das funções

Exponencial• y = f(x) = ex

• exemplo:• exemplo:

Gráfico das funções

15

Análise de desempenhoTempo de execução exato do algoritmo

• normalmente difícil de determinar• o tempo de execução do algoritmo cresce a conforme o tamanho da entrada• pode ser medido pelo número de algumas operações – operações fundamentais

ordenação – comparação quanto a ordembusca - comparação quanto a igualdadebusca comparação quanto a igualdade

Devido a este fato, estudamos:• melhor caso• caso médio – normalmente difícil de determinar• pior caso

Mais fácil de analisarCrucial para aplicações, como jogos, robótica, financeiras, médicas, ...

Usamos: notação assintótica• A notação assintótica (notação assimptótica) é uma aproximação matemática para

a comparação entre o crescimento de duas funções. (fonte: wikipédia)

Porque não utilizamos unidades temporais ? (segundo, milisegundo, etc..)• depende do hardware, qualidade na implementação, eficiência do compilador, etc...

Notação Assintótica

Limite superior assintótico.Notação: f (n) = O(g(n))

16

Notação Assintótica

Limite inferior assintótico.• Notação: f (n) = Ω(g(n))

Notação Assintótica

Limite rigoroso assintótico.Notação: f (n) = Θ(g(n))

17

Bibliografia

Livro texto• ZIVIANI, Nivio. Projeto de Algoritmos : com implementação em Pascal

e C.. 2ª ed. São Paulo: Pioneira Thomson Learning, 2004.• VELOSO, Paulo A. S.. Estrutura de Dados. 1ª ed. São Paulo: Campus, , p ,

1983.• CORMEN, Thomas H. Algoritmos : teoria e prática. 1ª ed. Rio de Janeiro:

CAMPUS, 2002.

Complementar• SCHILDT, Herbert. C Completo e Total. 3ª ed. São Paulo: Pearson

Education, 2005.Education, 2005.• CELES, Waldemar; CERQUEIRA, Renato. Introdução a Estruturas de

Dados : com técnicas de programação em C. 4ª ed. Rio de Janeiro: Elsevier, 2004

• WIRTH, Niklaus. Algoritmos e Estruturas de Dados. 1ª ed. Rio de Janeiro: LTC, 1989

• TENENBAUM, Aaron M; SOUZA, Tereza Cristina Félix de. Estruturas de Dados usando C. 1ª ed. São Paulo: Makron Books,1995.