Algoritmos e Estrutura de
Dados: Uma pequena motivação
Luiz Gonzaga da Silveira Jr
[email protected]
Cenário visionário
• Suponha que os computadores fossem
infinitamente rápidos, com memória infinita. Você
precisaria estudar algoritmos?!
• Me dê 2 razões...
• Demonstrar que o método de sua solução termina, e,
• o faz com a resposta correta!
• Se todos os métodos estivessem corretos, você
escolheria o método mais fácil de implementar...
• Mas o mundo perfeito não existe: velocidade
infinita e memória grátis...
Eficiência: Caso
• Computador A: 1 bilhão de instruções/sec
• Computador B: 10 milhões de instruções/sec
• Conclusão:
•
CompA é 100x mais rápido do que CompB
• Programador mais ansioso do mundo:
• Ordenação (inserção) 2n 2 instruções para ordenar n números
no CompA
• Programador mais relaxado do mundo:
• Ordenação (intercalação) 50 n log n instruções para ordenar n
números no CompB
• Para ordenar 01 milhão de números:
• CompA: ~2000 segundos
• CompB: ~100 segundos
• CompB executou 20x mais rápido do que o CompA
Alguns problemas
• Ordenação
• Busca
• Armazenamento
• Compressão
• Transmissão
• Descompressão
Parâmetros de qualidade
• Corretude (depuração)
• Desempenho (perfilação)
Ordenação
• Ordenar buscar!
• Exercício 1:
Uma função que verifique se um vetor v[0..n1] está em ordem crescente.
• Exercício 2:
Uma função que busque a ocorrência de um
valor em um vetor v[0..n-1]
• Exercício 3:
Uma função que ordene um vetor com N
elementos.
• Comparação
http://cg.scs.carleton.ca/~morin/misc/sortalg/
Qual a complexidade destas funções
para as soluções encontradas?!
• Melhor caso?
• Pior caso?
• Caso médio?
Um pouco de noção de complexidade
• Ao ver uma expressão como n+10 ou n 2+1, a
maioria das pessoas pensa automaticamente
em valores pequenos de n, valores próximos
de zero.
• Testar: para n=2, n=3,n=4, n=10, n=100
• A análise de algoritmos faz exatamente o
contrário: ignora os valores pequenos e
concentra-se nos valores enormes de n.
Algumas funções
• Observemos as seguintes funções:
n2 , (3/2)n2,9999n2, n2/1000, n2+100n
• Quem cresce mais rápido?! (claro, para valores enormes
de n): vamos experimentar!
• Resposta:
• Todas têm crescimentos equivalentes
• Crescimento assintótico!
• Nessa “matemática”, as funções são classificadas em
ORDENS.
• Funções de mesma ordem são ditas equivalentes.
• As funções acima pertencem a mesma ordem
Ordem O (Big-Oh)
• Segundo Knuth, “O” trata-se do ômicron grego
maiúsculo.
• Definição:
Dadas funções assintoticamente não-negativas f e g,
dizemos que f está na ordem O de g, e escrevemos
f = O(g), se f(n) ≤ c · g(n) para algum c positivo
e para todo n suficientemente grande.
• Em outras palavras, existe um número positivo c e
um número N tais que f(n) ≤ c · g(n) para todo n
maior que N.
• Exemplo: Se f(n) ≤ 9999 g(n) para todo n ≥ 1000
então f = O(g). (Mas cuidado: a recíproca não é
verdadeira!)
Exemplo
• Dadas as funções:
f(n) = (3/2)n2 + (7/2)n – 4 e que g(n) = n2.
n
0
1
2
3
4
5
6
7
8
f(n)
–4
1
9
20
34
51
71
94
120
g(n)
0
1
4
9
16
25
36
49
64
• A tabela sugere que f(n) ≤ 2g(n) para n ≥ 6 e
portanto parece que f(n) = O(g(n)).
Bubblesort: intuitivo, porém...!
bubbleSort( A : lista )
do
swapped := false
for each i in 0 to length( A ) - 2 do:
if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] )
swapped := true
end if end
for while swapped
end
Implementação Alternativa
bubbleSort( A : lista )
n := length( A ) - 1
do
swapped := false
n := n - 1
for each i in 0 to n do:
if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] )
swapped := true
end if
end for
while swapped
end
Qual a diferença
entre as duas
implementações?
Análise de complexidade
• Para uma lista de n elementos
• Pior caso: O(n2)
• Melhor caso: O(n)
• Posição dos elementos na lista define eficiência do
algoritmo 
• Para grande quantidade de dados: ineficiente!
• Na prática:
• Simples (entender e implementar)
• Aceitável para n pequeno!
Inserção
• Analogia: cartas do baralho!
• Funcionamento: mão esquerda vazia...cartas pra
baixo, retira carta da mesa e vai inserindo
5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6
• Complexidade
• Melhor caso:O(n)!
• Pior caso:O(n2)
Implementação
void insercao (int n, int v[])
{
int j, i, x;
for (j = 1; j < n; j++)
{
x = v[j];
for (i = j-1; i >= 0 && v[i] > x; --i)
v[i+1] = v[i];
v[i+1] = x;
}
}
Algoritmo de seleção
void selecao (int n, int v[ ])
{
int i, j, min, x;
for (i = 0; i < n-1; ++i)
{
min = i;
for (j = i+1; j < n; ++j)
if (v[j] < v[min])
min = j; x = v[i];
v[i] = v[min];
v[min] = x;
}
}
Complexidade: O(n2)
Quicksort
•
Inventado por C.A.R. Hoare , em 1962.
•
Estratégia: dividir e conquistar!
•
Idéia: Dividir a lista em 2 sublistas
•
Atividade:
• Pesquisar o funcionamento do algoritmo!
• Implementar para um conjunto de valores inteiros contidos no site
• Medir tempo!
Complexidade na prática
• Considerações:
• Tamanho do conjunto
• Considerar usar algoritmos mais eficientes para
grandes conjuntos
• Natureza dos dados (repetidos, já ordenados ou
praticamente ordenados,…)
• Se 2 algoritmos tem mesma complexidade, qual
utilizar?!
Busca
Problema
• Determinar se um dado número está ou não
está em um dado vetor ordenado.
• Mais precisamente, dado um número x e um
vetor crescente v[0..n-1], encontrar um
índice m tal que v[m] == x.
• É claro que o problema pode não ter
solução. Este é o caso, por exemplo, se o
vetor é vazio, ou seja, se n vale 0.
• Ex:
111 222 444 444 555 555 666 888 888 888 999 999
Solução 1: óbvia e lenta
•
Comecemos com um algoritmo simples e óbvio:
A função abaixo recebe um número x e um vetor // crescente v[0..n-1].
Ela devolve um índice m // em 0..n-1 tal que v[m] == x.
• Se tal m não existe, // a função devolve -1. int buscaSequencial (int x,
int n, int v[]) { int m = 0; while (m < n && v[m] < x) ++m; if (m < n &&
v[m] == x) return m; else return -1; }
Busca seqüencial
•
Comecemos com um algoritmo simples e óbvio:
•
// A função recebe um número x e um vetor // crescente v[0..n-1].
• Ela devolve um índice m tal que v[m] == x.
• Se tal m não existe, a função devolve -1.
int buscaSequencial (int x, int n, int v[])
{
int m = 0;
while (m < n && v[m] < x)
++m;
if (m < n && v[m] == x)
return m;
else return -1;
}
Busca binária
int buscaBinaria (int x, int n, int v[])
{
int e, m, d;
e = 0; d = n-1;
while (e <= d) {
m = (e + d)/2;
if (v[m] == x)
return m;
if (v[m] < x)
e = m + 1;
else d = m - 1;
}
return -1;
}
Info importante
Diminuição o espaço de
busca!
Falamos sobre estruturas…
• Listas, vetores…indistintamente
• Qual o papel destas estruturas nos
processos de ordenação e busca?!
Java:
Vector, ArrayList, LinkedList,…