Slides - Complexidade de Algoritmos

Prévia do material em texto

Linguagens Formais e Autômatos 
(Complexidade de Algoritmos) 
Profs. Júlio Silveira 
e 
Sérgio Monteiro 
Apresentação 
• Objetivos 
– Dominar a utilização da complexidade assintótica como ferramenta 
para a avaliação de algoritmos computacionais. 
– Conhecer as principais técnicas utilizadas no projeto de algoritmos 
para produzir soluções corretas e eficientes. 
– Analisar e categorizar diversos problemas da área de comutação, 
relacionando-os com as principais técnicas algorítmicas estudadas. 
 
Apresentação 
• Ementa 
– Notação assintótica. Análise de algoritmos. 
– Recorrências. Técnicas de Programação. Algoritmos de ordenação. 
– Estruturas de Dados: Listas, Filas, Pilhas, Árvores, e suas aplicações. 
– Grafos e algoritmos clássicos. 
Bibliografia 
• Básica 
• CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Algoritmos – Teoria e 
Prática. Tradução da 3ª edição americana. 
Rio de Janeiro: Elsevier, 2012. 
• SZWARCFITER, J. L.; MARKENZON, L. Estrutura de Dados e seus Algoritmos. 
Rio de Janeiro: LTC, 1997. 
• TOSCANI, L.V.; VELOSO, P.A.S. Complexidade de Algoritmos. Série Livros 
Didáticos, N°. 13. 2. ed. Porto Alegre: Sagra Luzzato, 2005. 
Bibliografia 
• Complementar 
• CELES, W. et al. Introdução a Estrutura de Dados. Rio de Janeiro: Campus, 
2004. 
• LOUDON, K. Mastering Algorithms with C. O'Reilly Media. 1st edition, 1999. 
• SHARRER, C.A. A Practical Introduction to Data Structures and Algorithm 
Analysis. 2nd Edition. Upper Saddle River,NJ: Prentice Hall, 2001. 
• TENENBAUM, A. M. et al. Estruturas de Dados Usando C. São Paulo: Pearson 
Makron Books, 1995. 
• ZIVIANI, N. Projeto de Algoritmos com Implementação em Pascal e C. 2. ed. 
São Paulo: Pioneira Thomson Learning, 2004. 
 
Aula 1 
• Conceitos básicos 
– Problema computacional 
• Definição 
• Instância de um problema 
• Tamanho da entrada 
– Algoritmo 
• Definição 
• Revisão de algoritmos, Exemplos 
• Noções intuitivas de melhor caso, pior caso, e caso médio 
Problema Computacional 
• Algoritmo 
– Procedimento computacional bem definido 
• Toma um conjunto de valores como entrada, e 
• Produz um conjunto de valores como saída. 
– Conjunto finito de instruções 
• realizadas passo a passo, para a 
• resolução de um problema computacional bem definido. 
Definição de Problema Computacional 
• Enunciado que especifica formalmente: 
– Descrição genérica de uma entrada de um dado “tamanho”; e 
– Descrição da saída correspondente à entrada fornecida 
– Opcionalmente pode incluir o “nome” do problema 
 
• O enunciado não especifica “como gerar” a saída 
– O “como gerar” é solução do problema 
– Solução do problema: um algoritmo 
 
Definição de Problema Computacional 
• Tamanho da entrada 
– Parâmetro numérico que descreve sua magnitude 
– Um valor n, ou a quantidade de dígitos binários ou decimais 
necessários para representá-lo. 
• Exemplo: Encontrar o n-ésimo termo da sequência de Fibonacci 
– Se a entrada for um conjunto de valores, o tamanho da entrada n 
geralmente caracteriza a cardinalidade do conjunto. 
• Exemplo: Ordenar um vetor com n elementos. 
 
Instância de um Problema 
• O problema computacional apenas descreve 
– Caracteriza um par (entrada, saída), em termos genéricos 
– Especifica o tamanho da entrada por um parâmetro numérico 
 
• Instância de um problema 
– Um caso particular do problema 
– Exemplo específico de par entrada/saída específico 
Problema Computacional 
• Exemplo 1 
– Nome: Calcular um termo da sequência de Fibonacci 
– Entrada: n (valor natural positivo) 
– Tamanho: n ou log2 (n+1) (bits necessários para representar n) 
– Saída: F(n) 
 
 F = 0, 1, 1, 2, 3, 5, 8, 13, 21,  
Problema Computacional 
• Exemplo 1: Calcular um termo da sequência de Fibonacci 
 
• Instância do problema 
– Entrada: 8 (1000)2 
– Tamanho: 4 (bits) 
– Saída: 13 
 
 F = 0, 1, 1, 2, 3, 5, 8, 13, 21,  
 
 
Problema Computacional 
• Exemplo 2 
– Nome: Ordenação (crescente) dos termos de uma sequência 
– Tamanho: n 
– Entrada: (vetor, n) { vetor[1..n]: sequência  v1, v2, , vn  } 
 { n: número de elementos do vetor } 
 
– Saída: vetor ordenado { Permutação dos valores do vetor 
 em ordem crescente } 
 
 
Problema Computacional 
• Exemplo 2: Ordenação 
 
• Instância do problema 
– Entrada: ( [13, 40, 8, 30, 9, 15, 2], 7 ) 
– Tamanho: 7 
– Saída: [2, 8, 9, 13, 15, 30, 40] 
 
 
Problema Computacional 
• Exemplo 3 
– Nome: Busca não-ordenada (em um vetor qualquer) 
– Tamanho: n 
– Entrada: (vetor, n, chave) { vetor[1..n] } 
 { n: número de elementos } 
 { chave: valor procurado } 
 
– Saída: i Se vetor[i] = chave 
 0 caso chave  vetor 
Problema Computacional 
• Exemplo 3: Busca não-ordenada 
 
• Instâncias do problema 
1. Entrada: ( [15, 3, 25, 40, 31, 2, 8], 7, 25) Tamanho: 7 Saída: 3 
2. Entrada: ( [15, 3, 25, 40, 31, 2, 8], 7, 29) Tamanho: 7 Saída: 0 
3. Entrada: ( [2, 3, 8, 15, 25, 31, 40], 7, 25) Tamanho: 7 Saída: 5 
 
 
Problema Computacional 
• Exemplo 4 
– Nome: Busca ordenada (em um vetor ordenado ) 
– Tamanho: n 
– Entrada: (vetor, n, chave) { vetor[1..n] , ordenado } 
 { n: número de elementos } 
 { chave: valor procurado } 
 
– Saída: i Se vetor[i] = chave 
 0 caso chave  vetor 
Problema Computacional 
• Exemplo 4: Busca ordenada 
 
• Instâncias do problema 
1. Entrada: ( [2, 3, 8, 15, 25, 31, 40], 7, 25) Tamanho: 7 Saída: 5 
2. Entrada: ( [2, 3, 8, 15, 25, 31, 40], 7, 29) Tamanho: 7 Saída: 0 
 
 
Problemas e Algoritmos 
• Problema: Busca não ordenada 
– Busca sequencial 
• Problema: Busca ordenada 
– Busca sequencial, Busca binária 
• Problema: Ordenação 
– Bolha, Seleção, Inserção, Quick, Merge, Heap, Counting, Radix 
 
 
 
Análise de Algoritmos 
• Analisando algoritmos 
– Definição: T(I) 
• Tempo para um algoritmo processar uma entrada I, onde |I| = n 
• Medido em instruções básicas de computação 
• Função do tamanho da entrada: T(I) é função de n 
• Exemplo 
• Um algoritmo processa uma entrada I, de tamanho n, e executa 2n2 
instruções (atribuições, comparações, ) 
 
 T(I) = 2n2 
 
 
Análise de Algoritmos 
• Para um algoritmo qualquer, definimos: 
– Tempo de MELHOR CASO 
• Dentre todas as entradas de tamanho n: f(n) = min |I|=n { T(I) } 
– Tempo de PIOR CASO 
• Dentre todas as entradas de tamanho n: f(n) = max |I|=n { T(I) } 
– Tempo de CASO MÉDIO: 
• Dentre todas as entradas de tamanho n: f(n) = |I|=n p(I) T(I) 
 
p(I): probabilidade de ocorrência da entrada I, 
 dentre todas as entradas de tamanho n 
 
Análise de Algoritmos 
• Analisando algoritmos 
– Exemplo 
• Problema: Busca em vetor não ordenado 
 Entrada: (vetor, n, chave) 
 
 
 
• Proposta: T(I) = número de comparações com elementos 
do vetor, efetuadas por um algoritmo qualquer 
vetor v[1] v[2] v[3] v[4]  v[n] 
 1 2 3 4  n 
Análise de Algoritmos 
• Exemplo (problema: busca em vetor não ordenado) 
– Algoritmo: busca sequencial 
• Comparar chave com v[1], v[2], v[3], , v[n] 
 
 
 
• T(I) = número de comparações com elementos 
do vetor, efetuadas por um algoritmo qualquer 
vetor v[1] v[2] v[3] v[4]  v[n] 
 1 2 3 4  n 
Análise de Algoritmos 
• Algoritmo: busca sequencial 
 
BUSCASEQNAOORD (v,n, chave) 
1 Para i = 1 até n faça 
2 Se chave = v[i] então 
3 Retorne i 
4 Retorne 0 
 
i = 1,3,4,,n (n vezes) 
Análise de Algoritmos 
• Exemplo: Algoritmo debusca sequencial 
– Tempo de MELHOR CASO f(n) = 1 comparação  f(n) = O(1) 
– Tempo de PIOR CASO f(n) = n comparações  f(n) = O(n) 
 
• O(1), O(n): O que é isso? 
– Veremos depois. 
 
 
 
Análise de Algoritmos 
• Exemplo: Algoritmo de busca sequencial 
– Tempo de CASO MÉDIO 
• Assumindo que chave  vetor, e distribuição uniforme 
 
 
 
 









