Organização e Recuperação
da Informação (ORI)
Complexidade de Algoritmos
Existem várias formas de se resolver
um problema e, portanto, várias formas de se construir algoritmos para
resolvê-los.
 Comparações entre soluções
 Métodos para comparações
 Estimativas de tempo...
O que é complexidade?
A complexidade de um algoritmo consiste
na quantidade de "trabalho" necessária
para a sua execução, expressa em função
das operações fundamentais, as quais
variam de acordo com o algoritmo, e em
função do volume de dados.
O que é complexidade?
• Ou seja, normalmente, programas demoram
mais para executar de acordo com sua
estruturação de instruções e na medida em que
se aumenta a quantidade de dados de entrada.
• Esta
“demora”
pode
ser
linearmente
proporcional, quadrática...
• Em alguns casos, o tempo de execução não
depende somente da quantidade de dados,
mas sim de sua forma.
Para que?
Para permitir a comparação teórica de
soluções diferentes para o mesmo
problema e identificar as melhores
soluções (eficiência).
Exemplo
Suposição: uma operação leva 1 ms para
ser efetuada. A tabela a seguir apresenta
o tempo necessário p/ resolver um mesmo
problema de cinco maneiras diferentes.
Podemos pensar no “conceito” T(n), que é
apresentado na tabela, como sendo o
número de comandos executados por um
programa (Pascal, C, ...).
Tabela
T(n)
n
A1
A2
A3
A4
A5
n
n log n
n2
n3
2n
16
0.016s 0.064s 0.256s
4s
1m4s
32
0.032s
0.16s
33s
46 dias
512
0.512s
9s
1s
4m22s 1dia +
13h
1037
séculos
Conceitos
• Benchmark (prática)
– Quando se compara 2 ou mais programas projetados
para resolver a mesma tarefa, normalmente um
conjunto padrão de dados é reservado para avaliar o
desempenho da solução. Isso significa que este
conjunto deve ser representativo do universo de
dados aos quais o programa estará exposto e pode
servir como referência de teste para outras soluções.
• Análise (teórica)
• Exemplos : reconhecimento de face, fala...
Consideração sobre Benchmark
Supondo que tenhamos escrito, depurado
e testado um programa e que tenhamos
selecionado um particular conjunto de
dados de entrada para executa-lo. Ainda
assim, dependemos da configuração do
computador a ser utilizado e da eficiência
do compilador.
Tipos de complexidade
Espacial  memória
Temporal  tempo
(a) tempo real
(b) número de instruções
Regra 90-10
• Muitos programas executam um pequeno
conjunto de instruções muitas vezes (90%
do tempo de execução em 10% do
código).
Perspectivas de análise
• Pior caso
• Caso médio
• Melhor caso
Perspectivas de análise
Pior caso
Este método é normalmente representado por
O ( ). Por exemplo, se dissermos que um
determinado algoritmo é representado por g(x)
e a sua complexidade no pior caso é n, será
representada por g(x) = O(n).
Consiste, basicamente, em assumir o pior dos
casos que podem acontecer, sendo muito
usado e sendo normalmente o mais fácil de se
determinar.
Perspectivas de análise
Caso médio
Representa-se por θ().
Este método é, dentre os três, o mais
difícil de se determinar pois necessita de
análise estatística (muitos testes). No
entanto, é muito usado pois é também o
que representa mais corretamente a
complexidade do algoritmo.
Perspectivas de análise
Melhor caso
Representa-se por Ω ( )
Método que consiste em assumir que vai
acontecer o melhor. Pouco usado. Tem
aplicação em poucos casos.
Limite Superior
Seja dado um problema, por exemplo, multiplicação de duas
matrizes quadradas de ordem n (n*n). Conhecemos um algoritmo
para resolver este problema(pelo método trivial) de complexidade
O(n3). Sabemos assim que a complexidade deste problema não
deve superar O(n3), uma vez que existe um algoritmo desta
complexidade que o resolve. Um limite superior ( upper bound )
deste problema é O(n3). O limite superior de um algoritmo pode
mudar se alguém descobrir um algoritmo melhor. Isso de facto
aconteceu com o algoritmo de Strassen que é de O(n log 7). Assim o
limite superior do problema de multiplicação de matrizes passou a
ser O (nlog 7). Outros pesquisadores melhoraram ainda mais este
resultado. Atualmente, o melhor resultado é o de Coppersmith e
Winograd de O (n 2.376).
O limite superior de um algoritmo é parecido com o record mundial
de uma modalidade de atletismo. Ele é estabelecido pelo melhor
atleta ( algoritmo ) do momento. Assim como o record mundial o
limite superior pode ser melhorado por um algoritmo ( atleta ) mais
veloz.
Limite Inferior
Às vezes é possível demonstrar que para um dado problema, qualquer que
seja o algoritmo a ser usado o problema requer pelo menos um certo
número de operações. Essa complexidade é chamada Limite inferior
(Lower Bound). Veja que o limite inferior dependo do problema mas não do
particular algoritmo. Usamos a letra Ω em lugar de O para denotar um
limite inferior.
Para o problema de multiplicação de matrizes de ordem n, apenas para ler
os elementos das duas matrizes de entrada leva O(n2). Assim uma cota
inferior trivial é Ω(n2).
Na analogia anterior, um limite inferior de uma modalidade de atletismo
não dependeria mais do atleta. Seria algum tempo mínimo que a
modalidade exige, qualquer que seja o atleta. Um limite inferior trivial para
os 100 metros seria o tempo que a velocidade da luz leva a percorrer 100
metros no vácuo.
Se um algoritmo tem uma complexidade que é igual ao limite inferior do
problema então o algoritmo é ótimo.
O algoritmo de CopperSmith e Winograd é de O(n2.376) mas o limite inferior
é de Ω(n2). Portante não é ótimo. É possível que este limite superior possa
ainda ser melhorado.
Comparando
Tempo Tam. A Tam.
B
1s
10
22
T(n)=2n2
T(n)=10n
10s
100
70
100s
1.000
223
1.000s 10.000 707
Teoria
Seja T(n) o tempo de execução de um
programa, medido em função do tamanho do
conjunto de entrada n.
 n é um valor não negativo
 T(n) é um valor não negativo V n
