Como analisar um
algoritmo
AULA 2
Profa. Sandra de Amo
Disciplina: Análise de Algoritmos
BCC - UFU
Análise de um Algoritmo
O que é analisar um algoritmo ?
Determinar sua eficiência
 quanto ao tempo de execução
 quanto à quantidade de memória utilizada para
executar o algoritmo
Modelo para a Análise da complexidade: Modelo
RAM (Random Access Machine)
 Operações executadas em sequência
 Não há execuções simultâneas
Análise de um Algoritmo
Input = x
Tamanho de x = n
T(n) = tempo que o algoritmo leva para parar ao ser executado no input de
tamanho n.
T(n) = número de operações atômicas realizadas pelo algoritmo até parar
multiplicado pelo tempo de cada operação atômica.
Operações atômicas = custo em tempo é constante
Objetivo:

Avaliar como cresce T(n) à medida que n cresce.

Que operações atômicas considerar no cálculo de T(n) ?
Que operações atômicas ?



Operações aritméticas
 Soma, subtração, multiplicação, divisão,
resto, piso, teto
Movimentação de dados:
 Carregar, armazenar, copiar
Controle
 Desvio condicional e incondicional
 Chamada e retorno de subrotinas
T(n)

T(n)
T(n) = an + b
n


T(n)
T(n) = an2
T(n) = a2n
n
T(n)
n
Exemplo: Algoritmo Insert-Sort para o
problema de ordenação de sequências
Problema: (Ordenação de uma sequência)
Input: sequência de n números A = <a1,...,an>
Output: B = <b1,...,bn>, onde B é uma
permutação de A e b1≤ b2 ≤ ... ≤ bn
Projeto de um Algoritmo
Ideia
1.
2.
3.
4.
5.
6.
Para j = 2,..., n
Carta-chave = carta da posição j
Faça CHAVE = valor da posição j
Enquanto CHAVE < valor da posição anterior
(Compara CHAVE com os valores das posições anteriores a j
até encontrar posição adequada onde inserir a carta-chave)
Troca valor da posição anterior com o valor da chave
(saida do loop) Quando CHAVE >= valor da posição
anterior
Insere carta-chave em frente da posição correta encontrada
Ideia traduzida em pseudo-código
Insertion-Sort (A)
1.
2.
3.
4.
5.
6.
7.
Entrada : A = array [a1,...,an]
For j  2 to n
do chave  A[j]
ij–1
While i > 0 e A[i] > chave
do A[i+1]  A[i]
ii-1
A[i+1]  chave
% Procura lugar na sequência ordenada
A[1...j-1] onde inserir a chave
Insere a carta-chave
Na posição correta na sequência A[1...j-1]
Algoritmo é executado in place :
Espaço necessário = espaço da entrada + espaço das variáveis Chave, j, i
Complexidade em Espaço = constante (=3)
(não se conta o espaço ocupado pela entrada)
Análise do pseudo-código
Num. Descrição
Passo
tj = número de vezes que o teste do loop 4 é
executado.
1 Para j = 2,..., n
2
3
do chave  A[j]
ij–1
Custo
Vezes
c1
n
c2
n-1
c3
n-1
4
While i > 0 e A[i] > chave
c4
Σnj=2 tj
5
do A[i+1]  A[i]
c5
Σnj=2 (tj – 1)
6
ii-1
c6
Σnj=2 (tj – 1)
7
A[i+1]  chave
c7
n-1
Algoritmo Insertion-Sort
T(n) = custo temporal do algoritmo em função do tamanho da
entrada (=n)
T(n) = c1.n + c2(n-1) + c3(n-1) + c4(Σnj=2 tj) + c5(Σnj=2 (tj-1)) + c6(Σnj=2 (tj-1)) + c7(n-1)
T(n) depende de tj
O valor de tj depende do “grau de desordenação” da entrada.
Algoritmo Insertion-Sort
Melhor caso: a entrada está corretamente em ordem crescente.

tj = 1, para j = 2,...,n
T(n) = c1.n + c2(n-1) + c3(n-1) + c4(n-1) + c7(n-1)
= (c1+c2+c3+c4+c7)n – (c2+c3+c4+c7)
Pior caso : a entrada está ordenada de forma reversa (descrescente)