n
i
i
n
nf
1
1
)( 





 n
nnnn
1
3
1
2
1
1
1
 n
n
 321
1



2
)1(1 nn
n2
1n
Análise de Algoritmos 
• Exercício: Algoritmo de busca sequencial 
– Calcule Tempo de CASO MÉDIO, assumindo que 
• Probabilidade Insucesso (chave  vetor): p(in) = 50%; e 
• Probabilidade Sucesso: iguais probabilidades de 
encontrarmos o valor chave em qualquer posição. 
Análise de Algoritmos 
• Exercício: Calcule Tempo de CASO MÉDIO (cont.) 
– Insucesso (chave  vetor) : 
• Ocorrerão n comparações, com probabilidade = 
1
2
 
Análise de Algoritmos 
• Exercício: Calcule Tempo de CASO MÉDIO (cont.) 
– Sucesso (chave  vetor) 
• Ocorrerão comparações conforme a posição da chave 
• Probabilidade total = 
1
2
 , iqualmente distribuída pelos elementos 
• Logo, para um dado índice i específico: 
 
 i comparações; com probabilidade 
 
n2
1
Análise de Algoritmos 
• Exercício: Algoritmo de busca sequencial 
– Resposta: 
 
 
 
 
)(nf









n
i
i
n
ninp
1 2
1
)( 





 n
nnn
n
2
1
2
2
1
1
2
1
2




2
)1(
2
1
2
nn
n
n



4
1
2
nn
4
13 n
Análise de Algoritmos 
• Exercício: Algoritmo de busca sequencial 
– Resposta: 
 
 
 
 
)(nf









n
i
i
n
ninp
1 2
1
)( 





 n
nnn
n
2
1
2
2
1
1
2
1
2




2
)1(
2
1
2
nn
n
n



4
1
2
nn
4
13 n
Análise de Algoritmos 
• Mas por que escolher uma instrução? 
– No exemplo dado, escolhemos a comparação. 
– E as demais instruções do algoritmo? 
 
• Veremos nas próximas aulas. 
 
 
Obrigado! 
 
 
Aula 2 
• Análise de Algoritmos 
– Por que escolher uma instrução? 
• Exemplo: Valor máximo em um vetor 
– Versões iterativas 
• Exemplo: Busca em vetor ordenado 
• Busca sequencial 
• Busca Binária 
Análise de Algoritmos 
• Problema: encontrar o valor máximo em uma sequência 
• Entrada: (vetor, n) 
• Tamanho: n 
• Saída: valor máximo armazenado no vetor. 
– Instância: 
• Entrada: ([13, 40, 8, 30, 9, 15, 2], 7) 
• Tamanho: 7 
• Saída: 40 
 
Análise de Algoritmos 
• Primeira abordagem 
– Algoritmo sequencial – Versão 1.0 
• Examinar v[1], v[2], v[3], , v[n] 
 
 
 
• Vamos primeiro computar todas as instruções do algoritmo 
– f(n) = todas as instruções que forem executadas 
 
vetor v[1] v[2] v[3] v[4]  v[n] 
 1 2 3 4  n 
Análise de Algoritmos 
• Algoritmo sequencial – Versão 1.0 
MAXIMOSEQ1(vetor, n) 
 
1 max = vetor[1] 
 
2 i = 2 
3 Enquanto i <= n faça 
 
4 Se max < vetor[i] então 
5 max = vetor[i] 
6 i = i+1 
 
7 Retorne max 
Análise de Algoritmos 
• Algoritmo sequencial – Versão 1.0 
MAXIMOSEQ1(vetor, n) Quantidade 
 
1 max = vetor[1] 1 vez 
 
2 i = 2 1 vez 
3 Enquanto i <= n faça i = 2,3,4,,n, n+1 (n vezes) 
 
4 Se max < vetor[i] então i = 2,3,4,,n (n-1 vezes) 
5 max = vetor[i] ??? 
6 i = i+1 i = 2,3,4,,n (n-1 vezes) 
 
7 Retorne max 1 vez 
• Algoritmo sequencial – Versão 1.0 
– Custo total do algoritmo: todas as instruções, no melhor caso 
• Nenhuma atribuição –> max = vetor[i] 
 
f(n) = 3 n + 1 (polinômio de grau 1) 
Análise de Algoritmos 
f(n) = 1 + 1 + n + n–1 + 0 + n–1 + 1 
f(n) = O(n)  Dizemos que f(n) é da ordem de n ( ou linear ) 
• Algoritmo sequencial – Versão 1.0 
– Custo total do algoritmo: todas as instruções, no pior caso 
• n–1 atribuições –> max = vetor[i] 
 
f(n) = 4 n (polinômio de grau 1) 
Análise de Algoritmos 
f(n) = 1 + 1 + n + n–1 + n–1 + n–1 + 1 
f(n) = O(n)  Dizemos que f(n) é da ordem de n ( ou linear ) 
Análise de Algoritmos 
• Encontrar o valor máximo em um vetor 
– Algoritmo sequencial – Versão 1.0 
– Computar apenas: 
• f(n) = número de comparações com elementos do vetor 
 
ou 
 
• f(n) = número de atribuições –> max = vetor[i] 
Análise de Algoritmos 
• Algoritmo sequencial – Versão 1.0 
MAXIMOSEQ1(vetor, n) Quantidade 
 
1 max = vetor[1] 1 vez 
 
2 i = 2 1 vez 
3 Enquanto i <= n faça i = 2,3,4,,n, n+1 (n vezes) 
 
4 Se max < vetor[i] então i = 2,3,4,,n (n-1 vezes) 
5 max = vetor[i] ??? 
6 i = i+1 i = 2,3,4,,n (n-1 vezes) 
 
7 Retorne max 1 vez 
Análise de Algoritmos 
• Algoritmo sequencial – Versão 1.0 
– Custo total do algoritmo: comparações, no melhor caso 
 
 
 
– Custo total do algoritmo: comparações, no pior caso 
 
f(n) = n – 1 (polinômio de grau 1) 
f(n) = O(n)  Dizemos que f(n) é da ordem de n ( ou linear ) 
f(n) = n – 1 (polinômio de grau 1) 
f(n) = O(n)  Dizemos que f(n) é da ordem de n 
 ( ou linear ) 
Análise de Algoritmos 
• Algoritmo sequencial – Versão 1.0 
MAXIMOSEQ1(vetor, n) Quantidade 
 
1 max = vetor[1] 1 vez 
 
2 i = 2 1 vez 
3 Enquanto i <= n faça i = 2,3,4,,n, n+1 (n vezes) 
 
4 Se max < vetor[i] então i = 2,3,4,,n (n-1 vezes) 
5 max = vetor[i] ??? 
6 i = i+1 i = 2,3,4,,n (n-1 vezes) 
 
7 Retorne max 1 vez 
Análise de Algoritmos 
• Algoritmo sequencial – Versão 1.0 
– Custo total do algoritmo: atribuições, no melhor caso 
 
 
 
– Custo total do algoritmo: atribuições, no pior caso 
 
f(n) = 0 
f(n) = O(1)  Dizemos que f(n) é da ordem de 1 ( ou constante ) 
f(n) = n – 1 (polinômio de grau 1) 
f(n) = O(n)  Dizemos que f(n) é da ordem de n 
 ( ou linear ) 
Análise de Algoritmos 
• Segunda abordagem 
– Algoritmo sequencial – Versão 2.0 
• Examinar v[1], v[2], v[3], , v[n] 
 
 
 
• Computar apenas as comparações com elementos do vetor 
• Não computar o custo das comparações 
 
vetor v[1] v[2] v[3] v[4]  v[n] 
 1 2 3 4  n 
Análise de Algoritmos 
• Algoritmo sequencial – Versão 2.0 
MAXIMOSEQ2(vetor, n) 
 
1 max = vetor[1] 
 
2 Para i = 2 até n faça 
 
3 Se max < vetor[i] então 
4 max = vetor[i] 
 
5 Retorne max 
Análise de Algoritmos 
• Algoritmo sequencial – Versão 2.0 
 OPERAÇÃO QUANTIDADE 
 
1 max = vetor[1] 
2 Para i = 2 até n faça 
3 Se max < vetor[i] então n-1 vezes: i = 2,3,4,,n 
4 max = vetor[i] 
5 Retorne max 
• Algoritmo sequencial – Versão 2.0 
– Passo básico de computação: comparação max < vetor[i] 
– TEMPO DE PIOR CASO 
SOLUÇÃO: número de comparações efetuadas, no pior caso: 
 i = 2,3,4,,n  (n – 1) iterações 
Análise de Algoritmos 
f(n) = (n – 1) comparações 
f(n) = O(n)  f(n) é da ordem de n 
 Tempo linear 
Análise de Algoritmos 
• Problema: Busca em vetor ordenado 
• Entrada: (vetor, n, chave) 
• Tamanho: n 
• Saída: i Se vetor[i] = chave 
 0 caso chave  vetorAnálise de Algoritmos 
• Algoritmo: Busca Sequencial (em vetor ordenado) 
• Examinar v[1], v[2], v[3], , v[n], até encontrar a chave ou um valor maior. 
• Instância 
 
 
 
 
 
 
 
• 
 
 chave = 15 
 
• Considerar apenas comparações com elementos do vetor 
– Veremos... 
 
 
 
 
 
vetor 2 5 7 18 23 26 
 1 2 3 4 5 6 
Análise de Algoritmos 
• Busca Sequencial (em vetor ordenado) 
BUSCASEQORD(vetor, n, chave) 
 
1 Para i = 1 até n faça 
 
2 Se chave <= vetor[i] então 
3 Se chave = vetor[i] então 
4 Retorne i 
5 Senão 
6 Retorne 0 
 
7 Retorne 0 
Análise de Algoritmos 
• Busca Sequencial (em vetor ordenado) 
 OPERAÇÃO QUANTIDADE 
 
1 Para i = 1 até n faça 
2 Se chave <= vetor[i] então n vezes: i = 1,2,3,4,,n 
3 Se chave = vetor[i] então 
4 Retorne i 
5 Senão 
6 Retorne 0 
 
7 Retorne 0 
• Busca Sequencial (em vetor ordenado) 
– Passo básico de computação: comparação chave <= vetor[i] 
– TEMPO DE PIOR CASO 
SOLUÇÃO: número de comparações efetuadas, no pior caso 
 i = 1,2,3,4,,n  n iterações 
 
Análise de Algoritmos 
f(n) = n comparações 
f(n) = O(n)  f(n) é linear 
Análise de Algoritmos 
• Problema: Busca em vetor ordenado 
• Entrada: (vetor, n, chave) 
• Tamanho: n 
• Saída: i Se vetor[i] = chave 
 0 caso chave  vetor 
 
Análise de Algoritmos 
• Algoritmo: Busca Binária 
• Instância 
 
 
 
 
 
 
 
 
 
 
 
 
 
 chave = 20 
 
• Considerar apenas comparações com elementos do vetor 
 
 
 
 
 
vetor 2 5 7 18 23 26 35 
 1 2 3 4 5 6 7 
Análise de Algoritmos 
• Busca Binária 
BUSCABIN(vetor, ini, fim, chave) 
 
1 Se ini > fim então 
2 Retorne 0 
 
3 meio = (ini+fim)/2  { (ini+fim) div 2 } 
4 Se chave = vetor[meio] então 
5 Retorne i 
 
6 Se chave > vetor[meio] então 
7 Retorne BUSCABIN(vetor, meio+1, fim, chave) 
8 Senão 
9 Retorne BUSCABIN(vetor, ini, meio-1, chave) 
Análise de Algoritmos 
• Busca Binária 
– Chamada inicial à função BUSCABIN 
 
 BUSCABIN(vetor, 1, n, chave) 
 
• Busca Binária 
– Passo básico de computação: comparação chave = vetor[meio] 
– TEMPO DE PIOR CASO 
 
Análise de Algoritmos 
f(n) = log2 (n+1)  comparações (depois veremos a prova) 
f(n) = O(log n)  f(log n) é logarítmica (da ordem de log n) 
• Resumindo (número de comparações) 
– Vetor não ordenado 
• Busca sequencial melhor caso: f(n) = 1  f(n) = O(1) 
 pior caso: f(n) = n  f(n) = O(n) 
– Vetor ordenado 
• Busca sequencial melhor caso: f(n) = 1  f(n) = O(1) 
 pior caso: f(n) = n  f(n) = O(n) 
• Busca binária melhor caso: f(n) = 1  f(n) = O(1) 
 pior caso:  f(n) = O(log n) 
 
 
Análise de Algoritmos 
Análise de Algoritmos 
• Análise de algoritmos iterativos 
– Algoritmos de ordenação 
– Problema: Ordenação 
• Tamanho: n 
• Entrada: (vetor, n) { vetor[1..n]: sequência  v1, v2, , vn  } 
 { n: número de elementos do vetor } 
 
• Saída: vetor ordenado { Permutação dos valores do vetor 
 em ordem crescente } 
 
 
Análise de Algoritmos 
• Análise da complexidade de algoritmos iterativos 
– Exemplo 
• Problema: Ordenação 
• Instância 
 
 
 
 
Entrada: 13 40 8 30 9 15 2 n = 7 
Saída: 2 8 9 13 15 30 40 
Análise de Algoritmos 
• Algoritmo: BubbleSort 
 BUBBLESORT (vetor, n) 
 
1 Para i = n até 2 faça 
 
2 trocou = falso 
 
3 Para j = 1 até i-1 faça 
 
4 Se vetor[j] > vetor[j+1] então 
 
5 aux = vetor[j] { Troca: vetor[j] <=> vetor[j+1] } 
6 vetor[j] = vetor[j+1] 
7 vetor[j+1] = aux 
8 trocou = verdadeiro 
 
9 Se trocou = falso então 
10 retorne 
 
Análise de Algoritmos 
• Algoritmo: BubbleSort 
• Exemplo 
Vetor inicial: 13 40 8 30 9 15 2 Troca? 
i = 7 j = 1 13 40 8 30 9 15 2 NÃO 
j = 2 13 40 8 30 9 15 2 SIM 
j = 3 13 8 40 30 9 15 2 SIM 
j = 4 13 8 30 40 9 15 2 SIM 
j = 5 13 8 30 9 40 15 2 SIM 
j = 6 13 8 30 9 15 40 2 SIM 
13 8 30 9 15 2 40 
Análise de Algoritmos 
• Algoritmo: BubbleSort 
• Exemplo 
Vetor atual: 13 8 30 9 15 2 40 Troca? 
i = 6 j = 1 13 8 30 9 15 2 40 SIM 
j = 2 8 13 30 9 15 2 40 SIM 
j = 3 8 13 30 9 15 2 40 SIM 
j = 4 8 13 9 30 15 2 40 SIM 
j = 5 8 13 9 15 30 2 40 SIM 
8 13 9 15 2 30 40 SIM 
Análise de Algoritmos 
• Algoritmo: BubbleSort 
• Exemplo 
Vetor atual: 8 13 9 15 2 30 40 Troca? 
i = 5 j = 1 8 13 9 15 2 30 40 
j = 2 30 40 
j = 3 30 40 
j = 4 30 40 
30 40 
Análise de Algoritmos 
• Complexidade de pior caso: número de comparações 
BUBBLESORT (vetor, n) 
 
1 Para i = n até 2 faça 
 
2 trocou = falso 
 
3 Para j = 1 até i-1 faça 
 
4 Se vetor[j] > vetor[j+1] então 
 
5 aux = vetor[j] { Troca: vetor[j] <=> vetor[j+1] } 
6 vetor[j] = vetor[j+1] 
7 vetor[j+1] = aux 
8 trocou = verdadeiro 
 
9 Se trocou = falso então 
10 retorne 
 
i = n, n-1, n-2, , 2 
j = 1, 2, 3, , i-1 
Análise de Algoritmos 
• Complexidade de pior caso: número de comparações 
– Número de iterações efetuadas pelo laço da linha 1 (variável i): 
i = n,n-1,n-2,,4,3,2  n-1 iterações. 
– Número de iterações efetuadas pelo laço da linha 3 (variável j): 
 
i = n  j = 1, 2, 3, …, n–1  n–1 comparações 
i = n–1  j = 1, 2, 3, …, n–2  n–2 comparações 
i = n–2  j = 1, 2, 3, …, n–3  n–3 comparações 
… 
 = 3  j = 1, 2  2 comparações 
i = 2  j = 1  1 comparação 
Análise de Algoritmos 
• Complexidade de pior caso: número de comparações 
– Total de comparações 
1 + 2 + 3 + … + (n–1) comparações 
– Soma dos termos consecutivos da P.A.: 
• a1, a2, …, ak 1º termo: a1 = 1 
 Último termo: ak = n-1 
 nº de termos: k = n-1 
• Fórmula da soma dos termos da P.A.: 
 
2
1 kaaS kk


Análise de Algoritmos 
• Complexidade de pior caso: número de comparações 
– Total de comparações: 1 + 2 + 3 + … + (n–1) comparações 
 
f(n) = 
 
 
nn
nnnnnn
2
1
2
1
222
)1(
2
)1()1(1 2
2




)(
2
1
2
1
)( 22 nOnnnf 
Complexidade de pior caso do 
BubbleSort = O(n2) 
Análise de Algoritmos 
• Complexidade de melhor caso: número de comparações 
BUBBLESORT (vetor, n) 
 
1 Para i = n até 2 faça 
 
2 trocou = falso 
 
3 Para j = 1 até i-1 faça 
 
4 Se vetor[j] > vetor[j+1] então 
 
5 aux = vetor[j] { Troca: vetor[j] <=> vetor[j+1] } 
6 vetor[j] = vetor[j+1] 
7 vetor[j+1] = aux 
8 trocou = verdadeiro 
 
9 Se trocou = falso então 
10 retorne 
 
Análise de Algoritmos 
• Complexidade de melhor caso: número de comparações 
 BUBBLESORT (vetor, n) 
 
1 Para i = n até 2 faça 
 
 
 
3 Para j = 1 até i-1 faça 
 
 
4 Se vetor[j] > vetor[j+1] então 
 { Troca: vetor[j] <=> vetor[j+1] } 
8 trocou = verdadeiro 
 
9 Se trocou = falso então 
10 retorne 
 
i = n 
j = 1, 2, 3, , n-1 
i = n  j = 1,2,3,,n-1  n-1 comparações 
Análise de Algoritmos 
• Complexidade de melhor caso: número de comparações 
– Númerode iterações efetuadas pelo laço da linha 1 (variável i): 
i = n  1 iteração (se não houve troca, o procedimento retorna) 
– Número de iterações efetuadas pelo laço da linha 3 (variável j): 
Para i = n  j = 1, 2, 3, …, n–1  n–1 comparações 
 
Análise de Algoritmos 
• Complexidade de melhor caso: número de comparações 
– Total de comparações: n–1 comparações 
 
 
)()( nOnf 
Complexidade de melhor caso do BubbleSort = O(n) 
Análise de Algoritmos 
• Resumindo 
– BubbleSort, número de comparações 
• Melhor caso: n–1 comparações  Complexidade: f(n) = O(n) 
• Pior caso: n2/2 – n/2  Complexidade: f(n) = O(n2) 
 
– BubbleSort, número de trocas entre elementos 
• Melhor caso: 0 trocas  Complexidade: f(n) = O(1) 
• Pior caso: n2/2 – n/2  Complexidade: f(n) = O(n2) 
 
 
 
Obrigado! 
 
 
Aula 3 
• Análise de algoritmos iterativos 
– Algoritmos de ordenação 
• Ordenação por inserção – InsertionSort 
• Ordenação por seleção – SelectionSort 
Análise de Algoritmos 
• Exemplo: Ordenação por Inserção 
 INSERTIONSORT (vet, n) 
 
1 Para i = 2 até n faça 
 
2 j = i 
 
3 Enquanto j > 1 e vet[j] < vet[j-1] faça 
 
 
4 aux = vetor[j] { Troca: vetor[j] <=> vetor[j-1] } 
5 vetor[j] = vetor[j-1] 
6 vetor[j-1] = aux 
 
7 j = j-1 
 
 
Análise de Algoritmos 
• Exemplo: Ordenação por Inserção 
 INSERTIONSORT (vet, n) 
 
1 Para i = 2 até n faça 
 
2 j = i 
 
3 Enquanto j > 1 e vet[j] < vet[j-1] faça 
 
 
4 aux = vetor[j] { Troca: vetor[j] <=> vetor[j-1] } 
5 vetor[j] = vetor[j-1] 
6 vetor[j-1] = aux 
 
7 j = j-1 
 
 
 
Pior caso ? 
 
Análise de Algoritmos 
• Ordenação por Inserção 
– Complexidade de pior caso: número de comparações 
– Total de comparações: 
i = 2 j = 2  1 comparação 
i = 3 j = 3,2  2 comparações 
... 
i = n–1 j = n–1, n–2, ..., 3, 2  n–2 comparações 
i = n j = n , n–1, ..., 3, 2  n–1 comparações 
Análise de Algoritmos 
• Ordenação por Inserção 
– Complexidade de pior caso: número de comparações 
– Total de comparações: 1 + 2 + 3 + … + (n–1) comparações 
 
 
nn
nnnnnn
nf
2
1
2
1
222
)1(
2
)1()1(1
)( 2
2





)(
2
1
2
1
)( 22 nOnnnf 
Complexidade de pior caso do 
InsertionSort = O(n2) 
Análise de Algoritmos 
• Ordenação por Inserção 
– Complexidade de melhor caso: número de comparações 
– Total de comparações: 
i = 2 j = 2  1 comparação 
i = 3 j = 3  1 comparação 
... 
i = n–1 j = n–1  1 comparação 
i = n j = n  1 comparação 
Análise de Algoritmos 
• Ordenação por Inserção 
– Complexidade de melhor caso: número de comparações 
– Total de comparações: (n–1) comparações 
 
Complexidade de melhor caso do 
InsertionSort = O(n) 
Análise de Algoritmos 
• Ordenação por Inserção 
– InsertionSort, número de comparações 
• Melhor caso: n–1 comparações  Complexidade: f(n) = O(n) 
• Pior caso: n2/2 – n/2  Complexidade: f(n) = O(n2) 
 
– Complexidades iguais às do BubbleSort 
 
Análise de Algoritmos 
• Exemplo: Ordenação por Seleção 
 SELECTIONSORT (vet, n) 
 
1 Para i = n até 2 faça 
 
2 im = 1 
 
3 Para j = 2 até i faça 
 
4 Se vet[j] > vet[im] então 
 
5 im = j 
 
6 Se im < i então 
 
7 aux = vetor[i] { Troca: vetor[i] <=> vetor[im] } 
8 vetor[i] = vetor[im] 
9 vetor[im] = aux 
 
 
Análise de Algoritmos 
• Exemplo: Ordenação por Seleção 
 SELECTIONSORT (vet, n) 
 
1 Para i = n até 2 faça 
 
2 im = 1 
 
3 Para j = 2 até i faça 
 
4 Se vet[j] > vet[im] então 
 
5 im = j 
 
6 Se im < i então 
 
7 aux = vetor[i] { Troca: vetor[i] <=> vetor[im] } 
8 vetor[i] = vetor[im] 
9 vetor[im] = aux 
 
 
Análise de Algoritmos 
• Ordenação por Seleção 
– Complexidade de pior caso: número de comparações 
– Total de comparações: 
 1 + 2 + 3 + … + (n–1) comparações (verifique) 
 
– Complexidade de melhor caso: número de comparações 
– Total de comparações: 
 1 + 2 + 3 + … + (n–1) comparações (verifique) 
 
 
 
Análise de Algoritmos 
• Ordenação por Seleção 
– Complexidade de pior caso: número de comparações 
– Total de comparações: 1 + 2 + 3 + … + (n–1) comparações 
 
 
nn
nnnnnn
nf
2
1
2
1
222
)1(
2
)1()1(1
)( 2
2





)(
2
1
2
1
)( 22 nOnnnf 
Complexidade de pior caso do 
SelectionSort = O(n2) 
Análise de Algoritmos 
• Ordenação por Seleção 
– SelectionSort, número de comparações 
• Melhor caso: n2/2 – n/2  Complexidade: f(n) = O(n2) 
• Pior caso: n2/2 – n/2  Complexidade: f(n) = O(n2) 
 
– Complexidades de pior caso iguais às do InsertionSort e BubbleSort 
– Complexidade de melhor caso maior 
Análise de Algoritmos 
• Ordenação por Seleção 
– E em relação ao número de trocas entre 
elementos do vetor? 
 
 
Análise de Algoritmos 
• Ordenação por Seleção 
– Número de trocas entre elementos do vetor 
– Complexidade de pior caso: 
• n–1 trocas (verifique)  Complexidade: f(n) = O(n) 
 
– Complexidade de melhor caso: 
• 0 trocas (verifique)  Complexidade: f(n) = O(1) 
 
 
 
Análise de Algoritmos 
• Exercício 
 Escreva a expressão exata da quantidade de operações de escrita (linha 3) realizada pelo algoritmo abaixo: 
 
 IMPRIMEAST(vetor, n, chave) 
 
 1 Para i = 2 até n-2 faça 
 
 2 Para j = i+1 até n faça 
 3 Escreva ("*") 
 
MOSTRE TODO O DESENVOLVIMENTO, usando as mesmas notações utilizadas em aula. 
Caso a soma envolva termos de uma PA, identifique os parâmetros presentes nas fórmulas 
utilizadas: a1, ak, k. 
Obrigado! 
 
 
Aula 4 
• Análise de Algoritmos 
– Complexidade Assintótica 
• Pior caso 
• Notação O 
• Crescimento assintótico de funções 
Complexidade Assintótica 
Complexidade Assintótica 
• Complexidade de pior caso 
– Limite superior para estimativa do pior caso do 
• Número de instruções dominantes executadas pelo algoritmo 
• Função de n (tamanho da entrada) 
• Notação O 
– Simplificação 
• Constantes aditivas e multiplicativas 
• Termos de mais baixa ordem 
Complexidade Assintótica 
• Complexidade de pior caso 
– Exemplo 
• f(n) = 5n3 + 3n2 + 2n + 100 
 = 5n3 + 3n2 + 2n + 100 
• f(n) = O(n3) 
• f é O(n3) 
Complexidade Assintótica 
• Crescimento assintótico de funções 
 
f(n) 40.000 10.000 log n 5.000 n 1.000 n log n 100 n2 20 n3 2n 
n = 2 
n = 8 
n = 10 
n = 20 
n = 100 
n = 200 
Complexidade Assintótica 
• Crescimento assintótico de funções 
 O(1) O(log n) O(n) O(n log n) O(n2) O(n3) O(2n) 
f(n) 40.000 10.000 log n 5.000 n 1.000 n log n 100 n2 20 n3 2n 
n = 2 
n = 8 
n = 10 
n = 20 
n = 100 
n = 200 
Complexidade Assintótica 
• Crescimento assintótico de funções 
 O(1) O(log n) O(n) O(n log n) O(n2) O(n3) O(2n) 
f(n) 40.000 10.000 log n 5.000 n 1.000 n log n 100 n2 20 n3 2n 
n = 2 40.000 10.000 10.000 2.000 400 160 4 
n = 8 40.000 30.000 40.000 24.000 6.400 10.240 256 
n = 10 40.000 40.000 50.000 40.000 10.000 20.000 1.024 
n = 20 40.000 50.000 100.000 100.000 40.000 160.000 1.048.576 
n = 100 40.000 70.000 500.000 700.000 1.000.000 20.000.000 1,26 1030 
n= 200 40.000 ? ? ? ? ? ? 
Complexidade Assintótica 
• Notação O 
– Cotas assintóticas superiores 
• f(n) = 5n3 + 3n2 + 2n + 100 
 ... 
 f é O(n5) 
 f é O(n4) 
 f é O(n3) 
– Menor cota assintótica superior 
• f = O(n3) 
Complexidade Assintótica 
• Cota Assintótica Superior 
– f = O(g) 
– Exemplo: f = 5n3 + 3n2 + 2n + 100 g = n3 
 ou 
 5n3 + 3n2 + 2n + 100 = O(n3) 
Complexidade Assintótica 
• Cota Assintótica Superior 
– Exemplo: 
 5n3 + 3n2 + 2n + 100 é O(n3) 
porque... 
5n3 + 3n2 + 2n + 100  n3 ? Não! 
5n3 + 3n2 + 2n + 100  5n3 ? Não! 
5n3 + 3n2 + 2n + 100  6n3 ? Sim, a partir de algum valor n0! 
5n3 + 3n2 + 2n + 100  10n3 ? Sim, ... 
Complexidade Assintótica 
• Notação O 
 
f = O(g) 
 
 
c g(n) 
 
f(n) 
 
Complexidade Assintótica 
• Cota Assintótica Superior 
– Definição 
 
Complexidade Assintótica 
• Cota Assintótica Superior 
– Exemplo: 
 3 n2 + 100 é O(n2) 
Prova (1) 
 3 n2 + 100  3 n2 + 100 n2 = 103 n2 
3 n2 + 100  103 n2 
c = 103 e n0 = 1 
 3 n2 + 100  c n2 
Complexidade Assintótica 
• Cota Assintótica Superior 
– Exemplo: 
 3 n2 + 100 é O(n2) 
Prova (2) 
 3 n2 + 100  4 n2 ? 
c = 4 e n0 = 10 
3 n2 + 100  4 n2  4 n2 - 3 n2  100 
 n2  100 
 n  10 
 3 n2 + 100  c n2 
 3 n2 + 100  3 n2 + n2 
3 n2 + 100  4 n2 
Complexidade Assintótica 
• Cota Assintótica Superior 
– Exemplo: 
 3 n2 + 100 
 
 
 
 
 3 n2 + 100 = O(n2) 
3n
2
+100
101 5
n
2
103 n
2
4 n
2
c = 103 n0 = 1 
c = 4 n0 = 10 
Complexidade Assintótica 
• Cota Assintótica Superior 
– Exemplos: 
• 1000 n2 = O(n4) 
• 1000 n2 = O(n3) 
• 1000 n2 = O(n2)  Menor cota assintótica superior 
• 1000 n2 não é O(n) 
 
Complexidade Assintótica 
• Cota Assintótica Superior 
– Exemplos: 
• 10 n log n + 3n = O(n2) 
• 10 n log n + 3n = O(n log n)  Menor cota assintótica superior 
• 10 n log n + 3n não é O(n) 
 
Complexidade Assintótica 
• Cota Assintótica Superior 
– Exemplos: 
• 10 n + 3 log n = O(n) 
• 415 = O(1) 
 
Complexidade Assintótica 
• Ordens Assintóticas 
 
 
 O(nn) 
INEFICIÊNCIA: O(n!) 
 O(2n) exponencial 
 
 O(nk) polinomial Obs.: k fixo (constante) 
 O(n3) polinomial 
 O(n2 log n) 
 O(n2) polinomial 
EFICIÊNCIA: O(n log n) 
 O(n) linear 
 O(log2 n) polilogarítmico Obs.: log2 n = (log2 n)
2 
 O(log n) logarítmico Obs.: log n = log2 n 
 O(1) tempo constante 
 
Complexidade Assintótica 
• Algoritmos eficientes 
 
– DEFINIÇÃO: Um algoritmo é considerado eficiente 
 se sua complexidade (de pior caso) for 
 limitada por um polinômio. 
 
– Exemplo: um algoritmo cuja complexidade de pior caso é 
 O(n log n) é eficiente, pois sua complexidade é 
 limitada pelo polinômio n2 
 
 n log n = O(n2) 
Obrigado! 
 
 
Aula 5 
• Análise de Algoritmos 
– Complexidade Assintótica 
• Notação  
• Notação  
– Limites inferiores de um Problema 
– Algoritmos ótimos 
Complexidade Assintótica 
• Notação  
– Cotas assintóticas inferiores 
• f(n) = 5n3 + 3n2 + 2n + 100 f é (n3) 
 f é (n2) 
 f é (n log n) 
 f é (n) 
 ... 
– Maior cota assintótica inferior 
• f = (n3) 
Complexidade Assintótica 
• Cota Assintótica Inferior 
– f = (g) ou f é (g) 
g é uma cota assintótica inferior de f 
Complexidade Assintótica 
• Cota Assintótica Inferior 
– Exemplo 1 
 
 f = 5n3 + 3n2 + 2n + 100 g = n3 
 
 5n3 + 3n2 + 2n + 100  n3 IN* 
 ou 
 f  g IN* 
 
 5n3 + 3n2 + 2n + 100 = (n3) 
Complexidade Assintótica 
• Cota Assintótica Inferior 
– Exemplo 1 (de forma equivalente) 
 
 f = 5n3 + 3n2 + 2n + 100 g = n3 
 
 n3  5n3 + 3n2 + 2n + 100 IN* 
 ou 
 g  f IN* 
 
 5n3 + 3n2 + 2n + 100 = (n3) 
Complexidade Assintótica 
• Cota Assintótica Inferior 
– Exemplo 2 
 
 f = 
𝑛3
4
+ 3𝑛2 + 2𝑛 + 10 g = 𝑛3 
 
 
𝑛3
4
+ 3𝑛2 + 2𝑛 + 10  
𝟏
𝟒
 𝑛3 IN* 
 ou 
 f  c g IN* 
 
 5n3 + 3n2 + 2n + 100 = (n3) 
Complexidade Assintótica 
• Cota Assintótica Inferior 
– Exemplo 2 (de forma equivalente) 
 
 f = 
𝑛3
4
+ 3𝑛2 + 2𝑛 + 10 g = 𝑛3 
 
 𝑛3  𝟒 
𝑛3
4
+ 3𝑛2 + 2𝑛 + 10 IN* 
 ou 
 g  c f IN* 
 
 5n3 + 3n2 + 2n + 100 = (n3) 
Complexidade Assintótica 
• Cota Assintótica Inferior 
 
Complexidade Assintótica 
• Notação  
 
f = (g) 
 
 
c f(n) 
 
g(n) 
 
Complexidade Assintótica 
• Cota Assintótica Inferior 
– Exemplos: 
• 1000 n2 = (n2)  Maior cota assintótica inferior 
• 1000 n2 = (n log n) 
• 1000 n2 = (n) 
• 1000 n2 = (log n) 
• 1000 n2 = (1) 
• 1000 n2 não é (n3) 
 
Complexidade Assintótica 
• Cota Assintótica Inferior 
– Exemplos: 
• 10 n log n + 3n = (n log n)  Maior cota assintótica inferior 
• 10 n log n + 3n = (n) 
• 10 n log n + 3n = (log n) 
• 10 n log n + 3n = (1) 
• 10 n log n + 3n não é O(n2) 
 
Complexidade Assintótica 
• Cota Assintótica Inferior 
– Exemplos: 
• 10 n + 3 log n = (n) 
• 415 = (1) 
 
Complexidade Assintótica 
• Resumindo: f(n) é O ( g(n) )  f(n)  c g(n) 
 f(n) é  ( g(n) )  f(n)  c g(n) 
 para n  n0 ou para n   
 
• Ainda: se duas funções f e g são tais que 
 f = O(g), 
 então 
 g = (f) 
Complexidade Assintótica 
• Cota Assintótica Exata (ou Justa) 
– Um algoritmo possui tempo de pior caso 
• 5n3 + 3n2 + 2n + 100 
– Podemos afirmar que sua complexidade de pior caso é 
• O(n4) ou O(n3) ? 
• Qual das afirmações é mais exata? 
Complexidade Assintótica 
• Cota Assintótica Exata (ou Justa) 
 
Complexidade Assintótica 
• Notação  
 
f = O(g) 
 
e 
 
f = (g) 
 
Complexidade Assintótica 
• Notação  
– f = (g)  f e g são da mesma ordem 
 
g é a menor cota assintótica superior de f 
e 
g é a maior cota assintótica inferior de f 
 
Exemplo: 5n3 + 3n2 + 2n + 100 é (n3) 
 
Complexidade Assintótica 
• Definição 
– LIMITE INFERIOR PARA UM PROBLEMA P 
• Também chamado complexidade intrínseca do problema 
• Função h, tal que a complexidade de pior caso 
de qualquer algoritmo que resolva P é (h) 
Complexidade Assintótica 
• Exemplo: P = Ordenação 
– Qualquer algoritmo de ordenação tem que efetuar, 
no pior caso, pelo menos uma comparação 
• Tempo de pior caso de um algoritmo de ordenação: f = (1) 
– Logo 
• Lim inf P = Ω(1) 
• Este limite inferior não está bom! 
Complexidade Assintótica 
• Exemplo: P = Ordenação 
– Qualquer algoritmo de ordenação tem que ler e examinar 
todos os elementos do vetor para comparação 
• Tempo de pior caso de um algoritmo de ordenação: f = (n) 
– Logo 
• Lim inf P = Ω(n) 
• Este limite inferior está bom? 
 
Complexidade Assintótica 
• Limites inferiores para um problema P 
– Examinando o problema 
 
 
 
 
 
 
 
 
 
 
– Objetivo 
• Determinar o maior limite inferior possível de um problema. 
• Em geral, o cálculo de limites inferiores é complicado. 
 
LIMITES Ω(n) 
INFERIORES Ω(log n) 
PARA P Ω(1) 
Complexidade Assintótica 
• Algoritmos 
– Cálculo da menor complexidade de pior caso (f) 
de um algoritmo é relativamente simples. 
– Objetivo 
• Desenvolver (descobrir?) algoritmos mais eficientes. 
• Para umdado problema, qual é o melhor algoritmo possível? 
Complexidade Assintótica 
• Limites inferiores para um problema P 
– Examinando o problema 
 
 
 
 
 
 
 
 
 
 
– Objetivo 
• Determinar o maior limite inferior possível de um problema. 
• Em geral, o cálculo de limites inferiores é complicado. 
 
LIMITES Ω(n) 
INFERIORES Ω(log n) 
 Ω(1) 
Complexidade Assintótica 
• Definição 
– ALGORITMO ÓTIMO 
• Algoritmo de menor complexidade de pior caso possível 
• Nenhum outro algoritmo possui complexidade (de pior caso) menor 
• Como descobrir se um algoritmo é ótimo? 
Complexidade Assintótica 
• Problemas x Algoritmos 
– Exemplo: dado um problema P 
 
 
 
 
 
 
 
 
 
 
 
LIMITES Ω(n) 
INFERIORES Ω(log n) 
PARA P Ω(1) 
 
ALGORITMOS O(n3) Algor. A 
QUE O(n2) Algor. B 
RESOLVEM P O(n log n) Algor. C 
Complexidade Assintótica 
• Exemplo: dado um problema P 
– Algoritmo A 
Não é ótimo! 
– Algoritmo B 
Não é ótimo! 
– Algoritmo C? 
Não se sabe! 
 
 
 
LIMITES Ω(n) 
INFERIORES Ω(log n) 
PARA P Ω(1) 
 
ALGORITMOS O(n3) Algor. A 
QUE O(n2) Algor. B 
RESOLVEM P O(n log n) Algor. C 
Complexidade Assintótica 
• Algoritmos ótimos 
– Um algoritmo é sabidamente ótimo se 
sua complexidade de pior caso for 
igual a um limite inferior do problema 
• Exemplo: Ordenação 
• BubbleSort 
InsertionSort 
Selection 
Não são ótimos! 
 
• MergeSort 
E ótimo! 
 O(n2) Bubble 
ALGORITMOS O(n2) Insertion 
DE O(n2) Selection 
 
ORDENAÇÃO O(n log n) Merge 
 
Complexidade Assintótica 
 
LIMITES Ω(n log n) 
 
INFERIORES Ω(n) 
PARA P Ω(1) 
• Outro exemplo: dado um problema P 
• Algoritmo A1 
Algoritmo A2 
Algoritmo A3 
Algoritmo A4 
 
• A1, A2, e A3 
 
não são ótimos! 
• A4 é ótimo? 
Nada se pode afirmar! 
 O(n3) A1 
ALGORITMOS O(n2.5) A2 
QUE RESOLVEM O(n2) A3 
O PROBLEMA P O(n log n) A4 
 
Complexidade Assintótica 
 
 
LIMITES Ω(n) 
INFERIORES 
PARA P Ω(1) 
• Outro exemplo: dado um problema P 
• A4 é ótimo? Nada se pode afirmar! 
• Se alguém descobrir um algoritmo com menor complexidade de pior caso, 
então 
A4 não é ótimo! 
• Se alguém provar que provar que Ω(n log n) é um limite inferior para o 
problema P, então 
A4 é ótimo! 
 
Complexidade Assintótica 
Obrigado! 
 
 
Aula 6 
• Exercícios 
Exercícios 
1) Para n suficientemente grande, ordene as funções abaixo: 
f1(n) = 30 n + 2000 log n 
f2(n) = 3000 log n + 3001 
f3(n) = n
3 
f4(n) = 2999 log
2 n 
f5(n) = 400 n
2 + 300 n + 200 
f6(n) = n log n 
 
