Análise de Algoritmos - Recursividade

Analise de Algoritmos

Recursividade

Divisão e Conquista

–p. 1/71

Recursividade

Muitos problemas possuem a seguintepropriedade: uma solução pode ser obtida atravésda solução de instâncias menores do mesmoproblema. Dizemos que esses problemas têmnatureza recursiva.

Para resolver um tal problema podemos aplicar oseguinte método:

– p. 2/71

Recursividade

se a instância em questão é pequena, resolva-adiretamente

– p. 3/71

Recursividade


senão,reduza-a a instâncias menores do mesmoproblema,resolva os problemas menoresrecursivamente,resolva o problema original.

– p. 3/71

Recursividade


senão,reduza-a a instâncias menores do mesmoproblema,resolva os problemas menoresrecursivamente,resolva o problema original.

A aplicação desse método produz um algoritmorecursivo. – p. 3/71

Fatorial

Fat(n) = n.(n! 1). . . . .2.1

– p. 4/71

Fatorial

Fat(n) = n. (n! 1). . . . .2.1! "# $Fat(n! 1)

– p. 5/71

Fatorial

Fat(n) = n. (n! 1). . . . .2.1! "# $Fat(n! 1)

Fat(n) = n.Fat(n! 1)

– p. 5/71

Fatorial

Fat(n) = n. (n! 1). . . . .2.1! "# $Fat(n! 1)

Fat(n) = n.Fat(n! 1)

Fat(n) =

%&

'1 se n = 0,

n.Fat(n! 1) se n > 0

– p. 5/71

Fatorial - algoritmo

Algoritmo: Fat(n)

Entrada: Um inteiro n " 0

Saída: n!

– p. 6/71


Algoritmo: Fat(n)


Saída: n!Início

Se n = 0 então retorne(1)

senão retorne(n.Fat(n! 1))

Fim

–p. 6/71


Algoritmo: Fat(n)


Saída: n!Início

Se n = 0 então retorne(1)

senão retorne(n.Fat(n! 1))

Fim

A condição de parada é fundamental!!!

– p. 6/71

Soma de n números

Algoritmo: Soma(n,A)

Entrada: Um inteiro n > 0 e um vetor A[1..n]Saída: O valor A1 + A2 + · · ·+ An

– p. 7/71

Soma de n números

Algoritmo: Soma(n,A)

Entrada: Um inteiro n > 0 e um vetor A[1..n]Saída: O valor A1 + A2 + · · ·+ An

Início

Se n = 1 então retorne(A1)

Senão retorne(An + Soma(n! 1, A))

Fim

–p. 7/71

Exercícios

1. Escreva um algoritmo recursivo para determinaro (um) maior elemento de um vetor A[1..n] deinteiros.

– p. 8/71

Busca binária – recursivo

– p. 9/71

Busca binária – recursivoAlgoritmo: Buscabin (l, r)Entrada: Um par (l, r) representando A[l..r]Saída: (“sim”, k) ou “não”

– p. 9/71


InícioSe l > r então imprima “não”

– p. 9/71


InícioSe l > r então imprima “não”senão

k # $(l + r)/2%;Se x = Mk então imprima (“sim”, k)

– p. 9/71



k # $(l + r)/2%;Se x = Mk então imprima (“sim”, k)senão se x > Mk então Buscabin (k + 1, r)

senão Buscabin (l, k ! 1)Fim

– p. 9/71





Qual o tempo (pior caso) gasto pelo algoritmo?

– p. 9/71





Qual o tempo (pior caso) gasto pelo algoritmo?Resposta: O(log n)

– p. 9/71


Ordenação por intercalação(Mergesort)

– p. 10/71

Ordenação por intercalação – mergesort

Algoritmo: Ordinter(l, r)Entrada: Um par (l, r) representando A[l..r]Saída: A[l..r] em ordem não decrescente

– p. 11/71



InícioSe l = r então retorne(Al)

– p. 11/71



InícioSe l = r então retorne(Al)senão

k # $(l + r)/2%;L1 # Ordinter(1, k); L2 # Ordinter(k + 1, j);L3 # Intercala(L1, L2);retorne(L3)

