Complexidade de Algoritmos-Tema 1

Prévia do material em texto

Complexidade de Algoritmos
Aula 1
• Conceitos básicos
 - Algoritmo
 Definição
– Problema computacional
• Definição
• Instância de um problema
• Tamanho da entrada 
• Exemplos
 --Função da Análise de Complexidade de Algoritmos
 . Problemas e seus Algoritmos
 . Exemplo de Comparação: Cramer x Gauss (Empírica)
 
 
 
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 (resultado) correspondente à entrada fornecida
Como gerar a saída? Resposta : Algoritmo 
ENTRADA 
(TAMANHO N)
ALGORITMO SAÍDA
MUITAS VEZES HÁ MAIS DE UM ALGORITMO POSSÍVEL PARA RESOLVER O PROBLEMA
Exemplo de Problema Computacional e Algoritmo
• Problema : Dado n ,calcule a soma de cubos = 1³ + 2³ + 3³ + … + n³ 
ENTRADA 
(n) ALGORITMO
SAÍDA
1³ + 2³ + 3³ + … + n³ 
ALGORITMO :
(Desconsidere 
Declarações de 
Variáveis e leitura da 
entrada n)
Definição de Problema Computacional
• Tamanho da entrada 
– Parâmetro numérico que descreve sua magnitude
– Pode ser o n de uma soma ou produto de 1 a n
. Exemplo : Dado n encontrar 1³ + 2³ +3³ + … + n³
– Dado n Encontrar fatorial de n= 1 x 2 x 3 x...x n
– Pode ser n-ésimo valor de uma sequência . (Tamanho n)
• 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.
 Resolver um sistema AX=b com A matriz quadrada tamanho m x m
 e vetor b de tamanho m (Sistema Tamanho n = m*m +m = m * (m+1) 
 Chama-se Sistema de Ordem m )
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 0
–Nome: Calcular 1³ + 2³ +3³ + … + n³
– Entrada: n (valor inteiro: n > 0)
– Tamanho: n 
– Saída: 1³ + 2³ +3³ + … + n³
Problema Computacional
• Exemplo 0: Calcular 1³ + 2³ +3³ + … + n³
• Instância do problema
– Entrada: 3 
– Tamanho: 3 
– Saída: 1³ + 2³ + 3³ = 36
Problema Computacional
• Exemplo 1
–Nome: Calcular o n–ésimo termo da sequência 
de Fibonacci
– Entrada: n (valor natural: n ≥ 0)
– Tamanho: n 
– Saída: F(n)
F = 0, 1, 1, 2, 3, 5, 8, 13, 21, 
Problema Computacional
• Exemplo 1: calcular o n–ésimo termo da sequência 
de Fibonacci
• Instância do problema
– Entrada: 8 
– Tamanho: 8 
– Saída: 21
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){ vetor[1..n] }
{ n: número de elementos }
– Saída: vetor ordenado
Problema Computacional
• Exemplo 2: Ordenação
• Instância do problema
– Entrada: ( [13, 40, 8, 30, 9, 15, 2])
– 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, 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], 25)
Tamanho: 7 Saída: 3
2. Entrada: ( [15, 3, 25, 40, 31, 2, 8], 29)
Tamanho: 7 Saída: 0
3. Entrada: ( [2, 3, 8, 15, 25, 31, 40], 25)
Tamanho: 7 Saída: 5
Problema Computacional
• Exemplo 4
– Nome: Busca ordenada (em um vetor ordenado )
– Tamanho: n
– Entrada: (vetor, 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], 25) 
Tamanho: 7 Saída: 5
2. Entrada: ( [2, 3, 8, 15, 25, 31, 40], 29) 
Tamanho: 7 Saída: 0
Exemplo de Problema Computacional
• Exemplo 5: Resolução de Sistemas Lineares:
ENTRADA 
 
TAMANHO m * (m + 1)
ALGORITMO
SAÍDA
SOLUÇÃO 
Vetor X 
de tamanho m
AX=b
Exemplo de Instância do Problema 
• Exemplo 5 : Resolva o Sistema Linear:
ENTRADA 
Tamanho 3 x 4=12
(Ordem 3) ALGORITMO
SAÍDA
SOLUÇÃO
(x,y,z)=(1,2,3)
Vetor de tamanho 3
 