Resp.: f2  f4  f1  f6  f5  f3 
Exercícios 
2) Indique a menor cota assintótica superior para as funções: 
f1(n) = 30 n + 2000 log n 
f2(n) = 3000 log n + 3001 
f3(n) = n
3 
f4(n) = 2999 log
2 n 
f5(n) = 400 n
2 + 300 n + 200 
f6(n) = n log n 
 
Resp.: f1 = O(n) f2 = O(log n) f3 = O(n
3) 
 f4 = O(log
2 n) f5 = O(n
2) f6 = O(n log n) 
Exercícios 
3) Encontre um valor de n  IN* que satisfaça as inequações 
abaixo. Basta apenas um valor. Justifique sua resposta. 
a. 30 n2 + n  n3 
 
 
Resp.: 30 n2 + n  30 n2 + n2 = 31 n2. 
 Ou seja, 30 n2 + n  31 n2 
 Resolvemos a inequação 31 n2  n3 dividindo ambos os termos por n2: 
 31 n2  n3  n  31 
 Resposta: n  31 
Exercícios 
3) Encontre um valor de n  IN* que satisfaça as inequações 
abaixo. Basta apenas um valor. Justifique sua resposta. 
b. 100 log n  n 
 
 
Resp.: Solução: testemos n como potências de 2 
 Para n = 32: 100 log 32 = 100  5 = 500  32  Falso 
 Para n = 1024: 100 log 1024 = 100  10 = 1000  1024 
 Resposta: n = 1024 
