1 Complexidade de Algoritmos Complexidade de pior caso Complexidade de melhor caso de uso bem menos...

1

Complexidade de Algoritmos Complexidade de pior caso Complexidade de melhor caso

de uso bem menos freqüente em algumas situações específicas

Complexidade de caso médio menos utilizada apesar de importante difícil conhecer a distribuição de

probabilidades das diferentes entradas

2

Recursividade um procedimento recursivo é aquele

que contém uma ou mais chamadas a si mesmo

a todo procedimento recursivo corresponde um não recursivo

os programas recursivos são mais concisos

aparente relação direta com a prova por indução matemática

3

Recursividade Cálculo de fatorialx! = se x <=0 1 senão x * (x-1)!

Implementação não recursivaint fatorial (int N){ int result = 1;

for (i=1; i<=N; i++) result = result * i;

return (result);}

4

Recursividade Implementação recursiva

int fatorial (int N){

if (N<= 1)return(1);

elsereturn( N * fatorial(N-1));

}

5

Recursividade X= fatorial (4)

return( 4* fatorial(3) ) return( 3* fatorial(2) ) return( 2* fatorial(1) ) return( 1 )

6

Análise de Recursividade relação de recorrência – a função é definida em

termos dela própria, recursivamente substituição repetida

1) int fatorial (int N)– { – if (N<= 1)– return(1);– else– return( N * fatorial(N-1));1) }

7

Análise de RecursividadeT(n)

tempo de processar o algoritmo para entrada n

número de passos ou operações dominantes

FatorialT(n) = 1, se n = 0

= T(n-1) + 1, se n > 0

mas quanto é T(n-1) ?

8

T(n) - Fatorial

= (T(n-1)) + 1= (T(n-2) + 1) + 1= T(n-2) + 2= (T(n-3) + 1) + 2= T(n-3) + 3..... forma geral, T(n) = T(n-k) + k, 1 k n fazendo n = k, reduzimos a T(n) = n

9

Maior elemento de uma lista

maior = a[0];for ( i =0; I < N; i++)

if (maior < a[i]) maior = a[i];return (maior);

10

Resolva as recorrências

T(n) = 1, se n = 0 = 2 T(n-1) + 1, se n

>0 T(n) = 1 se n = 0

= T(n/2) + 1 se n>1 T(n) = 1 se n = 1

= 2T(n/2) - n se n > 1

11

Qual melhor algoritmo?

Sejam A e B dois algoritmos que o resolvem o problema P, cujos tempos de execução são

TA(n) e TB(n)

comportamento assintótico – tamanho da entrada arbitrariamente grande caracterizado pela notação O (big O)

12

A notação Sejam f(n) e h(n) funções reais não

negativas da variável inteira n 0 f(n) = O (h(n)) quando existir uma

constante c> 0 e um valor inteiro no tal que

n > no f(n) c.h(n)

13

A notação f(n) = 8n + 128 é O (n2)?f(n) c.n2 ? Seja c =18n + 128 n2, então0 n2 – 8n – 1280 (n – 16)(n+8) n0 = 16

c =1, no = 16, f (n) c.n2 para todo n n0

14

A notação Tempo (ou espaço) é contabilizado em

número de passos do algoritmo (unidade de armazenamento)

Análise do algoritmo determina uma função que depende do tamanho da entrada n.

10n3 + 4n -10 à medida que n aumenta, o termo cúbico

começa a dominar A constante do termo cúbico tem relativamente

a mesma importância que a velocidade da CPU

15

A notação Complexidade

desprezar constantes aditivas ou multiplicativas

número de passos 3n será aproximado para n

interesse assintótico - termos de menor grau podem ser desprezados: n2 + n será aproximado para n2

6n3 + 4n - 9 será aproximado para n3

16

A notação A função atua como um limite superior

assintótico da função f f = n2 -1 f = (n2) f = n2 -1 f = (n3) f = 403 f = (1) f = 5+2logn +3log2n f = (log2n) f = 5+2 log n +3log2n f = (n) f = 5.2n +5n10 f = (2n)

17

A notação g(n), h(n) - funções reais positivas k - constante f1(n) = g(n) e f2(n) = h(n)

O(g+h) = O(g) + O(h) O(k*g) = k O(g) = O(g) f1(n) + f2(n) = O(max {g(n), h(n)}) f1(n) * f2(n) = O(g(n) * h(n))

18

A notação O algoritmo de inversão de uma

seqüência: o número de passos se mantém o

mesmo para o mesmo valor de n variável independente é n as complexidades de pior, melhor e

pior casos são iguais

19

A notação Para a inversão

efetua sempre n/2 passos então sua complexidade é (n)

Para a soma e o produto de matrizes n x n verifica-se complexidades (n2) e (n3) respectivamente

20

A notação Para procedimentos recursivos pode-se

aplicar a seguinte técnica determina-se o número total de

chamadas ao procedimento recursivo calcula-se a complexidade de

execução de uma única chamada complexidade

número de chamadas complexidade de uma chamada

21

A notação por outro lado, um outro exemplo:

duas matrizes A e B de dimensões n x n

um parâmetro x, com valores 0 ou 1 dependendo do valor de x

calcula a soma: se x =0 A + B ou o produto das matrizes: se x = 1 A

* B

22

A notação entrada: n2+1 informações - tamanho

O(n2) se x =0 então complexidade: O(n2)

complexidade do melhor caso se x = 1 então complexidade: O(n3)

complexidade do pior caso

23

Alguns conceitos T (n) = O (1) : constante T (n) = O (log log n) : super-rápido T (n) = O (log n) : logarítmico – muito bom T (n) = O (n) : linear – toda a entrada é visitada T (n) = O (n log n) : limite de muitos problemas T (n) = O (n2) : quadrático T (n) = O (nk) : polinomial no tamanho da entrada T (n) = O (kn), O (n!), O (nn) : exponencial – ruim!

24

Estrutura de Dados Listas lineares

estática dinâmicas

Como manipulá-las: pilhas filas

25

Listas Lineares fácil manipulação

agrupa informações referentes a um conjunto de elementos que se relacionam entre si

Uma lista linear ou tabela é um conjunto de n elementos L[0], L[1], ......, L[n-1] tais que

n>0, e L[0] é o primeiro elemento para 0 < k < n, L[k] é precedido por L[k-

1]

26

Listas Lineares Operações: busca, inclusão e remoção

outras operações: alteração de um elemento na lista combinação de duas ou mais listas ordenação

Casos particulares: remoção e inserção apenas nas extremidades -

deque inserção/remoção em um único extremo - pilha inserções e um extremo e remoções no outro -

fila Alocação: seqüencial ou encadeada

27

 Listas Sequenciais Alocação seqüencial de memória

endereço do (j+1) ésimo elemento se encontra a uma unidade de armazenamento j-ésimo elemento

Representação e acesso i-ésimo elemento: L[i]

Cada elemento pode ser formado por campos uma chave k[i] está associada ao nó L[i] a lista é dita classificada ou ordenado por chave

quando:

se i < j então k[i] precede k[j]

28

Busca Seqüencial busca em uma lista seqüencial

ordenada pelas suas chaves não ordenada

Problema: busca pelo valor v em um conjunto de N elementos. O procedimento retorna o valor da posição da lista sequencial se encontrar e N, caso contrário

29

Busca Seqüencial1

5

3

2

9

7

1

5

3

2

9

7

30

Busca Seqüencial1

5

3

2

9

7

1

5

3

2

9

7

4

Se posição igual a N então não existe no array

N = número de elementos

31

Busca Seqüencial Busca_Seqüencial_1 (v){ pos = 0; while ( (v != L [pos]) && (pos<N) ) pos++; return(pos);}Busca_Seqüencial_2 (v){ L[N] = v; pos = -1; do { pos = pos+1;

} while ( v != L [pos]) return(pos);}

32

Busca Seqüencial  A complexidade do pior caso é O(n) para os

dois algoritmos O segundo é de execução mais rápida pois o

número de testes é menor a cada iteração

Problema: inserir um novo valor em uma lista seqüencial desordenada, caso não exista na respectiva lista

33

Insere_seq (int v){ if (N == (maxN -1)) “overflow”; if (N != 0) {

pos = busca_sequencial (v);if ( pos == N) {

L[pos] = v; N++;}

} else { L[0] = v; N++;}}

Complexidade: O (n). Por que?

Inserção

34

Remoção Problema: remover um valor v existente em

uma lista seqüencial desordenada com N elementos

35

Remoção if (N != 0) {

indice = busca_sequencial (x);if (indice != N){

elemento = a[indice];for (i = indice; i < (N-1); i ++) L[i] = L[i + 1];N--;

} else “elemento não encontrado”;}else “underflow”

Complexidade: O (n) (?)

36

Busca em uma Lista Ordenada Problema: buscar um valor v não existente

em uma lista seqüencial ordenada com N elementos

o tempo de busca pode ser reduzido significantemente devido a relação entre os elementos da lista, mesmo para um conjunto de elementos é grande

37

Busca em uma Lista Ordenada

Busca_Seqüencial_Ord (v){

a[N].chave = v; do {

pos = pos+1; } while ( v < a [pos].chave);if (v != a[pos].chave)

return(pos); return(N);}

complexidade?

38

Busca Binária Busca baseada em "dividir para conquistar"

divida um conjunto de elementos em duas partes determine a qual dessas duas partes a chave

pertence e se concentre nessa parte use índices do array para delimitar a parte sendo

trabalhada ou seja:

compare com a chave do elemento do meio se a chave comparada for menor, o elemento

está na parte esquerda da lista, se maior, na parte direita

aplique o método recursivamente

39

Busca Bináriabusca_binaria (v){ e = 0; d = N-1; do {

pos= (e + d)/ 2; if (v < a[pos].chave) d = pos-1; else e=pos+1;

}while ((v!=a[pos].chave) && (e <= d)); if (v== a[pos].chave) return(pos); else return(N); }

40

Busca Binária

