Introdução à
complexidade de
algoritmos
Luiz Gonzaga da Silveira Junior
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:


Programador mais ansioso do mundo:


Ordenação (inserção) 2n2 instruções para ordenar n
números no CompA
Programador mais relaxado do mundo:


CompA é 100x mais rápido do que CompB
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
Problemas









Ordenação
Busca
Armazenamento
Desempenho (perfilação)
Corretude (depuração)
Compressão
Transmissão
Renderização
Visualização
Ordenação



Ordenar buscar!
Exercício:
Escreva uma função que verifique se um
vetor v[0..n-1] está em ordem crescente.
Resposta: ...
Comparação
http://cg.scs.carleton.ca/~morin/misc/s
ortalg/
Um pouco de noção de
complexidade

Ao ver uma expressão como n+10 ou n2+1, a
maioria das pessoas pensa automaticamente
em valores pequenos de n, valores próximos
de zero.


Vamos 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;
}
}
Exercício
1.
2.
Que acontece se trocarmos
"for (j = 1" por "for (j = 0"
no código da função inserção?
Que acontece se trocarmos
"v[i+1] = x" por "v[i] = x"
no código da função inserção?
Observação sobre estabilidade



Um algoritmo de ordenação é estável
(= stable) se não altera a posição relativa de
elementos com mesmo valor.
Por exemplo:
se o vetor v[0..n-1] tiver dois elementos
iguais a 222, um algoritmo de ordenação
estável mantém os valores nas posições
originais.
O algoritmo de inserção é estável? Senão
como torná-lo estável.
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!
Outros


Pesquisar e mostrar!
Ver página do curso!

Vou colocar um algoritmo para cada aluno
estudar e explicar na próxima aula!