Exercícios 
3) Encontre um valor de n  IN* que satisfaça as inequações 
abaixo. Basta apenas um valor. Justifique sua resposta. 
c. 10 n2  2n 
 
 
Resp.: Solução: para n = 10, temos 10  100 = 100  1024 
 Resposta: n = 10 
Exercícios 
5) Demonstre as cotas superiores, encontrando valores n0 e c. 
 
5 n3 + 100 n = O( ) 
a. Justifique, encontrando o menor valor natural para c. 
 
Resp.: 5 n3 + 100 n  6 n3 
 6 n3 – 5 n3  100 n 
 n3  100 n (dividindo por n, o que é válido para n IN*) 
 n2  100 
 n  10 
 Resposta: c = 6 n0 = 10 
n3 
Exercícios 
5) Demonstre as cotas superiores, encontrando valores n0 e c. 
 
5 n3 + 100 n = O( ) 
b. Justifique, encontrando outro valor natural para c. 
 
Resp.: 5 n3 + 100 n  5 n3 + 100 n3 
 5 n3 + 100 n  105 n3 
 
 Resposta: c = 105 n0 = 1 
n3 
Exercícios 
7) Deduza uma expressão para f(n): o número de '*'s impressos 
 
 ESCREVE_AST (n: inteiro) 
 