Complexidade: suponha que n = 2k

1o passo: uma lista de n elementos2o passo: uma lista de n/2 elementos 3o passo: uma lista de n/4 elementos ..........k-ésimo passo: uma lista de n/2(k-1) elementos(k+1)-ésimo elemento: uma lista de 1 elemento

log n passos ---- O(log n)

2 5 6 7 9 15 16 23 25 40 52 55

41

  Inserção em Lista Ordenada Problema: inserção de um valor v em uma lista

de elementos ordenada por chave, caso esse elemento não se encontre na lista

Passos: busca inserção na posição retornada

Complexidade: O(n). Por que? Não foi busca binária?

Obs.: remoção é equivalente

42

Complexidade Média - Busca Binária

Comportamente médio do algoritmo de busca binária q - probabilidade de sucesso da busca (1-q) - probabilidade de não achar

L[0] L[1] L[2] .... L[n-1]

R[0] R[1] R[2] R[n-1] R[n]

43

Complexidade Média - Busca Binária

complexidade média = número de passos da busca com sucesso + busca sem sucesso

busca com sucesso são n possibilidades de ter sucesso mesma probabilidade para qualquer elemento:

q/n busca sem sucesso

intervalo R[i] – L[i-1] < v < L[i] a probabilidade é a mesma para qualquer

intervalo = (1- q)/(n+1)

44

Complexidade Média - Busca Binária

(q/n)k + [(1-q)/(n+1)] (k+1)

(n-q+2)/2

45

Algoritmos de Ordenação Problema: encontrar um número de telefone em

uma lista telefônica simplificado pelo fato dos nomes estarem em ordem

alfabética e se estivesse sem uma ordem?

Problema: busca de um livro em uma biblioteca a cada livro é atribuída uma posição relativa a outros

e portanto pode ser recuperado em um tempo hábil

46

Algoritmos de Ordenação

Terminologia básica seqüência de n ítens ou elementos

(registros) r[0], r[1], ……….r[n-1]

a chave a[i] está associada ao elemento r[i] usualmente a chave é um campo do registro os elementos estão classificados por pela chave

se i < j então a[i] precede a[j]

47

Terminologia básica a ordenação tem por objetivo rearrumar as

chaves de forma que obedeçam a uma regra (ex.: ordem numérica ou alfabética)

se os elementos representam registros de um arquivo, sendo representado por uma lista sequencial em memória principal a ordenação é interna

se o arquivo estiver em memória secundária a ordenação é externa

48

  Terminologia básica a ordenação é estável se preserva a ordem

relativa das chaves iguais (senão, instável)

os algoritmos podem operar sobre o elemento ou sobre uma tabela de ponteiros registro é muito grande: ordenação indireta os registros não são rearrumados e sim os

índices as chaves tanto podem ficar armazenadas com

os registros ou com os ponteiros

49

Ordenação por Seleção Um dos algoritmos de sort mais simples:

ache primeiro o menor elemento da lista e troque sua posição com o primeiro elemento

ache o segundo menor elemento e troque sua posição com o segundo elemento

continue até que toda lista esteja ordenada para cada i de 0 a n-2, troca o menor elemento da

sub-lista que vai de i a N-1 com a[i]

50

9 2 6 3 5 7inicial

2 9 6 3 5 7

2 3 6 9 5 7

2 3 5 9 6 7

2 3 5 6 9 7

2 3 5 6 7 9

Cada passo acha o menor e o coloca em sua posição

Ordenação por Seleção

51

Sort por SeleçãoOrd_Seleção(){ int t, i, j,min; for (i=0;i< n-2; i++){ min = i; for (j=i+1; i< n-1; i++)

if (a[j]<a[min]) min = j;/* troca */

t = a[min]; a[min]=a[i]; a[i] = t; } } complexidad

e?

52

Bubble Sort percorrer a lista trocando elementos

adjacentes, se necessário quando nenhuma troca for efetuada ao

percorrer toda a lista está classificada

53

Bubble Sort

9 2 6 3 5 7

2 9 6 3 5 7

2 6 9 3 5 7

2 6 3 9 5 7

2 6 3 5 9 7

2 6 3 5 7 9

54

Bubble Sort

2 6 3 5 7 9 2 3 5 6 7 9

2 3 5 6 7 92 6 3 5 7 9

2 3 6 5 7 9

55

Bubble Sort

2 3 5 6 7 9

2 3 5 6 7 9

2 3 5 6 7 9

Não ocorreram trocas

56

Bubble Sort(){

int i, j, t, trocas; for (i = n-1; i>0; i--) {

trocas = 0; for (j = 1; j <= i; j++){

if (a[j-1] > a[j]){ /* troca */

t = a[j-1]; a[j-1] = a[j]; a[j] = t; trocas++;

} }

if (trocas == 0) break; }

}complexidade?

57

Pensar escreva um algoritmo de merge de duas

listas sequenciais ordenadas, analisando sua complexidade

escreva um algoritmo que some dois polinômios, sendo estes, representados por listas sequenciais. especifique as listas a complexidade