Seja f(n) outra função também definida no
conjunto dos inteiros não negativos. Se T(n) é
no máximo uma constante vezes f(n) – excetuandose, possivelmente, alguns valores pequenos de n – pode-se
dizer que T(n) é O(f(n)).
Teoria
• Definição formal
– T(n) é O(f(n)) se existe um inteiro n0 e uma
constante c (c > 0) | V n > n0  T(n) ≤ c. f(n)
Exemplo
Suponha que tenhamos um programa que tenha
os seguintes tempos de execução:
T(0) = 1; T(1) = 4; T(2) = 9
em geral podemos resumir em T(n)=(n+1)2
Assim, teríamos que T(n) é O(n2)
Prova: Pela definição tem-se que se
escolhermos uma constante c e um valor n0 tais
que T(n) ≤ c . n2, então T(n) será O(n2).
Para c = 4 e n0 > 1 temos esta relação.
Exemplo
função f(n)=(n+1)2
n2 + 2.n + 1 ≤ n2 + 2.n2 + n2
≤ 4 . n2
Princípios Gerais
1. Constantes não são importantes
Se T(n) é O(d .T(n)) para qualquer d > 0
e se
n0 = 0 e c ≥ 1/d
Então
T(n) ≤ c . (d . T(n))
≤ c . d . T(n)
≤ 1 . T(n)
Princípios Gerais
2. Termos de ordem menor não são importantes.
Seja T(n) um polinômio da forma:
ak.nk + ak-1.nk-1 + ... + a1.n + a0 (ak>0)
Seja n0 = 1 e c = ∑ ai
se ai > 0
 T(n) não é superior a c.T(n)
Exemplo: 2 . n3 é O (0.001 . n3)
Seja
n0 = 0 e c = 2 / 0.001 (2000)
2.n3 ≤ 2000 . (0.001 . n3)
≤ 2 n3
Princípios Gerais
Outro exemplo:
T(n) = 3 . n5 + 10 . n4 – 4 . n3 + n + 1
3.n5 + 10.n4 – 4.n3 + n + 1 ≤ 3.n5 + 10.n5 + n5 + n5
≤ 15 n5
Constatando através das proporções...
3 n2 + 10 n + 10 é O(n2)
p/ n = 10
 73.2%; 24.4% e 2.4%
p/ n = 100
 96.7%; 3.2%; ...