1 Para i de 2 até n–1 faça 
2 Escreva '*' 
3 Para i de n até 2 faça 
4 Para j de 1 até i faça 
5 Escreva '*' 
 
Resp.: Notas de Aula 
 
Exercícios 
7) Resolução 
 
Linha 2: i = 2,3,…,n-1  n-2 escritas 
 
Linha 3: i = n,n-1,n-2,…,2 
 
Linha 4: i = n j = 1,2,3, 3,…,n  n escritas 
 i = n-1 j = 1,2,3, 3,…,n-1  n-1 escritas 
 i = n-2 j = 1,2,3, 3,…,n-2  n-2 escritas 
 … 
 i = 3 j = 1,2,3  3 escritas 
 i = 2 j = 1,2  2 escritas 
 
Exercícios 
7) Resolução (cont.) 
 
f(n) = n–2 + [ 2 + 3 + 4 + … + n ] = n–1 + S 
 
 Onde S é a soma dos termos da PA: a1 = 2 
 ak = n 
 k = n-1 
   
...
2
12
2)( Desenvolva
nn
nnf 


Exercícios 
8) Um problema P tem limite inferior Ω(n2). 
Um algoritmo A resolve este problema com cota assintótica 
superior de melhor caso (n2) e de pior caso (n3). 
 
Responda (JUSTIFIQUE): 
a. Este algoritmo é eficiente? 
b. Este algoritmo é ótimo? 
Respostas nas notas de aula 
Exercícios 
9) Seja o algoritmo abaixo: 
 
 
 
 
 
 
 
 
 
SOMAVETOR (vetor, vsoma, n) { vetor[1..n] e vsoma[1..n] } 
1 Para i de 1 até n faça 
2 vsoma[i] = 0 
3 Para j de 1 até i faça 
4 vsoma[i] = vsoma[i] + vetor[j] 
• 
 
a. Qual o número de operações de adição, no pior caso? 
b. Qual a complexidade de pior caso do algoritmo? 
Respostas nas notas de aula 
Exercícios 
10) Seja o algoritmo abaixo: 
 
 
 
 
 
 
Procedimento MaxMin (v: vetor; n: inteiro; var max, min: inteiro) 
 
1 max := v[1] 
2 min := v[1] 
 
3 Para i := 2 até n faça 
4 Se v[i] > max então max := v[i] 
5 Se v[i] < min então min := v[i] 
 
a. Qual o total de atribuições: i. no melhor caso ii. no pior caso 
b. Complexidade (atribuições): i. de melhor caso ii. de pior caso 
Respostas nas notas de aula 
Exercícios 
12) Em relação ao problema de ORDENAÇÃO de um vetor com n 
posições, considere os algoritmos BUBBLE-SORT e MERGE-SORT. 
a. Qual é o limite inferior máximo do problema de ordenação? 
b. Quais são as complexidades de pior caso dos algoritmos citados? 
c. Os algoritmos são eficientes? Justique. 
d. Os algoritmos são ótimos? Sim, Não, ou Nada se pode afirmar? Justique. 
e. No pior caso de cada um dos algoritmos citados, todos os elementos serão 
comparados entre si? Justifique. 
 
 Respostas nas notas de aula 
Exercícios 
13) (ENADE adaptado) Suponha que se queira utilizar o algoritmo de busca binária para pesquisar a chave 287 em 
um vetor ordenado, contendo chaves entre 1 e 1000. Durante uma pesquisa como essa, uma sequência de 
chaves é examinada. Cada sequência abaixo é uma suposta sequência cronológica de chaves (pertencentes ao 
vetor considerado) que foram examinadas na pesquisa da chave 287. 
I. 7, 342, 199, 201, 310, 258, 287 
II. 110, 132, 133, 156, 289, 288, 287 
III. 252,266, 271, 294, 295, 289, 287 
IV. 715, 112, 530, 249, 406, 234, 287 
De todas as sequências acima, são válidas: 
a. I. 
b. III. 
c. I e II. 
d. II e IV. 
e. III e IV. Respostas nas notas de aula 
Exercícios 
14) Em relação a ordem de complexidade, pode-se afirmar que as 
menores cotas superiores para as funções f1(n) = 4 n
2 + n (log n + 3) 
e f2(n) = (n + log n)
2 – n2 são, respectivamente: 
 
a. f1(n) = O( n
2 log n ) e f2(n) = O( n log n ) 
b. f1(n) = O( n
2 ) e f2(n) = O( n log n ) 
c. f1(n) = O( n log n ) e f2(n) = O( n
2 ) 
d. f1(n) = O( n
2 ) e f2(n) = O( n
2 ) 
e. f1(n) = O( n log n ) e f2(n) = O( n log n ) 
 Respostas nas notas de aula 
Exercícios 
15) (ENADE 2005) No processo de pesquisa binária em um vetor 
ordenado, os números máximos de comparações necessárias para se 
determinar se um elemento faz parte de vetores com tamanhos 50, 
1.000 e 300 são, respectivamente, iguais a: 
a. 5, 100 e 30. 
b. 6, 10 e 9. 
c. 8, 31 e 18. 
d. 10, 100 e 30. 
e. 25, 500 e 150 
Respostas nas notas de aula 
Obrigado! 
 
 
Aula 7 
• Revisão de Estruturas de Dados 
• Exercícios de revisão 
Revisão de Estruturas de Dados 
• Listas Sequenciais 
– Busca (valor x) 
• O(n)  Lista não ordenada 
• O(log n)  Lista ordenada 
– Remoção (valor x) 
• O(n) 
• Busca do valor x: O(log n) ou O(n) 
• Remoção do elemento encontrado: O(n) 
(pode envolver O(n) deslocamentos) 
x1 x2 . . .x3 xn
Revisão de Estruturas de Dados 
• Listas Sequenciais 
– Remoção (posição k) 
• O(n) 
(pode envolver O(n) deslocamentos) 
– Inserção (valor x, posição k) 
• O(n) 
(pode envolver O(n) deslocamentos) 
x1 x2 . . .x3 xn
Revisão de Estruturas de Dados 
• Listas Simplesmente Encadeadas 
 
– Busca(valor x) 
• O(n) 
 
– Remoção (valor x) 
• O(n) 
• O(n) para busca + O(1) para remoção 
 
 
 first
x2x1 xn. . .
 last
Revisão de Estruturas de Dados 
• Listas Simplesmente Encadeadas 
– Remoção (ponteiro p – para o nó a ser excluído) 
• O(n) 
(para encontrar o nó anterior) 
– Inserção (valor x, posição k) 
• O(n) 
(para encontrar a posição) 
 
 
Revisão de Estruturas de Dados 
• Listas Duplamente Encadeadas 
 
– Busca 
• O(n) 
 
– Remoção (valor x) 
• O(n) 
• O(n) para busca + O(1) para remoção 
Revisão de Estruturas de Dados 
• Listas Duplamente Encadeadas 
– Remoção (ponteiro p – para o nó a ser excluído) 
• O(1) 
– Inserção (valor x, posição k) 
• O(n) 
(para encontrar a posição) 
 