Matriz A|b = [
1 2 1 8
2 −1 1 3
3 1 −1 2]
A
b
FUNÇÃO DA ANÁLISE DE 
COMPLEXIDADE DE ALGORITMOS
ENTRADA 
(TAMANHO N)
ALGORITMOS
SAÍDA 
(A MESMA PARA TODOS OS ALGORITMOS)
MUITAS VEZES HÁ MAIS DE UM ALGORITMO POSSÍVEL PARA RESOLVER O PROBLEMA
- Verificar se um algoritmo é viável para um Problema Computacional 
 (Tempo ou Espaço de Memória de tamanho razoável para determinado N) 
- Comparar Algoritmos Diferentes para o mesmo problema e ver quais são mais eficientes
 para determinados valores de N
Problemas e Algoritmos
• Problema: Busca não ordenada
Algoritmos : Busca sequencial
• Problema: Busca ordenada
Algoritmos: Busca sequencial, Busca binária
• Problema: Ordenação
Algoritmos: Bolha, Seleção, Inserção, Quick, Merge, Heap, 
Counting, Radix
. Problema: Resolver Sistema Linear Ax=b
 Algoritmos : Cramer , Gauss
MUITAS VEZES HÁ MAIS DE UM ALGORITMO POSSÍVEL PARA RESOLVER UM PROBLEMA
Exemplo de Problema Computacional
• Exemplo 5: Resolver Sistema:
ENTRADA 
 
TAMANHO m X (m + 1)
(Ordem m)
ALGORITMO
CRAMER
OU
GAUSS
SAÍDA
SOLUÇÃO 
Vetor X 
de tamanho m
AX=b
Exemplo de Instância do Problema 
• Resolva o Sistema:
ENTRADA 
Tamanho 3 x 4=12
(Ordem 3)
ALGORITMO
CRAMER
OU
GAUSS
SAÍDA
SOLUÇÃO
(x,y,z)=(1,2,3)
 
Matriz A|b = [
1 2 1 8
2 −1 1 3
3 1 −1 2]
A
b
ALGORITMO 1 - CRAMER
CÁLCULO DE DETERMINANTES DAS MATRIZES
Dando respectivamente os valores D=15 ,Dx=15,Dy=30 e Dz=45. 
 (ver detalhes em https://brasilescola.uol.com.br/matematica/regra-cramer.htm)
Logo x = Dx/D = 15/15 = 1 
 y = Dy/D =30/15 = 2
 Z = Dz/D = 45/15 = 3
https://brasilescola.uol.com.br/matematica/regra-cramer.htm
ALGORITMO 2 - GAUSS
Logo sistema original vira 
 -3z = -9 z = 3 
TRANSFORMAÇÃO DA MATRIZ A|b EM MATRIZ TRIANGULAR SUPERIOR
A|b = [
1 2 1 8
2 −1 1 3
3 1 −1 2] [
1 2 1 8
0 −5 −1 −13
0 0 −3 −9 ]
{
x+2 y+ z=8
0 x−5 y−z=−13
0 x+0 y−3 z=−9
Transformações
-5 y -3 = -13 y = 2 
X + 2 * 2 + 3 =8 x = 1 
COMPARAÇÃO CRAMER X GAUSS (EMPÍRICA)
Ordem
Gauss mais eficiente que 
Cramer (mais rápido) 
Cramer Viável para 
Sistemas de Ordem <=10
Cramer Inviável para 
Sistemas de Ordem = 20
Gauss Viável para 
Sistemas de Ordem = 20
Obs : SuperComputador
Ordem 20 Cramer :28 anos 
COMPARAÇÃO CRAMER X GAUSS (EMPÍRICA)
Ordem
 
Esta Comparação só é válida para um 
computador e depende do Algoritmo estar 
implementado em uma Linguagem de 
Programação neste computador para medir só 
nele
No curso será visto como Analisar 
Complexidade Independente do Computador 
só pelo pseudocódigo do Algoritmo. (Sem 
precisar da implementação)
	Slide 1
	Slide 2
	Aula 1
	Problema Computacional
	Slide 5
	Slide 6
	Definição de Problema Computacional_clipboard0
	Instância de um Problema
	Problema Computacional_clipboard0Problema Computacional
	Slide 11
	Slide 12
	Problema Computacional_clipboard1
	Problema Computacional
	Problema Computacional
	Problema Computacional
	Problema Computacional
	Problema Computacional
	Definição de Problema Computacional
	Slide 20
	Slide 21
	Problemas e Algoritmos
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28