Fim

– p. 11/71



InícioSe l = r então retorne(Al)senão

k # $(l + r)/2%;L1 # Ordinter(1, k); L2 # Ordinter(k + 1, j);L3 # Intercala(L1, L2);retorne(L3)

Fim

Qual o tempo gasto pelo algoritmo?

– p. 11/71


O tempo gasto pelo mergesort pode ser descritopela recorrência

– p. 12/71



T (n) = T ($n/2%) + T (&n/2') + n, T (1) = 0

– p. 12/71



T (n) = T ($n/2%) + T (&n/2') + n, T (1) = 0

Uma forma mais imediata de resolvê-la é observarque

T (n) ( 2T (&n/2') + n

e aplicar o método master, o que resulta em

T (n) = O(n log n)

– p. 12/71

Exercícios1. Escreva o algoritmo Intercala(L1, L2) para intercalar

dois vetores ordenados.

– p. 13/71


Ordenação por concatenação(Quicksort)

– p. 14/71

Ordenação por concatenação – quicksort

Algoritmo: Ordconc(l, r)Entrada: Um par (l, r) representando A[l..r]Saída: A[l..r] em ordem não decrescente

– p. 15/71



InícioSe l < r então

j # Partição(l, r);Ordconc(1, j ! 1);Ordconc(j + 1, r);

Fim

– p. 15/71





Fim


– p. 15/71





Fim

Qual o tempo (pior caso) gasto pelo algoritmo?Resposta: O(n2). Porém, o tempo médio é O(n log n)

– p. 15/71

Quicksort – partição

Algoritmo: Partição(l, r)Entrada: (l, r) representando A[l..r]Saída: Um valor j tal que A[l..j ! 1] são menores do que Aj

que, por sua vez, é menor ou igual a A[j + 1..r].

– p. 16/71



que, por sua vez, é menor ou igual a A[j + 1..r].Início

j # l; k # r;

– p. 16/71




j # l; k # r;Enquanto (j < k) faça

– p. 16/71




j # l; k # r;Enquanto (j < k) façaEnquanto (j < k) e (Aj ( Ak) faça k # k ! 1;Se j < k então { Troca(Mj ,Mk); j # j + 1 }

– p. 16/71




j # l; k # r;Enquanto (j < k) façaEnquanto (j < k) e (Aj ( Ak) faça k # k ! 1;Se j < k então { Troca(Mj ,Mk); j # j + 1 }Enquanto (Aj < Ak) faça j # j + 1;Se j < k então { Troca(Mj ,Mk); k # k ! 1 }

retorne(j)Fim

– p. 16/71





retorne(j)FimQual o tempo (pior caso) gasto pelo algoritmo?

– p. 16/71





retorne(j)FimQual o tempo (pior caso) gasto pelo algoritmo? O(r ! l).

– p. 16/71

Exercícios

1. Execute o algoritmo partição no caso em quetodos os elementos do vetor A[l..r] são iguaisentre si. O que voce observa? Qual o valor de j

que o algoritmo devolve?

2. Exiba uma instância de pior caso do algoritmopartição?

– p. 17/71


Tempo médio do Quicksort

– p. 18/71

Tempo médio do quicksort

Teorema: O tempo médio gasto pelo quicksort paraordenar um vetor A[1..n] é O(n log n), supondo quecada uma das n! permutações dos n elementos deA tem a mesma probabilidade de ocorrer comoentrada.

– p. 19/71


Teorema: O tempo médio gasto pelo quicksort paraordenar um vetor A[1..n] é O(n log n), supondo quecada uma das n! permutações dos n elementos deA tem a mesma probabilidade de ocorrer comoentrada.Dem.: A rapidez média T (n) em questão pode serexpressa pela seguinte recorrência:

– p. 19/71


Teorema: O tempo médio gasto pelo quicksort paraordenar um vetor A[1..n] é O(n log n), supondo quecada uma das n! permutações dos n elementos deA tem a mesma probabilidade de ocorrer comoentrada.Dem.: A rapidez média T (n) em questão pode serexpressa pela seguinte recorrência:

T (n) = n+1

n

n!1(

i=0

(T (i) + T ((n! 1)! i))

– p. 19/71


T (n) = n+1

n

n!1(

i=0

(T (i) + T ((n! 1)! i))

– p. 20/71


T (n) = n+1

n

n!1(

i=0

(T (i) + T ((n! 1)! i))

T (n) = n+2

n

n!1(

i=0

T (i)

– p. 20/71


T (n) = n+1

n

n!1(

i=0

(T (i) + T ((n! 1)! i))

T (n) = n+2

n

n!1(

i=0

T (i)

nT (n) = n2 + 2n!1(

i=0

T (i)

– p. 20/71


nT (n) = n2 + 2n!1(

i=0

T (i)

– p. 21/71


nT (n) = n2 + 2n!1(

i=0

T (i)

(n! 1)T (n! 1) = (n! 1)2 + 2n!2(

i=0

T (i)

– p. 21/71


nT (n) = n2 + 2n!1(

i=0

T (i)

(n! 1)T (n! 1) = (n! 1)2 + 2n!2(

i=0

T (i)

Subtraindo membro a membro as duas equaçõesacima, tem-se:

nT (n)! (n! 1)T (n! 1) = (2n! 1) + 2T (n! 1)

– p. 21/71


nT (n)! (n! 1)T (n! 1) = (2n! 1) + 2T (n! 1)

– p. 22/71


nT (n)! (n! 1)T (n! 1) = (2n! 1) + 2T (n! 1)

nT (n) = (n+ 1)T (n! 1) + (2n! 1)

– p. 22/71


nT (n)! (n! 1)T (n! 1) = (2n! 1) + 2T (n! 1)

nT (n) = (n+ 1)T (n! 1) + (2n! 1)

Dividindo ambos os membros por n(n+ 1):

T (n)

n+ 1=

T (n! 1)

n+

(2n! 1)

n(n+ 1)

– p. 22/71


T (n)

n+ 1=

T (n! 1)

n+

(2n! 1)

n(n+ 1)

– p. 23/71


T (n)

n+ 1=

T (n! 1)

n+

(2n! 1)

n(n+ 1)

T (n)

n+ 1( 2

n+ 1+

T (n! 1)

n

– p. 23/71


T (n)

n+ 1=

T (n! 1)

n+

(2n! 1)

n(n+ 1)

T (n)

n+ 1( 2

n+ 1+

T (n! 1)

n

T (n)

n+ 1( 2

n+ 1+

2

n+

T (n! 2)

n! 1

– p. 23/71


T (n)

n+ 1=

T (n! 1)

n+

(2n! 1)

n(n+ 1)

T (n)

n+ 1( 2

n+ 1+

T (n! 1)

n

T (n)

n+ 1( 2

n+ 1+

2

n+

T (n! 2)

n! 1

T (n)

n+ 1( 2

n+ 1+

2

n+

2

n! 1+

T (n! 3)

n! 2

– p. 23/71


T (n)

n+ 1( 2

n+ 1+

2

n+

2

n! 1+ · · ·+ 2

3+

T (1)

2

– p. 24/71


T (n)

n+ 1( 2

n+ 1+

2

n+

2

n! 1+ · · ·+ 2

3+

T (1)

2

T (n)

n+ 1( 2

n+1(

x=3

1

x

– p. 24/71


T (n)

n+ 1( 2

n+ 1+

2

n+

2

n! 1+ · · ·+ 2

3+

T (1)

2

T (n)

n+ 1( 2

n+1(

x=3

1

x

T (n)

n+ 1( 2

) n+1

x=2

dx

x

– p. 24/71


T (n)

n+ 1( 2

) n+1

x=2

dx

x

– p. 25/71


T (n)

n+ 1( 2

) n+1

x=2

dx

x

T (n)

n+ 1( 2 loge(n+ 1)

– p. 25/71


T (n)

n+ 1( 2

) n+1

x=2

dx

x

T (n)

n+ 1( 2 loge(n+ 1)

T (n) ( 2(n+ 1) loge(n+ 1)

– p. 25/71


T (n)

n+ 1( 2

) n+1

x=2

dx

x

T (n)

n+ 1( 2 loge(n+ 1)

T (n) ( 2(n+ 1) loge(n+ 1)

T (n) = O(n log n)

– p. 25/71


Limite inferior paraa ordenação

–p. 26/71

Limite inferior para a ordenação

Algoritmos de ordenação como o bubblesort,seleção, mergesort, quicksort, etc. são todosalgoritmos baseados em comparação. Éexatamente algoritmos desse tipo queconsideraremos nesta seção.

– p. 27/71


Algoritmos de ordenação como o bubblesort,seleção, mergesort, quicksort, etc. são todosalgoritmos baseados em comparação. Éexatamente algoritmos desse tipo queconsideraremos nesta seção.

Pergunta: Qual o número mínimo de comparaçõesque qualquer algoritmos de ordenação baseadoem comparações necessita para resolver oproblema da ordenação?

–p. 27/71


A execução de qualquer algoritmo de ordenação(baseado em comparações) pode ser representadapor uma árvore binária chamada “árvore dedecisão”.

– p. 28/71

Árvore de decisão

– p. 29/71

Árvore de decisãoCada caminho da raiz até uma folhacorresponde a uma sequência de comparaçõesnecessárias para se concluir uma ordem doselementos.

– p. 30/71

Árvore de decisãoCada caminho da raiz até uma folhacorresponde a uma sequência de comparaçõesnecessárias para se concluir uma ordem doselementos.

Cada uma das n! permutações de n elementospode ocorrer, e cada uma destas permutaçõesdeve aparecer como folha em uma árvore dedecisão.

– p. 30/71

Árvore de decisãoPortanto, toda árvore de decisão querepresenta um algoritmo de ordenação deve terpelo menos n! folhas.

– p. 31/71


Baseado nestas observações, podemos mostrarque:

– p. 31/71


Baseado nestas observações, podemos mostrarque:

Teorema: O problema da ordenação de n elementostem cota inferior !(n log n).

– p. 31/71

Árvore de decisãoDem.: Considere um algoritmo R que resolve oproblema da ordenação.

– p. 32/71

Árvore de decisãoDem.: Considere um algoritmo R que resolve oproblema da ordenação. Seja A a árvore dedecisão correspondente a R para uma entrada detamanho n.

– p. 32/71

Árvore de decisãoDem.: Considere um algoritmo R que resolve oproblema da ordenação. Seja A a árvore dedecisão correspondente a R para uma entrada detamanho n. Então A possui pelo menos n! folhas.

– p. 32/71

Árvore de decisãoDem.: Considere um algoritmo R que resolve oproblema da ordenação. Seja A a árvore dedecisão correspondente a R para uma entrada detamanho n. Então A possui pelo menos n! folhas.Toda árvore binária com k folhas tem altura " log k.

– p. 32/71

Árvore de decisãoDem.: Considere um algoritmo R que resolve oproblema da ordenação. Seja A a árvore dedecisão correspondente a R para uma entrada detamanho n. Então A possui pelo menos n! folhas.Toda árvore binária com k folhas tem altura " log k.Logo, A altura de A é " log n!.

– p. 32/71

Árvore de decisãoDem.: Considere um algoritmo R que resolve oproblema da ordenação. Seja A a árvore dedecisão correspondente a R para uma entrada detamanho n. Então A possui pelo menos n! folhas.Toda árvore binária com k folhas tem altura " log k.Logo, A altura de A é " log n!. Mas o tempo T (n)

gasto por R é dado pela altura de A.

– p. 32/71


gasto por R é dado pela altura de A. Ou seja,T (n) " log n! = "(n log n).

– p. 32/71


gasto por R é dado pela altura de A. Ou seja,T (n) " log n! = "(n log n). Portanto, o problemada ordenação de n elementos tem cota inferior!(n log n).

– p. 32/71

Exercícios

1. Mostre, através de uma árvore de decisão, queo problema da busca (por comparações) de umelemento em uma lista ordenada de n

elementos tem cota inferior !(log n).

– p. 33/71


Máximo e mínimo de um vetor

– p. 34/71

Máximo e mínimo de um vetorAlgoritmo: Maxmin(l, r)Entrada: Um par (l, r) representando A[l..r]Saída: Um par (Ai, Aj) contendo o maior e o menor valorde A[l..r]

– p. 35/71

Máximo e mínimo de um vetorInício

Se l = r então retorne(Al, Al)

– p. 36/71


Se l = r então retorne(Al, Al)senão Se l = r ! 1

então Se Al " Ar então retorne(Al, Ar)senão retorne(Ar, Al)

– p. 36/71




senão k # $(l + r)/2%;(MaxL,MinL)# Maxmin(l, k);(MaxR,MinR) # Maxmin(k + 1, r);max# maximo(MaxL,MaxR);min # minimo(MinL,MinR);retorne(max,min)

Fim

– p. 36/71




senão k # $(l + r)/2%;(MaxL,MinL)# Maxmin(l, k);(MaxR,MinR) # Maxmin(k + 1, r);max# maximo(MaxL,MaxR);min # minimo(MinL,MinR);retorne(max,min)

Fim


– p. 36/71

Tempo gasto pelo Maxmin

Seja T (n) o número de comparações feitas peloMaxmin para um vetor com n elementos.

– p. 37/71


Seja T (n) o número de comparações feitas peloMaxmin para um vetor com n elementos. EntãoT (n) pode ser descrito pela seguinte recorrência:

– p. 37/71



T (1) = 0, T (2) = 1

– p. 37/71



T (1) = 0, T (2) = 1

T (n) = T (&n/2') + T ($n/2%) + 2

– p. 37/71



T (1) = 0, T (2) = 1

T (n) = T (&n/2') + T ($n/2%) + 2

Vamos mostrar que

T (n) (*3n

2

+! 2

– p. 37/71


T (n) (*3n

2

+! 2

– p. 38/71


T (n) (*3n

2

+! 2

T (1) = 0 =,3.12

-! 2

– p. 38/71


T (n) (*3n

2

+! 2

T (1) = 0 =,3.12

-! 2

T (2) = 1 =,3.22

-! 2

– p. 38/71


T (n) (*3n

2

+! 2

T (1) = 0 =,3.12

-! 2

T (2) = 1 =,3.22

-! 2

T (n) = T (&n/2') + T ($n/2%) + 2

– p. 38/71


T (n) (*3n

2

+! 2

T (1) = 0 =,3.12

-! 2

T (2) = 1 =,3.22

-! 2

T (n) = T (&n/2') + T ($n/2%) + 2

(.3&n/2'

2

/! 2 +

.3$n/2%

2

/! 2 + 2

– p. 38/71


T (n) (*3n

2

+! 2

T (1) = 0 =,3.12

-! 2

T (2) = 1 =,3.22

-! 2

T (n) = T (&n/2') + T ($n/2%) + 2

(.3&n/2'

2

/! 2 +

.3$n/2%

2

/! 2 + 2

(.3&n/2'

2

/+.3$n/2%

2

/! 2

– p. 38/71


T (n) (*3n

2

+! 2

T (1) = 0 =,3.12

-! 2

T (2) = 1 =,3.22

-! 2

T (n) = T (&n/2') + T ($n/2%) + 2

(.3&n/2'

2

/! 2 +

.3$n/2%

2

/! 2 + 2

(.3&n/2'

2

/+.3$n/2%

2

/! 2

Analisar os casos: n = 4k + i, para i = 0, 1, 2, 3.

– p. 38/71


T (n) (*3&n/2'

2

++

*3$n/2%

2

+! 2

n = 4k

– p. 39/71


T (n) (*3&n/2'

2

++

*3$n/2%

2

+! 2

n = 4k + 1

– p. 40/71


T (n) (*3&n/2'

2

++

*3$n/2%

2

+! 2

n = 4k + 2 e n = 4k + 3 (exercício).

– p. 41/71

Exercícios

1. Pode-se desenvolver um algoritmo nãorecursivo para calcular o máximo e o mínimo deuma lista baseado na seguinte idéia:compara-se pares de elementos consecutivose, em seguida, compara-se o maior no par como máximo temporário e o menor no par com omínimo temporário. Escreva este algoritmo ecalcule o número de comparações realizadas.

2. Qual é um limite inferior para este problema?

–p. 42/71


Seleção do k-ésimo mínimo

–p. 43/71


Dado um vetor L[1 · · ·n] com n elementos, escrevaum algoritmo para determinar o k-ésimo menorelemento, para 1 ( k ( n.

– p. 44/71



Solucao: ordenar o vetor.

– p. 44/71



Solucao: ordenar o vetor. Tempo O(n log n).

– p. 44/71



Solucao: ordenar o vetor. Tempo O(n log n).

Utilizando a divisão e conquista, vamos projetarum algoritmo linear.

– p. 44/71


Ideia: dividir L em três sublistas L1, L2 e L3 deacordo com um elemento m de L tais que:

L1 contenha todos os elementos menores doque m;

L2 contenha todos os elementos iguais a m;

L3 contenha todos os elementos maiores doque m.

– p. 45/71


Ideia: dividir L em três sublistas L1, L2 e L3 deacordo com um elemento m de L tais que:

L1 contenha todos os elementos menores doque m;

L2 contenha todos os elementos iguais a m;

L3 contenha todos os elementos maiores doque m.

Atenção especial à escolha de m.

– p. 45/71

Escolha dem

Divida L em |L|/5 listas de 5 elementos cada;

– p. 46/71

Escolha dem


Ordene separadamente cada uma dessaslistas;

– p. 46/71

Escolha dem



SejaM a lista das medianas das listas de 5elementos.

– p. 46/71

Escolha dem



SejaM a lista das medianas das listas de 5elementos.

m será a mediana deM .

– p. 46/71


Algoritmo: Seleção(k, L)Entrada: Um inteiro k e um vetor L[1..n]Saída: O k-ésimo menor elemento de L

– p. 47/71


1. Se n < 15 então “ordene L e pare com saída (Lk)”

– p. 48/71


1. Se n < 15 então “ordene L e pare com saída (Lk)”2. Divida L em listas de 5 elementos cada;3. Ordene separadamente cada uma dessas listas;4. SejaM a lista das medianas das listas de 5 elementos;

– p. 48/71


1. Se n < 15 então “ordene L e pare com saída (Lk)”2. Divida L em listas de 5 elementos cada;3. Ordene separadamente cada uma dessas listas;4. Seja M a lista das medianas das listas de 5 elementos;5. m # Seleção(&|M |/2',M)

– p. 48/71



6. Sejam L1, L2 e L3 as sublistas dos elementos de L quesão menores, iguais e maiores do que m, respect.;

– p. 48/71




7. Se |L1| " k então pare com saída Seleção(k, L1)

– p. 48/71





8. senão Se (|L1|+ |L2|) " k

– p. 48/71





8. senão Se (|L1|+ |L2|) " k

então pare com saída (m)

– p. 48/71





8. senão Se (|L1|+ |L2|) " k

então pare com saída (m)

senão pare com saída Seleção(k ! |L1|! |L2|, L3)

– p. 48/71

Seleção do k-ésimo mínimo - Tempo

Seja T (n) o tempo gasto pelo algoritmo seleçãopara determinar o k-ésimo mínimo em uma listacom n elementos.

– p. 49/71



O tempo de execução das linhas 1 a 4 é O(n).

– p. 49/71




A listaM das medianas contém no máximo n/5

elementos, e a execução da linha 5 requertempo T (n/5).

– p. 49/71




A listaM das medianas contém no máximo n/5

elementos, e a execução da linha 5 requertempo T (n/5).

A linha 6 também requer tempo O(n).

– p. 49/71


Cada chamada recursiva nas linhas 7 e 8requer tempo máximo T (3n/4).

– p. 50/71


Cada chamada recursiva nas linhas 7 e 8requer tempo máximo T (3n/4).

Podemos então expressar o tempo T (n) pelaseguinte recorrência:

T (n) (

%&

'cn para n < 15,

T (n/5) + T (3n/4) + cn para n " 15

– p. 50/71


Vamos mostrar, por indução em n que

T (n) ( 20cn

– p. 51/71



T (n) ( 20cn

A afirmação é claramente verdadeira para n < 15.

– p. 51/71



T (n) ( 20cn

A afirmação é claramente verdadeira para n < 15.Vamos supor, por hipótese de indução, que ela éválida para valores menores do que n, e vamosprovar sua validade para n.

– p. 51/71


T (n) ( T (n/5) + T (3n/4) + cn

– p. 52/71


T (n) ( T (n/5) + T (3n/4) + cn

( 20c(n/5) + 20c(3n/4) + cn

– p. 52/71


T (n) ( T (n/5) + T (3n/4) + cn

( 20c(n/5) + 20c(3n/4) + cn

= 20c(n/5 + 3n/4) + cn

– p. 52/71


T (n) ( T (n/5) + T (3n/4) + cn

( 20c(n/5) + 20c(3n/4) + cn

= 20c(n/5 + 3n/4) + cn

= 20c(19n/20) + cn

– p. 52/71


T (n) ( T (n/5) + T (3n/4) + cn

( 20c(n/5) + 20c(3n/4) + cn

= 20c(n/5 + 3n/4) + cn

= 20c(19n/20) + cn

= 20cn

– p. 52/71

Exercícios

1. Calcule o tempo gasto pela seleção do k-ésimomínimo no caso em que as sublistas tenham:(a) 7 elementos; (b) 3 elementos.

2. Suponha que ao invés de selecionar o k-ésimomínimo, queremos determinar os k-elementosmínimos, mas sem a sua ordem relativa. Seráque isso pode ser feito em tempo O(n)?

3. Dado uma lista com n elementos, determine seexiste um elemento que aparece n/2 vezes oumais.

– p. 53/71


Multiplicação de matrizes

–p. 54/71


Sejam A e B duas matrizes n) n. A matrizproduto C = A.B é, por definição, uma matriz n) n

onde cada elemento cij é obtido por

cij =n(

k=1

aikbkj

Cada elemento cij requer, portanto, a realização den produtos. Como a matriz produto C possui n2

elementos cij, este algoritmo para calcular oproduto de duas matrizes tem rapidez O(n3).

– p. 55/71


Veremos nesta seção o Algoritmos de Strassen,um algoritmo para multiplicação de matrizes comrapidez O(nlog 7), que é aproximadamente n2,81.Para simplificar a apresentação, vamos supor quen é uma potência de 2.

– p. 56/71


Particionamos A e B em submatrizes quadradasde ordem (n/2)) (n/2). Então o produto A.B podeser calculado da seguinte forma:

0

1 C11 C12

C21 C22

2

3 =

0

1 A11 A12

A21 A22

2

3 ·

0

1 B11 B12

B21 B22

2

3

Ou equivalentemente,

Cij = Ai1B1j + Ai2B2j, i, j = 1, 2

– p. 57/71


0

1 C11 C12

C21 C22

2

3 =

0

1 A11 A12

A21 A22

2

3 ·

0

1 B11 B12

B21 B22

2

3

C11 = A11B11 + A12B21

C12 = A11B12 + A12B22

C21 = A21B11 + A22B21

C22 = A21B12 + A22B22

– p. 58/71


O cálculo das 4 matrizes Cij requer 8 produto dematrizes. A idéia central do algoritmo de Strassené reduzir estes 8 produtos para 7. Isso é feito daseguinte forma:

– p. 59/71


Calculamos inicialmente as matrizes

S1 = A11(B12 ! B22)

S2 = (A11 + A12)B22

S3 = (A21 + A22)B11

S4 = A22(B21 ! B11)

S5 = (A21 + A22)(B11 + B22)

S6 = (A12 ! A22)(B21 + B22)

S7 = (A11 ! A21)(B11 + B12)

– p. 60/71


As matrizes Cij podem ser calculadas da seguinteforma:

C11 = S5 + S4 ! S2 + S6

C12 = S1 + S2

C21 = S3 + S4

C22 = S5 + S1 ! S3 + S7

– p. 61/71


As matrizes Cij podem ser calculadas da seguinteforma:

C11 = S5 + S4 ! S2 + S6

C12 = S1 + S2

C21 = S3 + S4

C22 = S5 + S1 ! S3 + S7

O cálculo dos Cij desta forma requer 7 produtos dee 18 soma de matrizes de ordem (n/2)) (n/2).

– p. 61/71


Portanto, o tempo gasto pelo algoritmo de Strassenpode ser descrito pela recorrência

T (n) = 7T (n/2) + cn2

– p. 62/71


Portanto, o tempo gasto pelo algoritmo de Strassenpode ser descrito pela recorrência

T (n) = 7T (n/2) + cn2

cuja solução pelo método master é

T (n) = "(nlog 7)

– p. 62/71


Na prática, o algoritmo de Strassen não é maisutilizado do que o algoritmo tradicional, poralgumas razões, tais como:

– p. 63/71



O fator constante em "(nlog 7) é alto;

As submatrizes adicionais e as chamadasrecursivas consomem espaço considerável.

– p. 63/71



O fator constante em "(nlog 7) é alto;

As submatrizes adicionais e as chamadasrecursivas consomem espaço considerável.

Testes empíricos mostram que o algoritmo deStrassen começa a ser mais rápido que oalgoritmo tradicional quando n > 100.

– p. 63/71


Subsequência máxima

–p. 64/71


Dada uma sequência (x1, x2, . . . , xn) de númerosreais (positivos e negativos), encontre umasubsequência (xi, xi+1, . . . , xj) (de elementosconsecutivos) tal que a soma dos números seja amaior possível.

– p. 65/71



Por exemplo, na sequência

(2, !3, 1.5, !1, 3, !2, !3, 3)

a subsequência máxima é

–p. 65/71



Por exemplo, na sequência

(2, !3, 1.5, !1, 3, !2, !3, 3)

a subsequência máxima é (1.5, !1, 3).

– p. 65/71


Pode haver mais de uma subsequênciamáxima.

– p. 66/71



Se todos os números são negativos, asubsequência máxima é vazia, e a soma dosseus elementos é zero.

– p. 66/71



Se todos os números são negativos, asubsequência máxima é vazia, e a soma dosseus elementos é zero.

Queremos projetar um algoritmo que determimauma subsequência máxima.

– p. 66/71


Ajuda alguma coisa se:

dividirmos o problema? (divisão e conquista)

– p. 67/71




soubermos a subsequência máxima de(x1, x2, . . . , xn!1)?

–p. 67/71




soubermos a subsequência máxima de(x1, x2, . . . , xn!1)?

e se soubermos a subsequência máxima e osufixo máximo de (x1, x2, . . . , xn!1)?

–p. 67/71


Algoritmo: Subseq-Max(L)Entrada: Um vetor x[1..n]Saída: O valor da subsequência máxima

–p. 68/71


Iníciosubseq-max# 0; sufixo-max# 0;

– p. 69/71


Iníciosubseq-max# 0; sufixo-max# 0;Para i = 1 até n faça

– p. 69/71


Iníciosubseq-max# 0; sufixo-max# 0;Para i = 1 até n façaSe (xi+ sufixo-max > subseq-max)

– p. 69/71


Iníciosubseq-max# 0; sufixo-max# 0;Para i = 1 até n façaSe (xi+ sufixo-max > subseq-max)então sufixo-max# sufixo-max +xi;

subseq-max# sufixo-max

–p. 69/71



subseq-max# sufixo-maxsenão se (xi+ sufixo-max > 0)

– p. 69/71



subseq-max# sufixo-maxsenão se (xi+ sufixo-max > 0)

então sufixo-max# sufixo-max +xi;senão sufixo-max# 0

Fim

–p. 69/71

Exercícios

1. Modifique o algoritmo para que ele determineuma subsequência máxima.

– p. 70/71

Outros problemas

1. Par mais próximo.

– p. 71/71

Education

Análise de Algoritmos - Recursividade