Exercícios 
1) Considere um algoritmo que busca um determinado valor em um vetor ordenado, removendo-o do vetor, caso 
seja encontrado. Como o vetor está ordenado, será utilizada a BUSCA BINÁRIA. Queremos avaliar o algoritmo nas 
condições abaixo: 
– Serão consideradas TODAS as operações, tanto as COMPARAÇÕES com os valores do vetor, como os 
DESLOCAMENTOS de seus elementos. 
– Queremos considerar TODAS AS INSTÂNCIAS, até mesmo aquelas em que O VALOR NÃO SEJA ENCONTRADO. 
Sobre o número de operações (comparações mais deslocamentos), efetuadas pelo algoritmo, podemos afirmar: 
a) No pior caso, O(n2) operações serão efetuadas. 
b) No melhor caso, O(n) operações serão efetuadas. 
c) No melhor caso, O(n log n) operações são efetuadas. 
d) No pior caso, O(n) operações serão efetuadas. 
e) O pior caso ocorre quando o valor não é encontrado. 
 
Respostas nas notas de aula 
Exercícios 
2) Considere as operações de busca e remoção em listas simplesmente encadeadas e duplamente encadeadas: 
– Busca(v): procura um nó de valor v na lista, retornando seu endereço, ou null caso não exista. 
– Remove(p): onde p aponta para um nó existente na lista (p é um endereço válido). 
Assinale a alternativa correta: 
a) Se os elementos estiverem ordenados, a busca na lista duplamente encadeada efetuará menos 
comparações do que no caso dos elementos estarem desordenados. 
b) Comparando o algoritmo de busca em ambas as listas, os números de comparações para encontrar os elementos, 
no pior caso, serão distintos. 
c) No pior caso, o número de operações efetuadas para a remoção de um nó apontado por um ponteiro p será: O(n) 
para a lista simplesmente encadeada, e O(1) para a duplamente encadeada. 
d) A remoção de um nó apontado por um ponteiro p, em uma lista simplesmente encadeada, tem a mesma 
complexidade no melhor e no pior caso. 
e) Na lista duplamente encadeada, o algoritmo de remoção efetua, no melhor e no pior caso, O(1) e O(log n) 
operações, respectivamente. 
 
 
Respostas nas notas de aula 
Exercícios 
3) Considere o problema de BUSCA EM VETOR ORDENADO, cujos dois principais algoritmos são: 
BUSCA SEQUENCIAL, e BUSCA BINÁRIA. 
Indique a afirmação correta: 
a) O algoritmo de busca binária também pode ser usado em vetores não ordenados. 
b) No melhor caso, a busca binária e a busca sequencial efetuam números de comparações 
distintos. 
c) No pior caso, a busca binária e a busca sequencial efetuam o mesmo número de comparações 
d) Para qualquer instância do problema, o número de comparações da busca binária sempre será 
menor ou igual ao efetuado pela busca sequencial. 
e) No pior caso, o algoritmo de busca sequencial em vetor ordenado realiza o mesmo número de 
comparações que a sua versão para vetores não ordenados. 
 
Respostas nas notas de aula 
Exercícios 
4) Sobre o método de ordenação da bolha, podemos afirmar que, assumindo ordenação crescente: 
 
a) O número de comparações efetuadas pelo algoritmo será o mesmo quer o vetor esteja ou não 
previamente ordenado. 
b) Em termos de comparações, se os valores do vetor estiverem dispostos em ordem decrescente, 
teremos o pior caso do algoritmo. 
c) O(log n) comparações serão efetuadas pelo algoritmo, no melhor caso. 
d) No pior caso, teremos O(n) comparações efetuadas pelo algoritmo. 
e) Teremos O(n log n) comparações efetuadas pelo algoritmo, no pior caso. 
 
 
Respostas nas notas de aula 
Obrigado! 
 
 
Aula 8 
• Recursividade (recursão) 
– Algoritmos recursivos 
– Árvores de recursão 
– Complexidade de algoritmos recursivos 
• Resolução de recorrências 
Recursividade 
• Algoritmo recursivo 
– Procedimento ou função que chama a si mesmo 
– Uma “instância do algoritmo” faz chamada(s) recursiva(s) 
para resolver uma ou mais “instância(s) menor(es)” 
– A solução das instâncias menores são usadas para a instância 
maior resolver o problema 
– Na base da recursão, o problema trivial é resolvido sem 
mais chamadas recursivas 
Recursividade 
• Árvores de recursão 
– Uma instância de tamanho n 
invoca UMA instância menor 
(de tamanho n–1) 
PROC_REC(n)
 
PROC_REC(n-1)
PROC_REC(n-2)
Recursividade 
• Árvores de recursão 
– Uma instância de tamanho n 
invoca DUAS instâncias 
menores 
(ex. duas instâncias 
 de tamanho n/2) 
PROC_REC(n)
 
PROC_REC(n/2)
PROC_REC(n/4) PROC_REC(n/4)
PROC_REC(n/2)
PROC_REC(n/4) PROC_REC(n/4)
Recursividade 
• Exemplo 
– Problema: valor máximo armazenado em um vetor 
– Entrada: vetor 
– Tamanho: n 
– Saída: max 1 ≤ i ≤ n { vetor[i] } 
Recursividade 
• Problema: valor máximo armazenado em um vetor 
• Algoritmo recursivo 
– MAXREC(vetor,n) 
• MAXREC(vetor,n) chama MAXREC(vetor,n–1) 
• O valor retornado será comparado ao vetor[n] 
 
– Mas... Antes... 
• MAXREC(vetor,n–1) chama MAXREC(vetor,n–2) 
• E assim sucessivamente, até que ... 
Recursividade 
• MAXREC(vetor,5) 
 
 
 
 
• MAXREC(vetor,4) 
 
 
 
15 3 25 40 31 
40 
15 3 25 40 
31 ? 
40 
Retorna 
Retorna 
Recursividade 
• MAXREC(vetor,n)• Chamadas recursivas 
– MAXREC(vetor,5) chama MAXREC(vetor,4) 
– MAXREC(vetor,4) chama MAXREC(vetor,3) 
– ... 
– MAXREC(vetor,1) retorna vetor[1] 
 
 
 
Recursividade 
• Árvore de Recursão 
– vetor 
[ 15,3,25,40,31 ] 
 
 
MAXREC ( [15 3 25 40 31], 5 )
40 > 31 ?
Retorna 40
 
MAXREC ( [15 3 25 40], 4 )
25 > 40 ?
Retorna 40
40
40
Recursividade 
• Árvore de Recursão 
– vetor 
[ 15,3,25,40,31 ] 
 
 
MAXREC ( [15 3 25 40 31], 5 )
40 > 31 ?
Retorna 40
 
MAXREC ( [15 3 25 40], 4 )
25 > 40 ?
Retorna 40
MAXREC ( [15 3 25], 3 )
15 > 25 ?
Retorna 25
15
MAXREC ( [15 3], 2 )
15 > 3 ?
Retorna 15
MAXREC ( [15], 1 )
Retorna 15
40
25
15
40
Recursividade 
• Algoritmo MAXREC 
 
MAXREC(vetor,n) 
1 Se n = 1 então 
2 Retorne vetor[1] 
3 max = MAXREC(vetor,n-1) 
4 Se max > vetor[n] então 
5 Retorne max 
6 Senão 
7 Retorne vetor[n] 
 
 
 
 
Recursividade 
• Qual a complexidade do algoritmo MAXREC? 
 
MAXREC(vetor,n) 
1 Se n = 1 então 
2 Retorne vetor[1] 
3 max = MAXREC(vetor,n-1) 
4 Se max > vetor[n] então 
5 Retorne max 
6 Senão 
7 Retorne vetor[n] 
 
 
 
 
Operação básica? 
comparação (linha 4) 
Recursividade 
• Complexidade de Algoritmos recursivos 
– C(n) : número de Comparações 
– C(n) definida por Recorrência 
– f(n) é a fórmula fechada para a função C(n) 
• Resolução da recorrência 
Recursividade 
• Qual a complexidade do algoritmo MAXREC? 
 
MAXREC(vetor,n) 
1 Se n = 1 então 
2 Retorne vetor[1] 
3 max = MAXREC(vetor,n-1) 
4 Se max > vetor[n] então 
5 Retorne max 
6 Senão 
7 Retorne vetor[n] 
 
 
 
 
C(1) = 
C(n) = 
C(n) definida por recorrência 
C(n–1) + 1 
0 
Recursividade 
• Qual a complexidade do algoritmo MAXREC? 
• Resolver a recorrência C(1) = 0 
 C(n) = C(n–1) + 1 
 
Recursividade 
– C(1) = 0 
C(n) = C(n–1) + 1 
 
= C(n–2) + 1 + 1 
= C(n–3) + 1 + 1 + 1 
= C(n–4) + 1 + 1 + 1 + 1 
... após k passos ... 
C(n) = C(n–k) + k 
... para k = n–1, isto é ... 
... após n–1 passos ... 
C(n) = C( n – (n–1) ) + n–1 
C(n) = C(1) + n–1 
C(n) = n–1 comparações 
Recursividade 
• Qual a complexidade do algoritmo MAXREC? 
• Resposta: 
– f(n) = n–1 comparações  f(n) = O(n) 
 
Recursividade 
• Problema: valor máximo armazenado em um vetor 
• Algoritmo recursivo 
– MAXREC2(vetor,ini,fim) 
• MAXREC2() chama duas instâncias menores de MAXREC2(), 
uma para cada metade do vetor 
– Os valores retornados por cada uma delas é comparado 
para calcular o máximo do vetor original 
• E assim sucessivamente, até que ... 
– Casos triviais: ini = fim 
Recursividade 
• MAXREC2(v,1,8) 
 
 
 
 
 
 
 
15 3 25 40 31 1 8 5 
40 31 ? 
Retorna 
15 3 25 40 31 1 8 5 
Retorna 
Recursividade 
• Árvore de Recursão 
[15,3,25,40,31,1,8,5] 
 
 
MAX(vet,1,8)
40 > 31 ?
Retorna 40
 
MAX(vet,1,4)
15 > 40 ?
Retorna 40
MAX(vet,5,8)
31 > 8 ?
Retorna 31
MAX(vet,1,2)
15 > 3 ?
Retorna 15
MAX(vet,3,4)
25 > 40 ?
Retorna 40
MAX(vet,5,6)
31 > 1 ?
Retorna 31
MAX(vet,7,8)
8 > 5 ?
Retorna 8
MAX(vet,1,1)
Retorna 15
MAX(vet,2,2)
Retorna 3
MAX(vet,3,3)
Retorna 25
MAX(vet,4,4)
Retorna 40
MAX(vet,6,6)
Retorna 1
MAX(vet,7,7)
Retorna 8
MAX(vet,8,8)
Retorna 5
MAX(vet,5,5)
Retorna 31
Recursividade 
• Algoritmo MAXREC2 
 
MAXREC2(vetor,ini,fim) 
1 Se ini = fim então 
2 Retorne vetor[ini] 
3 meio = (ini+fim) div 2 
4 max1 = MAXREC2(vetor,ini,meio) 
5 max2 = MAXREC2(vetor,meio+1,fim) 
6 Se max1 > max2 então 
7 Retorne max1 
8 Senão 
9 Retorne max2 
 
 
 
 
Recursividade 
• Qual a complexidade do algoritmo MAXREC2? 
 
MAXREC2(vetor,ini,fim) 
1 Se ini = fim então 
2 Retorne vetor[ini] 
3 meio = (ini+fim) div 2 
4 max1 = MAXREC2(vetor,ini,meio) 
5 max2 = MAXREC2(vetor,meio+1,fim) 
6 Se max1 > max2 então 
7 Retorne max1 
8 Senão 
9 Retorne max2 
 
 
 
 
Operação básica? 
comparação (linha 6) 
Recursividade 
• Qual a complexidade do algoritmo MAXREC2? 
 
MAXREC2(vetor,ini,fim) 
1 Se ini = fim então 
2 Retorne vetor[ini] 
3 meio = (ini+fim) div 2 
4 max1 = MAXREC2(vetor,ini,meio) 
5 max2 = MAXREC2(vetor,meio+1,fim) 
6 Se max1 > max2 então 
7 Retorne max1 
8 Senão 
9 Retorne max2 
 
 
 
 
C(1) = 
C(n) = 
C(n) definida por recorrência 
2C(n/2) + 1 
0 
Recursividade 
• Qual a complexidade do algoritmo MAXREC2? 
• Resolver a recorrência C(1) = 0 
 C(n) = 2C(n/2) + 1 
 
Recursividade 
– C(1) = 0 
C(n) = 2C(n/2) + 1 
 
