Projeto e Análise de Algoritmos  
Aula 01 Complexidade de Algoritmos  
Edirlei Soares de Lima  
<edirlei@iprj.uerj.br>  
O que é um algoritmo?  
Um conjunto de instruções executáveis para resolver um  
problema (são as ideias por detrás dos programas)  
O problema é a motivação para o algoritmo.  
Geralmente existem vários algoritmos para um mesmo problema.  
Como escolher?  
Algoritmos são independentes da linguagem de programação, da  
máquina, da plataforma, etc.  
Algoritmos são representados através da descrição das instruções de  
forma suficiente para que a audiência os entenda.  
O que é um algoritmo?  
Um problema é caracterizado pela descrição de uma entrada  
e saída.  
Exemplo: problema de ordenação  
Entrada: uma sequência {a1; a2; ... ; an} de n números  
Saída: uma permutação dos números {a'1; a'2; ... ; a'n}  
tal que a'1 a'2 ... a'n  
Entrada: 6 3 7 9 2 4  
Saída: 2 3 4 6 7 9  
Propriedades Desejadas em um Algoritmo  
Eficácia: deve ser capaz de resolver corretamente  
todas as instâncias do problema.  
Eficiência: a sua performance (tempo e memória)  
tem de ser adequada.  
Exemplo: Eficácia de um Algoritmo  
Problema do Caixeiro Viajante:  
Entrada: um conjunto S de n pontos no plano  
Saída: o ciclo mais curto que visita todos os pontos de S  
Exemplo:  
Exemplo: Eficácia de um Algoritmo  
Problema do Caixeiro Viajante  
Um primeiro possível algoritmo:  
1. p1 ponto inicial escolhido aleatoriamente  
2
3
4
5
6
. i ← 1  
. enquanto (existirem pontos por visitar) fazer  
. i ← i + 1  
. pi vizinho não visitado mais próximo de pi-1  
. retorna caminho p1 p2 ... → pn p1  
Exemplo: Eficácia de um Algoritmo  
Problema do Caixeiro Viajante  
Parece funcionar…  
Exemplo: Eficácia de um Algoritmo  
Problema do Caixeiro Viajante  
Mas não funciona para todas as instâncias do problema!  
Exemplo: Eficácia de um Algoritmo  
Problema do Caixeiro Viajante  
Um segundo possível algoritmo:  
1. Para i ← 1 até (n - 1) fazer  
2
. Adiciona ligação ao par de pontos mais próximo tal  
que os pontos estão em componentes conexas (cadeias  
de pontos) diferentes  
3. Adiciona ligação entre dois pontos dos extremos da  
cadeia ligada  
4. retorna o ciclo que formou com os pontos  
Exemplo: Eficácia de um Algoritmo  
Problema do Caixeiro Viajante  
Parece funcionar…  
Exemplo: Eficácia de um Algoritmo  
Problema do Caixeiro Viajante  
Mas não funciona para todas as instâncias do problema!  
Exemplo: Eficácia de um Algoritmo  
Problema do Caixeiro Viajante  
Um terceiro possível algoritmo (força bruta):  
1
2
3
4
5
. Pmin uma qualquer permutação dos pontos de S  
. Para Pi cada uma das permutações de pontos de S  
. Se (custo(Pi) < custo(Pmin)) Então  
.
Pmin Pi  
. retorna caminho formado por Pmin  
O algoritmo é eficaz/correto, mas extremamente lento!  
P(n) = n! = n × (n - 1) × ... × 1 (n fatorial)  
Exemplo: P(20) = 2,432,902,008,176,640,000  
Exemplo: Eficácia de um Algoritmo  
O problema apresentado é uma versão restrita (euclidiana) de um dos  
problemas mais "clássicos": Travelling Salesman Problem (TSP).  
Este problema tem inúmeras aplicações (mesmo na forma "pura")  
Exemplos: produção industrial, rotas de veículos, análise genômica...  
Não é conhecida nenhuma solução eficiente para este problema (que  
gere resultados ótimos, e não apenas "aproximados")  
A solução apresentada tem complexidade temporal: O(n!)  
O TSP pertence a classe dos problemas NP-hard  
A versão de decisão pertence à classes dos problemas NP-completos  
Eficiência de um Algoritmo  
Quantas operações simples um computador pode realizar por  
segundo? (aproximação em ordem de grandeza)  
Assumindo que um computador realizar 1 milhão de  
operações simples por segundo, quanto tempo demorariam  
as seguintes quantidades de instruções?  
Quantidade  
100  
< 1 seg  
< 1 seg  
1 seg  
1,000  
< 1 seg  
1 seg  
10,000  
< 1 seg  
2 min  
100,000  
< 1 seg  
3 horas  
32 anos  
1,000,000  
1 seg  
N
N2  
N3  
2N  
N!  
12 dias  
18 min  
12 dias  
31,710 anos  
1017 anos  
muito tempo muito tempo muito tempo muito tempo  
muito tempo muito tempo muito tempo muito tempo muito tempo  
muito tempo > 1025 anos  
Eficiência de um Algoritmo  
Voltando as permutações do algoritmo para o problema do  
caixeiro viajante:  
P(n) = n! = n × (n - 1) × ... × 1  
Exemplo de 6 permutações de {1, 2, 3}:  
2 3  
3 2  
1
1
2
2
3
3
1 3  
3 1  
1 2  
2 1  
Eficiência de um Algoritmo  
Quanto tempo demora um programa que passa por todas as  
permutações de n números? (tempos aproximados  
considerando cerca de 10 permutações por segundo)  
7
n = 8: 0,003s  
n = 9: 0,026s  
n = 10: 0,236s  
n = 11: 2,655s  
n = 12: 33,923s  
n = 20: 5000 anos !  
Eficiência de um Algoritmo  
Um computador mais rápido adiantaria alguma  
coisa?  
Se n = 20 = 5000 anos, hipoteticamente:  
10x mais rápido ainda demoraria 500 anos;  
5,000x mais rápido ainda demoraria 1 ano;  
1,000,000x mais rápido demoraria quase dois dias mas:  
n = 21 já demoraria mais de um mês;  
n = 22 já demoraria mais de dois anos!  
A taxa de crescimento do algoritmo é muito importante!  
Eficiência de um Algoritmo  
Como conseguir prever o tempo que um algoritmo  
demora?  
Como conseguir comparar dois algoritmos diferentes?  
Random Access Machine (RAM)  
Precisamos de um modelo que seja genérico e independente  
da máquina/linguagem usada.  
Vamos considerar uma Random Access Machine (RAM)  
Cada operação simples (+, -, / , *) demora 1 passo;  
Cada acesso á memória custa também 1 passo;  
Tempo de execução: número de passos executados em relação ao  
tamanho da entrada (T(n)).  
As operações são simplificadas, mas mesmo assim isto é útil  
(somar dois inteiros não custa o mesmo que dividir dois reais,  
mas veremos que esses valores não são importantes em uma  
visão global)  
Exemplo de Contagem de Operações  
Um programa simples:  
int count = 0;  
int i;  
for (i=0; i<n; i++)  
if (v[i] == 0)  
count++;  
Número de operações simples:  
Declarações de variáveis  
Atribuições  
2
2
Comparação menor que”  
Comparação igual a”  
Acesso ao vetor  
n + 1  
n
n
Incremento  
Entre n e 2n (dependendo dos zeros)  
Exemplo de Contagem de Operações  
Um programa simples:  
int count = 0;  
int i;  
for (i=0; i<n; i++)  
if (v[i] == 0)  
count++;  
Total de operações no pior caso:  
T(n) = 2 + 2 + (n + 1) + n + n + 2n = 5 + 5n  
Total de operações no melhor caso:  
T(n) = 2 + 2 + (n + 1) + n + n + n = 5 + 4n  
Tipos de Análises de um Algoritmo  
Análise do Pior Caso:  
T(n) = tempo máximo do algoritmo para uma entrada  
qualquer de tamanho n.  
Análise Caso Médio:  
T(n) = tempo médio do algoritmo para todos as entradas  
de tamanho n.  
Implica conhecer a distribuição estatística das entradas.  
Análise do Melhor Caso:  
T(n) = avaliação ingênua de um algoritmo que é rápido  
para algumas entradas.  
Tipos de Análises de um Algoritmo  
Análise Assintótica  
Precisamos de ferramenta matemática para comparar funções  
Na análise de algoritmos usa-se a Análise Assintótica  
Estudo do comportamento de algoritmos para entradas arbitrariamente  
grandes ou a "descrição" da taxa de crescimento.  
Usa-se uma notação especifica: O, , (big O, omega, theta)  
Permite "simplificar" expressões como a mostrada  
anteriormente focando apenas nas ordens de grandeza.  
Análise Assintótica Notação  
f(n) = O(g(n))  
Significa que C × g(n) é um limite superior de f(n)  
f(n) = (g(n))  
Significa que C × g(n) é um limite inferior de f(n)  
f(n) = (g(n))  
Significa que C1 × g(n) é um limite inferior de f(n) e  
C2 × g(n) é um limite superior de f(n)  
Análise Assintótica Notação  
O
Análise Assintótica Formalização  
f(n) = O(g(n)) se existem constantes positivas n0 e c  
tal que f(n) c × g(n) para todo o n n0  
f(n) = 3n2 - 100n + 6  
2
f(n) = O(n )  
f(n) = O(n3)  
f(n) O(n)  
Análise Assintótica Formalização  
f(n) =(g(n)) se existem constantes positivas n0 e c  
tal que f(n) c × g(n) para todo o n n0  
f(n) = 3n2 - 100n + 6  
2
f(n) = Ω(n )  
f(n) ≠ Ω(n3)  
f(n) = Ω(n)  
Análise Assintótica Formalização  
f(n) = (g(n)) se existem constantes positivas n0, c1 e  
c2 tal que c1 × g(n)f(n) c2 × g(n) para todo o n ≥  
n0  
f(n) = 3n2 - 100n + 6  
2
f(n) = Θ(n )  
f(n) ≠ Θ(n3)  
f(n) ≠ Θ(n)  
f(n) = Θ(g(n)) implica que f(n) = O(g(n)) e f (n) = Ω(g(n))  
Análise Assintótica  
O estudo assintótico nos permite ignorar constantes e termos  
que não são dominantes.  
Considerando a função f(n) = 3n2 + 10n + 50  
Análise Assintótica Regras Praticas  
Multiplicação por uma constante não altera o comportamento:  
Θ(c × f (n)) = Θ(f(n))  
2 2  
99 × n = Θ(n )  
Em um polinômio a n + a n + ... + a n2 + a1n + a0 podemos nos  
x
x-1  
x
x-1  
2
focar na parcela com o maior expoente:  
3 2 3  
3n - 5n + 100 = Θ(n )  
4 2 4  
6n - 20 = Θ(n )  
0.8n + 224 = Θ(n)  
Em uma soma/subtração podemos nos focar na parcela dominante:  
n
3
n
2 + 6n = Θ(2 )  
2
n! - 3n = Θ(n!)  
n log n + 3n = Θ(n2)  
2
Análise Assintótica Exercício  
T(n) = 32n2 + 17n + 32  
Responda se T(n) é  
2
O(n )? Sim  
3
O(n )? Sim  
Ω(n)? Sim  
2
Ω(n )? Sim  
O(n)? Não  
2
Θ(n )? Sim  
3
Ω(n )? Não  
Θ(n)? Não  
4
Θ(n )? Não  
Crescimento Assintótico  
Função  
Nome  
Exemplos  
1
log n  
n
constante  
logarítmica  
linear  
Somar dois números  
Pesquisa binária, inserir um número em uma heap  
1 ciclo para buscar o valor máximo em um vetor  
Ordenação (merge sort, heap sort)  
2 ciclos (bubble sort, selection sort)  
3 ciclos (Floyd-Warshall)  
n log n linearítimica  
n2  
n3  
2n  
n!  
quadrática  
cúbica  
exponencial  
fatorial  
Pesquisa exaustiva (subconjuntos)  
Todas as permutações  
Crescimento Assintótico  
Análise Assintótica Exemplos Praticos  
Um programa tem dois pedaços de código A e B, executados um a seguir  
2
ao outro, sendo que A corre em O(n log n) e B em O(n ).  
2 2  
O programa corre em O(n ), porque n > n log n  
Um programa chama n vezes uma função O(log n), e em seguida volta a  
chamar novamente n vezes outra função O(log n)  
O programa corre em O(n log n)  
Um programa tem 5 ciclos, chamados sequencialmente, cada um deles  
com complexidade O(n)  
O programa corre em O(n)  
Um programa P tem tempo de execução proporcional a 100 × n log n.  
1
2
Um outro programa P tem 2 × n . Qual é o programa mais eficiente?  
1
2
2
P é mais eficiente porque n > n log n. No entanto, para um n pequeno, P2 é  
mais rápido e pode fazer sentido ter um programa que chama P ou P de  
1
2
acordo com o valor de n.  
Exercícios  
1
) Escreva um algoritmo para verificar se um vetor contêm pelo  
menos dois valores duplicados (em qualquer lugar do vetor).  
Em seguida, analise a complexidade do algoritmo proposto.  
bool hasDuplicate(int *vet, int n){  
int i, j;  
bool duplicate = false;  
for (i = 0; i < n; i++){  
for (j = 0; j < n; j++){  
if (i != j && A[i] == A[j])  
return true;  
}
}
return false;  
O(n2)  
}
Exercícios  
) Qual a complexidade do seguinte algoritmo?  
2
int i, j, k, x, result = 0;  
for (i = 0; i < N; i++){  
for (j = i; j < N; j++){  
for (k = 0; k < M; k++){  
x = 0;  
while (x < N){  
m
m
result++;  
x += 3;  
n
n2  
}
}
for (k = 0; k < 2 * M; k++)  
if (k % 7 == 4)  
result++;  
}
O(n2mn) = O(mn3)  
}
Exercícios  
3
) Qual o menor valor de n tal que um algoritmo cujo tempo de  
2
execução é 100n funciona mais rápido que um algoritmo  
n
cujo tempo de execução é 2 na mesma máquina?  
Wolfram Alpha:  
plot 100*n^2 from n=0 to 15, 2^n from n=0 to 15  
Exercícios  
Lista de Exercícios 01 Complexidade de  
Algoritmos  
http://www.inf.puc-rio.br/~elima/paa/  
Leitura Complementar  
Cormen, T., Leiserson, C., Rivest, R., e Stein, C.  
Algoritmos Teoria e Prática (tradução da 2ª.  
Edição americana), Editora Campus, 2002.  
Capítulo 1: A função dos Algoritmos na  
Computação  
Capítulo 2: Conceitos Básicos  
Capítulo 3: Crescimento de Funções