tj = j, para j = 2,...,n
Σnj=2 j = [n(n+1)/2] – 1
T(n) = c1.n + c2(n-1) + c3(n-1) + c4([n(n+1)/2] – 1) + c5([n(n-1)/2]) +
+ c6([n(n-1)/2]) + c7(n-1) =
= (c4/2 + c5/2 + c6/2)n2 + (c1+c2+c3 - c4/2 - c5/2 - c6/2 + c7)n - (c2 + c3 + c4 + c7)
Algoritmo Insertion-Sort
Caso médio:
tj = j/2, para j = 2,...,n
Exercício: Determinar o valor de T(n) para o caso médio.
Notação O
Notação O é utilizada para ter uma estimativa superior
do tempo T(n) de execução, em termos de funções
do tipo nk, logn, 2n, cujas tendências de crescimento
seguem padrões distintos.

No melhor caso:


T(n) = O(n)
No pior caso:

T(n) = O(n2)
Notação O

T(n) = O(f(n)) se
existe c > 0, existe inteiro n0 > 0 tal que
para todo n ≥ n0
T(n) ≤ c f(n)
f(n)
T(n)
n0
O que importa é o comportamento de T(n) e f(n) para VALORES GRANDES DE n
Se T(n) = O(f(n)) : T(n) e f(n) se comportam de forma semelhante no infinito, a menos de
uma constante. Isto é, T(n) e f(n) crescem de forma semelhante.
Exemplos
1) Seja f(n) = 5n3 + 2n2 + 22n + 6
Mostrar que f(n) = O(n3)
2) Em geral se f(n) é um polinômio de grau k
então f(n) = O(nk)
3) Mostrar que 2n = O(n!)
Aritmética Assintótica



O(f(n) + g(n)) = O(f(n) + O(g(n))
O(nk1) + O(nk2) = O(nk1) se k1 ≥ k2
aO(f(n)) = bO(f(n)) = 2O(f(n)) para quaisquer a,b
Algoritmo Bubble-sort
Ideia:
4
4
4
4
4
2
2
2
3
3
3
3
2
4
4
3
8
8
8
2
3
3
3
4
7
7
2
8
8
8
7
7
2
2
7
7
7
7
8
8
9
9
9
9
9
9
9
9
Pseudo-código
custo vezes
1 c1
n
2 c2
Σ i=1 (n-1) ti
3 c3
4 c4
Σ i=1 (n-1) (ti-1)
x < ti -1
ti = n - i
Análise da complexidade do pseudocódigo
1
2
3
4
custo
c1
c2
c3
c4
vezes
n
Σ i=1 (n-1) ti
Σ i=1 (n-1) (ti-1)
x < ti -1
T(n) = c1n + c2 Σ i=1(n-1) ti + c3 (Σ i=1(n-1) (ti-1)) + c4x
ti = n - i
Mostrar que T(n) = O(n2) para todos os casos (pior, melhor e médio)
Fibonacci
F(n) = F(n-1) + F(n-2) se n > 1
F(1) = 1
F(0) = 0
Cresce tão rapidamente como as potências de 2
F(n) ~ 20.694n
É possivel computar F(n) de forma eficiente ?
Algoritmo fib1(n)
1.
2.
3.
If n = 0 return 0
If n = 1 return 1
Return fib1(n-1) + fib1(n-2)
T(n) = número de passos para computar fib1(n)


T(0) = 1, T(1) = 2
Se n ≥ 2 : T(n) = T(n-1) + T(n-2) + 3
Para todo n ≥ 0 T(n) > F(n)
Prova por indução sobre n
n = 0 T(0) = 1 > F(0) = 0
n = 1 T(1) = 2 > F(1) = 1
T(n) = T(n-1) + T(n-2) + 3 > F(n-1) + F(n-2) + 3 = F(n) + 3 > F(n)
Logo T(n) > F(n) ~ (20.694n ) ~ (1.6)n
fib1 é exponencial
Algoritmo fib2(n)
1.
2.
3.
4.
5.
6.
If n = 0 return 0
Create array f[0,...,n]
f[0] = 0, f[1] = 1
For i = 2,...,n
f[i] = f[i-1] + f[i-2]
Return f[n]
fib2(n) = O(n) ; fib2 é linear