= 2[2C(n/4)+1] + 1 = 
= 4C(n/4) + 1 + 2 
= 4[2C(n/8)+1] + 1 + 2 = 
= 8C(n/8) + 1 + 2 + 4 = 
Recursividade 
– C(1) = 0 
C(n) = 2C(n/2) + 1 
 
= 8[2C(n/16)+1] + 1 + 2 + 4 = 
... após k passos ... 
= 8C(n/8) + 1 + 2 + 4 = 
= 16C(n/16) + 1 + 2 + 4 + 8 
= 2k C(n/2k) + 1 + 2 + 22 + 23 + ... + 2k-1 
Recursividade 
– C(1) = 0 
C(n) = 2C(n/2) + 1 
 ... após k passos ... 
= 2k C(n/2k) + 1 + 2 + 22 + 23 + ... + 2k-1 
Recursividade 
– C(1) = 0 
C(n) = 2k C(n/2k) + 1 + 2 + 22 + 23 + ... + 2k-1 
 Vamos examinar a subexpressão C(n/2k) ... 
Conforme k aumenta, n/2k diminui ... 
Suponha que n seja potência de 2. 
Ou seja, n = 2p, para algum p natural ... 
Exemplo: n = 1024 = 210. 
Neste caso p = 10. 
Recursividade 
– C(1) = 0 
C(n) = 2k C(n/2k) + 1 + 2 + 22 + 23 + ... + 2k-1 
 Quando k = p teremos ... 
C(n) = 2p C(n/2p) + 1 + 2 + 22 + 23 + ... + 2p-1 
C(n) = n C(1) + 1 + 2 + 22 + 23 + ... + 2p-1 
C(n) = 1 + 2 + 22 + 23 + ... + 2p-1 
Recursividade 
– C(1) = 0 
C(n) = 1 + 2 + 22 + 23 + ... + 2p-1 
 
 
Relembrando a fórmula da soma dos termos iniciais de 
uma PG: 𝑆𝑘 = 𝑎1
𝑞𝑘−1
𝑞−1
 
C(n) = 2p –1 
Ou seja, C(n) = n –1 
Recursividade 
• Qual a complexidade do algoritmo MAXREC2? 
• Resposta: 
– f(n) = n–1 comparações  f(n) = O(n) 
 
Recursividade 
• Exercícios 
– Notas de aula, Seção 1.8 - Exercícios 
 
Obrigado! 
 
 
Aula 9 
• Principais Técnicas de Projeto de Algoritmos 
– Dividir para Conquistar (ou Divisão e Conquista) 
• Recursividade 
• Balanceamento 
Divisão e Conquista 
• Dividir para Conquistar 
– Se o problema é trivial, resolver de forma direta 
– Caso contrário, quebrar o problema (instância) em subproblemas 
(instâncias menores) 
• Dividir: uma instância de tamanho n em instâncias menores 
• Conquistar: resolver as instâncias menores de forma recursiva 
• Combinar as soluções dos problemas menores para 
formar a solução do problema original 
Divisão e Conquista 
• Definição 
– Balanceamento: dividir um problema (instância) em 
subproblemas (instâncias) de mesmo tamanho 
• O balanceamento permite, em muitos casos, algoritmos 
mais eficientes, como veremos nos exemplos a seguir. 
 
Divisão e Conquista 
• Problema: Ordenação 
– Algoritmo 1: Ordenação por Seleção (Selection_Sort) 
• Identificar o índice m com o maior valor em vetor[1..n] 
• Trocar os elementos m e n: vetor[m] ↔ vetor[n] 
• Repetir o processo 
 invocar o mesmo algoritmo, recursivamente, 
 para ordenar o vetor[1..n–1] 
Divisão e Conquista 
• SELECTION_SORT (vetor,8) 
 
 
 
 
 
 
 
• SELECTION_SORT(vetor,7) 
 
 
 
15 3 25 40 31 1 8 5 
Retona 4 
15 3 25 5 31 1 8 40 
IMAXIMO(vetor,8) 
15 3 25 5 31 1 8 40 
40 5 
vetor[4] ↔ vetor[8] 
Ordena [1..7] 
Divisão e Conquista 
• Ordenação por Seleção 
SELECTION_SORT(vetor,n)
 
SELECTION_SORT(vetor,n-1)
 
SELECTION_SORT(vetor,n-2)
 
SELECTION_SORT(vetor,1)
 

 
Divisão e Conquista 
• Ordenação por Seleção 
 
SELECTION_SORT(vetor,n) { Ordena o vetor[1..n] } 
1 Se n = 1 então 
2 Retorne 
3 i = IMAXIMO(vetor,n) { Retorna o índice do maior elemento } 
4 Se i < n então 
5 aux = vetor[i] 
6 vetor[i] = vetor[n] 
7 vetor[n] = aux 
8 SELECTION_SORT(vetor,n-1) 
 
Divisão e Conquista 
• Complexidade da Ordenação por Seleção 
 
SELECTION_SORT(vetor,n) 
1 Se n = 1 então 
2 Retorne 
3 i = IMAXIMO(vetor,n) 
4 Se i < n então 
5 aux = vetor[i] 
6 vetor[i] = vetor[n] 
7 vetor[n] = aux 
8 SELECTION_SORT(vetor,n-1) 
 
Operação básica? 
Comparações entre 
elementos do vetor 
No pior caso 
n-1 comparações 
Divisão e Conquista 
• Complexidade da Ordenação por Seleção 
 
SELECTION_SORT(vetor,n) 
1 Se n = 1 então 
2 Retorne 
3 i = IMAXIMO(vetor,n) 
4 Se i < n então 
5 aux = vetor[i] 
6 vetor[i] = vetor[n] 
7 vetor[n] = aux 
8 SELECTION_SORT(vetor,n-1) 
 
C(1) = 0 
C(n) = C(n–1) + n–1 
Divisão e Conquista 
• Qual a complexidade do algoritmo SELECTION_SORT(vetor,n)? 
• Resolver a recorrência C(1) = 0 
 C(n) = C(n–1) + n–1 
 
Divisão e Conquista 
– C(1) = 0 
C(n) = C(n–1) + n–1 
 
= C(n–2) + (n–2) + (n–1) 
= C(n–3) + (n–3) + (n–2) + (n–1) 
... após k passos ... 
C(n) = (n–1) + (n–2) + (n–3) + ... + (n–k) + C(n–k) 
Divisão e Conquista 
– C(1) = 0 
C(n) = 
C(n) = (n–1) + (n–2) + (n–3) + ... + (n–k) + C(n–k) 
... para k = n–1, isto é após n–1 passos ... 
... após k passos ... 
C(n) = (n–1) + (n–2) + (n–3) + ... + (n – (n–1)) + C(n – (n–1) ) 
C(n) = (n–1) + (n–2) + (n–3) + ... + 1 + C(1) 
C(n) = (n–1) + (n–2) + (n–3) + ... + 1 
Divisão e Conquista 
• Qual a complexidade do algoritmo SELECTION_SORT(vetor,n)? 
 
 
 
 
C(n) = (n–1) + (n–2) + (n–3) + ... + 3 + 2 + 1 
Resolvendo o somatório (fórmula da P.A.) 
(1 + 𝑛 − 1)(𝑛 − 1)
2
= 
𝑛(𝑛 − 1)
2
= 
𝑛2
2
−
𝑛
2
 C(n) = 
f(n) = O(n2) 
Divisão e Conquista 
• Problema: Ordenação 
– Algoritmo 2: Ordenação por Intercalação (Merge_Sort) 
• Quebrar o vetor em duas partes iguais (de mesmo tamanho) 
• Ordenar cada uma das metades do vetor isoladamente 
• Intercalar as duas metades ordenadas 
Divisão e Conquista 
 
• MERGESORT(v,1,8) 
 
 
 
 
 
 
 
15 3 25 40 31 1 8 5 
15 3 25 40 31 1 8 5 
3 15 25 40 1 5 8 31 
MERGE 
1 3 5 8 15 25 31 40 
• Função Merge 
Divisão e Conquista 
MERGE(L1,L2) { Intercala as listas ordenadas L1 e L2 } 
 
 R =  
 Enquanto L1   ou L2   faça 
 Se L1 =  então 
 R = R + L2[1] 
 L2 = L2 – L2[1] 
 Senão Se L2 =  então 
 R = R + L1[1] 
 L1 = L1 – L1[1] 
 Senão Se L1[1] < L2[1] então 
 R = R + L1[1] 
 L1 = L1 – L1[1] 
 Senão 
 R = R + L2[1] 
 L2 = L2 – L2[1] 
 Retorne R 
• Complexidade da função Merge 
Divisão e Conquista 
MERGE(L1,L2) 
 
 R =  
 Enquanto L1   ou L2   faça 
 Se L1 =  então 
 R = R + L2[1] 
 L2 = L2 – L2[1] 
 Senão Se L2 =  então 
 R = R + L1[1] 
 L1 = L1 – L1[1] 
 Senão Se L1[1] < L2[1] então 
 R = R + L1[1] 
 L1 = L1 – L1[1] 
 Senão 
 R = R + L2[1] 
 L2 = L2 – L2[1] 
 Retorne R 
Operação básica? 
Comparações entre 
 elementos dos vetores 
• Complexidade da função Merge 
– Se |L1| = n1 e |L2| = n2 , então |R| = n1 + n2 
 
a função Merge efetua, no pior caso 
 
 n1 + n2 – 1 comparações. 
• Justificativa 
• No pior caso, cada comparação “leva” um elemento para o vetor R. 
Precisamos então de n1 + n2 comparações, certo? Errado! 
Com n1 + n2 – 1 comparações, resta apenas um elemento a 
ser incluído no vetor R, e não será comparado com ninguém. 
 
Divisão e Conquista 
E no melhor caso? 
min { n1,n2 } comparações 
Divisão e Conquista 
• Ordenação por Intercalação 
 
 
SORT(vetor,ini,fim) { Ordena o vetor[ini..fim] } 
 
1 Se ini = fim então 
2 Retorne 
 
3 meio = (ini+fim) div 2 
 
4 Retorne MERGE( SORT(vetor,ini,meio), SORT(vetor,meio+1,fim) ) 
Divisão e Conquista 
• Complexidade da Ordenação por Intercalação 
 
 
SORT(vetor,ini,fim) { Ordena o vetor[ini..fim] } 
 
1 Se ini = fim então 
2 Retorne 
 
3 meio = (ini+fim) div 2 
 
4 Retorne MERGE( SORT(vetor,ini,meio), SORT(vetor,meio+1,fim) ) 
Operação básica? 
Comparações entre elementos do vetor 
Divisão e Conquista 
• Complexidade da Ordenação por Intercalação 
 
 
SORT(vetor,ini,fim) { Ordena o vetor[ini..fim] } 
 
1 Se ini = fim então 
2 Retorne 
 
3 meio = (ini+fim) div 2 
 
4 Retorne MERGE( SORT(vetor,ini,meio), SORT(vetor,meio+1,fim) ) 
C(1) = 0 
C(n) = 2C(n/2) + n–1 
Merge(L1,L2) = n/2 + n/2 – 1 
comparações 
Divisão e Conquista 
• Exemplo 
n = 8 
SORT(vetor,5,6)
SORT(vetor,5,8)
SORT(vetor,7,8)SORT(vetor,1,2)
SORT(vetor,1,8)
 
SORT(vetor,1,4)
SORT(vetor,1,1)
SORT(vetor,3,4)
SORT(vetor,2,2) SORT(vetor,3,3) SORT(vetor,4,4) SORT(vetor,5,5) SORT(vetor,6,6) SORT(vetor,7,7) SORT(vetor,8,8)
0 0 0 0 0 0 0 0 
1 
Quantas comparações? 
1 1 1 
3 3 
7 
n = 1 
n = 2 
n = 4 
n = 8 
Resposta: 
C(8) = 7 + 2 x 3 + 4 x 1 
 = 17 
Divisão e Conquista 
• Qual a complexidade do algoritmo MERGE_SORT? 
• Resolver a recorrência C(1) = 0 
 C(n) = 2C(n/2) + n–1 
 
Divisão e Conquista 
– C(1) = 0 
C(n) = 2C(n/2) + n–1 
 