Princípios Gerais
A eliminação de elementos de menor
ordem é conseqüência do fato de que o
que é realmente importante é a taxa de
crescimento e não o valor exato de T(n).
Desta forma, T(n) = 2n + n3 tem como
resultado a avaliação de que T(n) = O(2n)
pois n3/2n tende a zero à medida que n
cresce.
Princípios Gerais
T(n) = 2n + n3 tem como resultado a avaliação
de que T(n) = O(2n)
Prova: Seja n0=10 e c = 2. Deve-se provar que
para n ≥ 10 tem-se que 2n + n3 ≤ 2. 2n
Subtraindo-se 2n de ambos os lados temos: n3 ≤
2n (2 – 1)
Para n = 10 tem-se que
210 = 1024
103 = 1000
Princípios Gerais
Tabela
O(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
Constante
Logarítmica
Linear
n log n
Quadrática
Cúbica
Exponencial
Princípios Gerais
A relação de big-oh (O) é importante para
se estabelecer a relação de ≤ entre as
funções. Existem outras definições dentro
da análise de algoritmos que apresentam
outras relações.
Analisando tempo de execução
Comandos simples
 atribuição, leitura, escrita... O(1)
Exemplo:
a1
leia (x)
escreva (z)
Analisando tempo de execução
Repetições
 Os limites superiores (loops determinados)
indicam o limite superior do número de vezes que os
comandos dentro do loop serão repetidos.
Exemplo 1:
Para j  1 até n faça
a[j]  j
Como atribuição é O(1) tem-se: n . O(1) = O(n)
Exemplo 2:
Para i  1 até n faça
Para j  1 até n faça
a[i][j]  i*j
Como atribuição é O(1) tem-se: n . O(1) = O(n)
Como tem-se outro loop (externo): n . O(n) = O(n2)
Analisando tempo de execução
Repetições (while e repeat)

Não
têm
limite
superior
(indeterminado). Deve-se detectar um
limite superior (pior caso).
Exemplo 1: i  1
Enquanto i <> a[i] faça
ii+1
O(n)
Analisando tempo de execução
Comandos condicionais
 Normalmente o comando condicional é O(1) – a menos que
tenha uma chamada de função. Assim, as partes então e senão do
comando devem ser analisadas individualmente e uma estimativa
deve ser atribuída ao conjunto.
Exemplo 1: Se a[1][1] = 0 então
Para i  1 até n faça
Para j  1 até n faça
a[i][j]  i*j
senão
Para j  1 até n faça
a[i][j]  10
Quando não se tem idéia do que acontecerá  assumir pior caso
Analisando tempo de execução
Procedimentos
Se todos os procedimentos são não
recursivos, pode-se começar a computar o
tempo de todo o programa à partir dos
procedimentos que não chamam outros.
Parte-se, então, para aqueles que utilizam
os procedimentos cujos valores já foram
calculados... E assim por diante...
Analisando tempo de execução
Procedimentos Recursivos
Análise um pouco mais difícil.
função fatorial (n)
O(1)
se n ≤ 1 então
fatorial  1
senão
fatorial  n . fatorial (n-1)
2.O(1) + O(n-1)
Analisando tempo de execução
Indução T(n) = O(1) + T(n-1)
Caso base : T(1) = O(1) = a
O(1)
Indução: T(n) = b + T(n-1)
T(2) = b + T(1) = b + a
T(3) = b + T(2) = b + b + a = 2.b + a
T(4) = b + T(3) = b + 2.b + a = 3.b + a
...
T(n) = (n-1).b + a
Analisando tempo de execução
Substituição repetida
T(m) = b + T(m-1) m > 1
T(n) = b + T(n-1)
T(n-1) = b + T(n-2)
...
T(2) = b + T(1)
T(1) = a
Analisando tempo de execução
Substituição repetida
T(n-1)
T(n-2)
T(n) = b + b + T(n-2)
T(n-3)
T(n) = b + b + b + T(n-3)
T(n) = b + b + b + b + T(n-4)
T(n) = 3.b + T(n-3) ou 4.b + T(n-4)
...
T(n) = (n-1).b + T(n-(n-1)) = (n-1).b + a
Classificação e Pesquisa
Métodos de Classificação
Bolha
Inserção
Quicksort
Mergesort
Pesquisa
Seqüêncial
Binária
Classificação - bolha
O algoritmo da bolha, ou em Inglês,
Bubblesort, efetua a ordenação através
de trocas entre pares de números
sucessivos.
Classificação - Bolha
25 57 48
37
12
25 57
48
37 12 92
86 33
25 57
48
37 12 92
86 33
25 48
57
37 12 92
86 33
25 48
57
37 12 92
86 33
25 48
37
57 12 92
86 33
25 48
37
57 12 92
86 33
25 48
37
12 57 92
86 33
25 48
37
12 57 92
86 33
25 48
37
12 57 86
92 33
25 48
37
12 57 86
92 33
25 48
37
12 57 86
33 92
92
86
33
Classificação - bolha
Algoritmo
Para passo  1 até n-1 faça
Para pos  1 até n-1 faça
Se x[pos] > x [pos+1] então
troca(x[pos],x[pos+1])
Fim_se
Análise:
(n-1) . (n-1) = n2 + 2.n + 1  O(n2)
Classificação - Inserção
O algoritmo de ordenação por inserção é bastante
simples e eficiente para uma quantidade pequena de
números. A idéia de funcionamento é semelhante ao
ordenamento de cartas de baralho na mão de um
jogador. A mão esquerda começa "vazia" e a mão direita
insere uma "carta" de cada vez na posição correta. Ao
final, quando todas as "cartas" foram inseridas, elas já
estão ordenadas. Para encontrar, durante a inserção, a
posição correta para um valor, compara-se este valor
um-a-um com as cartas já na mão esquerda, até
encontrarmos a posição correta.
Exercício: fazer o algoritmo
Classificação – mergesort
A idéia de “aceleração” por trás do
algoritmo de Mergesort (e também do
Quicksort) é que é mais rápido ordenar 2
seqüências de n/2 números do que uma
seqüência de n números (dividir p/
conquistar). A complexidade do Mergesort
é proporcional a n . log n, onde log n é o
logaritmo de base 2 do número n.
Classificação – mergesort
Neste algoritmo, recursivamente, divide-se a
seqüência de números a ser ordenada em 2
subseqüências. Ordena-se cada uma delas e,
posteriormente, combinam-se os resultados.
Classificação – mergesort
Mergesort(vetor a[]; inteiro p, r)
Inicio
Se (p < r) então
q  (p + r) / 2;
mergesort(a, p, q)
mergesort(a, q+1, r);
unir(a, p, q, r);
Fim_se
Fim
Classificação - Quicksort
Quicksort é na maioria das vezes a melhor
opção prática para ordenação porque ele
é muito eficiente na média. O tempo
esperado de execução também é
proporcional a n . log n
Classificação - Quicksort
procedimento QuickSort (vetor A; inteiros p, r)
Inteiro q
Inicio
Se p < r então
Inicio_se
q  particionar(A,p,r)
QuickSort(A,p,q)
QuickSort(A,q+1,r)
Fim_se
Fim
Classificação - Quicksort
A parte não-trivial do Quicksort é a função
particionar que divide o vetor original em
2 sub-vetores de maneira que o primeiro
não contenha nenhum valor maior do que
o segundo.
Classificação - Quicksort
Para ordenar um array A[p..r] o procedimento é
o seguinte:
– O vetor A[p..r] é dividido em 2 sub-vetores A[p..q] e
A[q+1..r] de tal forma que cada elemento de A[p..q]
é menor ou igual a cada elemento de A[q+1..r]. O
índice q é calculado como parte deste procedimento
de divisão;
– Os 2 sub-vetores A[p..q] e A[q+1..r] são ordenados
através de chamadas recursivas ao Quicksort.
Classificação - Quicksort
Exemplo (p=1 e r=8).
8 2 5 7 1 -3 4 12 22 15 9
• Elegemos (arbitrariamente) o primeiro
elemento do vetor (neste caso o valor 8)
para ser o “pivô". Com isso temos dois
novos subvetores:
2 5 7 1 -3 4 8 e 12 22 15 9
• Neste exemplo a função particionar
retornaria q=7 (o índice no vetor onde
terminou o primeiro subvetor).
Classificação - Quicksort
n
2. n/2
h
4. n/4
8. n/8
Deve-se repetir o processo de ordenação dos n elementos h vezes (altura da
árvore binária). h = log n
Pesquisa
• Sequencial
• Binária