= 2[2C(n/4) + (n/2 – 1)] + (n–1) = 
= 4C(n/4) + (n–2) + (n–1) = 
= 4[2C(n/8) + (n/4 – 1)] + (n–2) + (n–1) = 
= 8C(n/8) + (n–4) + (n–2) + (n–1) = 
Divisão e Conquista 
– C(1) = 0 
C(n) = 2C(n/2) + n–1 
 
= 8[2C(n/16)+(n/8 – 1)] + (n–4) + (n–2) + (n–1) = 
... após k passos ... 
= 8C(n/8) + (n–4) + (n–2) + (n–1) = 
= 16C(n/16) + (n–8) + (n–4) + (n–2) + (n–1) 
= 2k C(n/2k) + (n–1) + (n–2) + (n–22) + ... + (n–2k-1) 
Divisão e Conquista 
– C(1) = 0 
C(n) = 2C(n/2) + n–1 
 
 
... após k passos ... 
= 2k C(n/2k) + (n–20) + (n–21) + (n–22) + (n–23) + ... + (n–2k-1) 
= 2k C(n/2k) + kn – ( 20 + 21 + 22 + 23 + ... + 2k-1 ) 
Divisão e Conquista 
– C(1) = 0 
C(n) = 2k C(n/2k) + kn – ( 20 + 21 + 22 + 23 + ... + 2k-1 ) 
Vamos examinar a subexpressão C(n/2k) ... 
Conforme k aumenta, n/2k diminui ... 
Suponha que n seja potência de 2. 
Ou seja, n = 2p, para algum p natural ... 
Exemplo: n = 1024 = 210. 
Neste caso p = 10. 
Divisão e Conquista 
– C(1) = 0 
C(n) = 2k C(n/2k) + kn – ( 20 + 21 + 22 + 23 + ... + 2k-1 ) 
Quando k = p teremos ... 
C(n) = = 2p C(n/2p) + pn – ( 20 + 21 + 22 + 23 + ... + 2p-1 ) 
C(n) = n C(1) + pn – ( 20 + 21 + 22 + 23 + ... + 2p-1 ) 
C(n) = pn – ( 20 + 21 + 22 + 23 + ... + 2p-1 ) 
– C(1) = 0 
C(n) = pn – ( 20 + 21 + 22 + 23 + ... + 2p-1 ) 
 
 
Divisão e Conquista 
Relembrando a fórmulada soma dos k termos iniciais 
de uma PG: 𝑆𝑘 = 𝑎1
𝑞𝑘−1
𝑞−1
 
Nesta PG específica temos 𝑆𝑝 = 2
0 
2𝑝−1
2−1
 = 2𝑝 − 1 = 𝒏 − 𝟏 
C(n) = np – (n–1) 
– C(1) = 0 
C(n) = np – ( 20 + 21 + 22 + 23 + ... + 2p-1 ) 
 
 
Divisão e Conquista 
p = log n 
C(n) = n log n – n + 1 
No exemplo anterior: C(8) = ? 
C(n) = np – (2p–1) = np – (n–1) = n p – n + 1 
Divisão e Conquista 
• Exemplo 
n = 8 
SORT(vetor,5,6)
SORT(vetor,5,8)
SORT(vetor,7,8)SORT(vetor,1,2)
SORT(vetor,1,8)
 
SORT(vetor,1,4)
SORT(vetor,1,1)
SORT(vetor,3,4)
SORT(vetor,2,2) SORT(vetor,3,3) SORT(vetor,4,4) SORT(vetor,5,5) SORT(vetor,6,6) SORT(vetor,7,7) SORT(vetor,8,8)
0 0 0 0 0 0 0 0 
1 
Quantas comparações? 
1 1 1 
3 3 
7 
n = 1 
n = 2 
n = 4 
n = 8 
Resposta: 
C(8) = 7 + 2 x 3 + 4 x 1 
 = 17 
– C(n) = n log n – n + 1 
= 8 x 3 – 8 + 1 = 
Divisão e Conquista 
No exemplo anterior: C(8) = 
= 17 
8 log 8 – 8 + 1 = 
Divisão e Conquista 
• Qual a complexidade do algoritmo MERGE_SORT? 
• Resposta 
– No pior caso 
 
f(n) = n log n – n + 1 comparações 
 
  f(n) = O(n log n) 
 
 
Divisão e Conquista 
• Relembrando, complexidade de pior caso 
 
– BUBBLESORT O(n2) 
– SELECTIONSORT O(n2) 
– MERGESORT O(n log n) 
 
 
• Exercícios 
– Notas de aula, Seção 2.1.4 - Exercícios 
 
Obrigado! 
 
 
Aula 10 
• Principais Técnicas de Projeto de Algoritmos 
– Problemas de Otimização 
– Algoritmo Guloso 
Problemas de Otimização 
• Problema 1 
• De uma turma com n alunos, selecionar r alunos com as melhores médias 
– Solução 1 
– Identificar o aluno de maior média, retirá-lo do conjunto, e adicioná-lo à seleção 
– Repetir o processo r vezes 
• Complexidade: 
– r constante: => O(n) 
– r = f(n) – p.ex. r = n/4 => O(n2) 
 
Problemas de Otimização 
• Problema 1 
• De uma turma com n alunos, selecionar r alunos com as melhores médias 
– Solução 2 
– Ordenar os alunos em valores decrescentes das médias 
– Estratégia gulosa: Selecionar os r alunos iniciais do vetor ordenado 
• Complexidade: 
– O(n log n) 
 
• Vamos complicar um pouco... 
 
Problemas de Otimização 
• Problema da Mochila 
– Um ladrão invade uma residência 
• Vários objetos disponíveis: cada objeto tem um valor 
 cada objeto tem um peso 
• O ladrão carrega uma mochila 
– Capacidade limitada 
• O ladrão quer maximizar seu “ganho” 
• Uma estratégia gulosa funciona? 
– O que é estratégia gulosa? 
Problemas de Otimização 
• Problema da Mochila 
– Entrada 
– Conjunto O com n objetos distintos 
– A cada objeto oi é associado um par (wi, vf), onde wi = peso do objeto, e 
 vi = valor do objeto 
– Um valor wM (capacidade da Mochila) 
– Saída 
– O’  O, contendo alguns dos objetos 
– Somatório dos valores: 𝑣𝑖𝑜𝑖∈O
′ é o máximo possível 
– Somatório dos pesos: 𝑤𝑖𝑜𝑖∈O
′ ≤ 𝑤M 
Algoritmo Guloso 
• Problema da Mochila 
– Instância do problema 
• Entrada 
O = { (4,40), (10,100), (5,50), (3,30), (6,60) } 
n = 5 
wM = 17 
 
• Saída (solução ótima) 
O’ = { o1, o2, o4 } 
Soma dos valores dos objetos selecionados: 170 
Soma dos pesis dos objetos selecionados: 17 
 
o1: w1 = 4 v1 = 40 
o2: w2 = 10 v2 = 100 
o3: w3 = 5 v3 = 50 
o4: w4 = 3 v4 = 30 
o5: w5 = 6 v5 = 60 
Algoritmo Guloso 
• Problema da Mochila 
– Estratégia gulosa 1: objetos de maior valor 
• wM = 17 
 
 
 
 
Resposta: O’ = { o2, o5 } 
 
Valor dos objetos: 160 
 
Solução não é ótima: solução ótima = 170 
o1: w1 = 4 v1 = 40 
o2: w2 = 10 v2 = 100 
o3: w3 = 5 v3 = 50 
o4: w4 = 3 v4 = 30 
o5: w5 = 6 v5 = 60 
Algoritmo Guloso 
• Problema da Mochila 
– Estratégia gulosa 2: objetos de menor peso 
• wM = 17 
 
 
 
 
Resposta: O’ = { o4, o1, o3 } 
 
Valor dos objetos: 120 
 
Solução não é ótima: solução ótima = 170 
o1: w1 = 4 v1 = 40 
o2: w2 = 10 v2 = 100 
o3: w3 = 5 v3 = 50 
o4: w4 = 3 v4 = 30 
o5: w5 = 6 v5 = 60 
Algoritmo Guloso 
• O Algoritmo Guloso não resolve o 
Problema da Mochila 
 
Algoritmo Guloso 
• Problemas de Otimização 
– Entrada 
• Conjunto S, contendo n objetos (p.ex, objetos na residência) 
• Todos os objetos possuem atributos (p.ex., valores e pesos) 
– Saída 
• Subconjunto S’  S, que: i. satisfaça alguma restrição 
 (p.ex., soma dos pesos tem um limite) 
 ii. seja ótimo em relação a algum critério 
 (p.ex., somatório dos valores) 
 
Algoritmo Guloso 
• Algoritmo guloso 
– A cada passo, identificar o elemento mais promissor e adicioná-lo 
à seleção se a restrição for obedecida 
– Como avaliar o elemento mais promissor? 
• Alguma estratégia escolhida de acordo com o critério para otimização 
P.ex., maior valor ou menor peso 
Algoritmo Guloso 
• ATENÇÃO 
– Nem todo problema de otimização é resolvido pelo algoritmo guloso 
• Não existe estratégia gulosa conhecida que resolva o Problema da Mochila 
 
Algoritmo Guloso 
• Algoritmo guloso* 
S =  
Enquanto S   faça 
 Identifique o mais promissor elemento s  S 
 S = S – {s} 
 Se S  {s} atende às restrições do problema então 
 S = S  {s} 
* Antes do laço principal: ordenar S de acordo com 
 a estratégia escolhida 
 
 
Algoritmo Guloso 
• Árvore Geradora (ou de espalhamento) Mínima (ou máxima)* 
– Problema de otimização 
– Entrada 
• Grafo G=(V,E) ponderado e conexo 
– Saída 
• Árvore: subgrafo conexo e acíclico de G 
• Somatório dos pesos da arestas é mínimo (ou máximo) 
 
*Em inglês: Minimum Spanning Tree 
 
 
 
Algoritmo Guloso 
• Árvore Geradora Mínima 
– Minimizar ou maximizar somatório dos pesos 
 
 
b
c
5
a
6
e
f
3
1
6
d
8
4
4
9
3
8
Algoritmo Guloso 
• Árvore Geradora Mínima 
– Estratégia gulosa 
• Aresta de menor peso como a mais promissora 
 
Identificar a aresta e de menor peso do grafo 
Remover e do grafo 
Se e formar um ciclo com as já selecionadas 
 descartar e 
Caso contrário 
 incluir e na seleção 
 
 
 
Algoritmo Guloso 
• Árvore Geradora Mínima 
– Estratégia gulosa: aresta de menor peso 
 
 
 
 
b
c
5
a
6
e
f
3
1
6
d
8
4
4
9
3
8
Solução: 15 
Algoritmo Guloso 
• Árvore Geradora Máxima 
– Estratégia gulosa: aresta de maior peso 
 
 
b
c
5
a
6
e
f
3
1
6
d
8
4
4
9
3
8
Solução: 35 
Algoritmo Guloso 
• O Algoritmo Guloso resolve o problema da 
Árvore Geradora Mínima (ou Máxima) 
Algoritmo Guloso 
• Alocação de Atividades 
– Problema de otimização 
– Entrada 
• Conjunto T com n tarefas disputando um recurso (processador, sala, etc.) 
• Cada tarefa é descrita por (ti, tf), onde ti = hora de início, e 
 tf = hora de término 
– Saída 
• T’  T, contendo tarefas sem interseção de tempo 
• |T’| é o máximo possível (otimizar utilização do recurso) 
 
Algoritmo Guloso 
• Alocação de Atividades 
– Exemplo 
• n = 11 
TAREFA A: (8,11) 
TAREFA B: (0,6) 
TAREFA C: (12,14) 
TAREFA D: (3,5) 
TAREFA E: (8,12) 
TAREFA F: (5,9) 
TAREFA G: (1,4) 
TAREFA H: (2,13) 
TAREFA I: (6,10) 
TAREFA J: (3,8) 
TAREFA K: (5,7) 
Subconjuntos possíveis 
 
T1 = { B,E,C } 
 
T2 = { G,K,A,C } 
 
T3 = { D,K,E,C } 
Algoritmo Guloso 
• Alocação de Atividades 
– Estratégia gulosa 
• As tarefas com menor horário de término tf são as mais promissoras 
– Tarefa com menor tf será incluída em T’ caso não tenha interseção de horário 
com as demais