4-AlgorithmAnalysis

Prévia do material em texto

Nuno Leite
AED: Algoritmos e Estruturas de Dados – Semestre de Inverno 2007/08
http://www.deetc.isel.ipl.pt/programacao/aed/
Capítulo 2 - Análise de Algoritmos e Complexidade
ISEL/LEIC - 2007/2008
2º ano, 1º Semestre 
* Estes acetatos foram parcialmente adaptados dos acetatos de AED da 
LEEC do Instituto Superior Técnico – Prof. Rui Gustavo Crespo
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 2
Análise de Algoritmos (1)
„ Para avaliar e comparar o desempenho de dois algoritmos:
„ Método empírico: executamos ambos (muitas vezes) para ver qual é
mais rápido
„ se o algoritmo for lento, o método empírico pode consumir 
demasiado tempo
„ não podemos esperar 2 horas até que o algoritmo produza a resposta!
„ ou se pretendermos afinar os vários parâmetros do algoritmo
„ testar várias variantes pode ser um processo moroso
„ é aqui que entra a análise matemática de algoritmos
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 3
Análise de Algoritmos (2)
„ É fundamental para se perceber e utilizar um algoritmo de forma 
efectiva/eficiente:
„ compararmos com outros
„ prevermos o desempenho
„ escolher correctamente os seus parâmetros 
„ Importante saber que há bases científicas irredutíveis para 
caracterizar, descrever e comparar algoritmos
„ Intenção nesta disciplina é
„ ilustrar o processo
„ introduzir alguma notação
„ introduzir este tipo de análise demonstrando a sua utilidade e 
importância
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 4
Análise de Algoritmos (3)
„ Análise precisa é uma tarefa complicada:
„ algoritmo é implementado numa dada linguagem
„ linguagem é compilada e o programa é executado num dado 
computador
„ difícil prever tempos de execução de cada instrução
„ muitos algoritmos são "sensíveis" aos dados de entrada
„ muitos algoritmos não são bem compreendidos
„ É em geral no entanto possível prever precisamente o tempo de 
execução de um programa,
„ ou que um algoritmo é melhor que outro em dadas circunstâncias 
(bem definidas)
„ apenas é necessário um pequeno conjunto de ferramentas matemáticas
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 5
Análise de Algoritmos (4)
„ Fundamental é separar a análise da implementação, i.e. 
identificar as operações de forma abstracta
„ é relevante saber quantas vezes id[p] é acedido
„ Uma propriedade (imutável) do algoritmo
„ não é tão importante saber quantos nanossegundos essa instrução 
demora no meu computador!
„ Uma propriedade do computador e não do algoritmo 
„ O número de operações abstractas pode ser grande, mas
„ o desempenho tipicamente depende apenas de um pequeno número 
de parâmetros
„ procurar determinar a frequência de execução de cada um desses 
operadores
„ Usar ferramentas de profiling para medir a frequência das instruções
„ Estabelecer estimativas
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 6
Tipos de dados de entrada (1)
„ Que dados usar?
„ dados reais: verdadeira medida do custo de execução
„ dados aleatórios: assegura-nos que as experiências testam o 
algoritmo e não apenas os dados específicos
„ Caso médio
„ dados perversos: mostram que o algoritmo funciona com qualquer 
tipo de dados
„ Pior caso!
„ dados benéficos:
„ Melhor caso
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 7
Tipos de dados de entrada (2)
„ Dependência nos dados de entrada
„ dados reais geralmente não disponíveis:
„ assumir que são aleatórios: caso médio
„ por vezes a análise é complicada
„ Pode ser uma ficção matemática não representativa da vida real
„ perversos: pior caso
„ por vezes difícil de determinar
„ podem nunca acontecer na vida real
„ benéficos: melhor caso
„ Em geral, qualquer destas análises fornece boas indicações 
quanto ao desempenho de um algoritmo
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 8
Análise: Crescimento de Funções (1)
„ O tempo de execução geralmente depende dum único parâmetro 
n
„ ordem de um polinómio
„ tamanho de um ficheiro a ser processado, ordenado, etc.
„ ou medida abstracta do tamanho do problema a considerar
„ usualmente relacionado com o número de dados a processar
„ Quando há mais de um parâmetro
„ procura-se exprimir todos os parâmetros em função de um só
„ faz-se uma análise em separado para cada parâmetro
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 9
Análise: Crescimento de Funções (2)
„ Os Algoritmos têm tempo de execução proporcional a:
„ 1
„ muitas instruções são executadas uma só vez ou poucas vezes
„ se isto for verdade para todo o programa diz-se que o seu tempo de 
execução é constante
„ log2 n
„ tempo de execução é logarítmico
„ cresce ligeiramente à medida que n cresce
„ usual em algoritmos que resolvem um grande problema reduzindo-o a 
problemas menores e resolvendo estes
„ quando n duplica, log2 n aumenta mas muito pouco; apenas duplica 
quando n aumenta para n2
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 10
Análise: Crescimento de Funções (3)
„ n 
„ tempo de execução é linear 
„ típico quando algum processamento é feito para cada dado de entrada
„ situação óptima quando é necessário processar n dados de entrada (ou 
produzir n dados na saída)
„ n log2 n
„ típico quando se reduz um problema em sub-problemas, se resolvem 
estes separadamente e se combinam as soluções
„ Ex: algoritmo de ordenação Mergesort
„ se n é 1 milhão, n log2 n é perto de 20 milhões
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 11
Análise: Crescimento de Funções (4)
„ n2
„ tempo de execução quadrático
„ típico quando é preciso processar todos os pares de dados de entrada
„ prático apenas em pequenos problemas (ex: produto matriz -vector)
„ n3
„ tempo de execução cúbico
„ para n = 100, n3 = 1 milhão (ex: produto de matrizes)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 12
Análise: Crescimento de Funções (5)
„ 2n
„ tempo de execução exponencial
„ algoritmos com esta ordem de complexidade geralmente não são úteis 
sob o ponto de vista prático
„ típico em soluções de força bruta
„ para n = 20, 2n = 1 milhão; n duplica, tempo passa a ser o quadrado
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 13
Análise: Crescimento de Funções (6)
„ Convenção:
„ lg n é equivalente a log2 n
Valores típicos de várias funções
lg n sqrt(n) n n lg n n(lg n)2 n3/2 n2
3 3 10 33 110 32 100
7 10 100 664 4414 1000 10000
10 32 1000 9966 99317 31623 1000000
13 100 10000 132877 1765633 1000000 100000000
17 316 100000 1660964 27588016 31622777 10000000000
20 1000 1000000 19931569 397267426 1000000000 1000000000000
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 14
Análise: Resolução de grandes problemas (1)
„ Relação do tempo de execução
„ conversão para unidades de tempo mais familiares
segundos unidades de tempo mais familiares
102 1.7 minutos
104 2.8 horas
105 1.1 dias
106 1.6 semanas
107 3.8 meses
108 3.1 anos
109 3.1 décadas
1010 3.1 séculos
1011 nunca
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 15
Análise: Resolução de grandes problemas (2)
tamanho do problema - 1 milhão tamanho do problema - 1 bilião*
n n lg n n2 n lg n n2
106 segundos segundos semanas horas horas nunca
109 instantâneo instantâneo horas segundos segundos décadas
1012 instantâneo instantâneo segundos instantâneo instantâneo semanas
n
operações 
por 
segundo
* 1 bilião (1 billion) = mil milhões
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 16
Análise: Complexidade
„ Complexidade refere-seao tempo de execução
„ usualmente o termo de maior ordem domina (para n elevado)
„ comum todos os termos serem multiplicados por uma constante
„ para n pequeno vários termos podem ser igualmente relevantes
„ ex: 0.1 n3 +100 * n2 para 1 ≤ n ≤ 1000
„ base do logaritmo não é muito relevante
„ mudar de base é um factor constante
„ bases mais comuns são 2 (lg n), 10 (log n) e e (ln n)
„ (e = número de Neper)
„ Análise de complexidade é muito importante quando n aumenta
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 17
Análise: Funções Relevantes
∑
=
=
n
1i
n i
1H
função nome valores típicos aproximação
⎣x⎦ função floor (chão) ⎣3.14⎦ = 3 x
⎡x⎤ função ceiling (tecto) ⎡3.14⎤ = 4 x
lg n logaritmo binário lg 1024 = 10 1.44 ln n
Fn números de Fibonacci F10 = 55 φn / sqrt(5)
Hn números harmónicos H10 ≈ 2.9 ln n + γ
n ! função factorial 10! = 3628800 (n / e)n
lg (n!) lg(100!) ≈ 520 n lg n – 1.44 n 
e = 2.71828 …
γ = 0.57721 …
, para n ≥ 2 com F0 = 0 e F1 = 1 φ = (1+ sqrt(5)) / 2 = 1.61803 …
ln 2 = 0.693147 …
lg e = 1 / ln 2 = 1.44269 …
2n1nn FFF −− +=
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 18
Algoritmos – Síntese da Aula 1
„ Análise de Algoritmos
„ Aspectos essenciais da análise
„ empírica, teórica; estratégias de melhoria de algoritmos; comparação 
de algoritmos
„ Crescimento de funções
„ Resolução de grandes problemas
„ Complexidade e funções relevantes
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 19
Análise: Notação "O grande" (1)
„ A notação matemática que nos permite suprimir detalhes na 
análise de algoritmos
„ A notação “O grande” fornece um limite assimptótico superior 
(não o menor limite superior) de uma dada função
„ Definição: Para uma dada função g(n), denota-se por O(g(n))
(pronuncia-se “ó grande de g de n”) o conjunto de funções
O(g(n)) = { f(n) : existem constantes positivas c e n0
tal que 0 ≤ f(n) ≤ c.g(n) para todo o n ≥ n0 }
„ Utiliza-se a notação “O grande” para encontrar um limite 
superior duma função, a menos de um factor constante
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 20
Análise: Notação "O grande" (2)
„ Escreve-se f(n) = O(g(n)) se existirem constantes c e n0 tal que, 
para todos os valores à direita de n0, o valor de f(n) é menor ou 
igual a c.g(n)
n0
f(n)
cg(n)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 21
Análise: Notação "O grande" (3)
„ A notação é usada com três objectivos: 
„ limitar o erro que é feito ao ignorar os termos menores nas fórmulas 
matemáticas 
„ limitar o erro que é feito na análise ao desprezar parte de um 
programa que contribui de forma mínima para o 
custo/complexidade total
„ permitir-nos classificar algoritmos de acordo com limites superiores 
no seu tempo de execução
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 22
Análise: Notação "O grande" (4)
„ Escreve-se f(n) = O(g(n)) para indicar que a função f(n) é um 
membro do conjunto O(g(n))
„ f(n) = O(g(n)) significa f(n) ∈ O(g(n))
„ Quando a notação assimptótica é usada em equações ou 
inequações, utilizam-se as seguintes convenções:
„ 1) O(n) significa O(g(n)); o argumento de O(.) é sempre uma função
„ p.ex.: O(1) significa O(f(n)), sendo f(n) uma função constante 
„ 2) notação assimptótica aparece isolada do lado direito da equação 
ou inequação
„ p.ex.: n = O(n2) significa n ∈ O(n2), ou mais precisamente f(n) = n∈
O(g(n)), onde g(n)=n2
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 23
Análise: Notação "O grande" (5)
„ Convenções (continuação)
„ 3) notação assimptótica aparece numa fórmula
„ p.ex.: 2n2 + 3n + 1 = 2n2 + O(n) significa
2n2 + 3n + 1 = 2n2 + f(n), em que f(n) = 3n+1 ∈ O(n)
„ Usando a definição, provar que:
„ 3n = O(n)
„ 2n + 3 = O(n)
„ 3n2 + 5n + 3 = O(n2)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 24
Análise: Notação "O grande" (6)
„ Os resultados da análise não são exactos
„ são aproximações tecnicamente bem caracterizadas
„ Manipulações com a notação "O grande”
„ permitem-nos ignorar termos de menor importância de forma 
precisa. Podem ser feitas como se o "O" não estivesse lá
Ex: (n + O(1)) (n + O(lg n) = 
usando distributividade e o facto de que
f(n) . O(g(n)) = O(f(n) . g(n)) se f(n) não for constante,
e
O(1) . g(n) = O(g(n)), fica:
= n2+ O(n) + O(n lg N) + O(lg n) = 
e como O(n lg n) > O(n) > O(lg n) 
= n2 + O(n lg n)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 25
Análise: Notação "O grande" (7)
„ Manipulações com a notação "O grande”: alguns exemplos
„ 1) f(n) = O(f(n))
„ 2) c . O(f(n)) = O(c . f(n)) = O(f(n))
„ 3) O(f) + O(g) = O(f+g) = O(max(f,g))
„ 4) O(f) . O(g) = O(f . g)
„ 5) O(f) + O(g) = O(f) sse g(n) ≤ f(n) para ∀ n >n0
„ Exercício: provar as relações 1), 2) e 5)
Fórmula com termo contendo O(...) diz-se expressão assimptótica
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 26
Exemplo: vantagens da notação (1)
„ Dado um problema para análise
„ verifica-se ter um ciclo interno iterado 2nHn vezes em média
„ cada iteração requer execução de a0 instruções (ou demora a0 ns)
„ secção interna iterada n vezes
„ requer execução de a1 instruções (ou demora a1 ns)
„ inicialização feita uma vez
„ requer execução de a2 instruções (ou demora a2 ns)
„ Complexidade (tempo médio de execução) é
2 a0 n Hn + a1 n + a2 = 2 a0 n Hn + O(n)
„ Para n grande não é preciso calcular a1 ou a2
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 27
Exemplo: vantagens da notação (2)
„ Usando a notação O() temos Hn = ln n + O(1)
logo 
2 a0 n Hn + a1 n + a2 = 2 a0 n ln n + O(n) ≈ 2 a0 n ln n
„ E se se duplicar n?
„ O tempo de execução também duplica
„ Conclui-se que também não é preciso conhecer a0 !
2
ln(n)
1
O2
O(1)ln(n)
O(1)2ln(2n)
O(n)(n)ln(n)2a
O(2n)(2n)ln(2n)2a
0
0 ≈⎟⎟⎠
⎞⎜⎜⎝
⎛+=+
+=+
+
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 28
Algoritmos – Síntese da Aula 2
„ Notação “O grande”
„ Conceito
„ Definições
„ Propriedades
„ Exercícios
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 29
Operações sobre dados - Complexidade
„ As operações sobre dados mais usadas são quatro:
1. Acesso
„ Ver se existe, e recolher, o valor do conteúdo de um elemento
2. Modificação
„ Alterar o valor do conteúdo de um elemento
3. Inserção
„ Acrescentar um novo elemento e/ou componente a uma estrutura já
existente
4. Remoção
„ Apagar um elemento e/ou componente de uma estrutura já existente
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 30
Acesso e modificação de variáveis
„ Na operação de acesso a dados organizados em array ou lista 
pode-se querer:
„ Aceder ao primeiro elemento
„ Aceder ao último elemento
„ Aceder a um elemento específico
„ Aceder ao próximo (pressupõe a existência de um iterador) 
„ Em operações de modificação pode-se também querer
„ Modificar o conteúdo do primeiro elemento
„ Modificar o conteúdo do último elemento
„ Modificar o conteúdo de um elemento específico
„ Modificar o próximo (pressupõe a existência de um iterador)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 31
Eficiência no acesso e modificação
„ A eficiência nas operações de acesso e modificação é
condicionada pela estrutura escolhida para armazenar os dados
„ Assim
Acesso/Modificação Array Lista
Primeiro O(1) O(1)
Último O(1) O(size)
Próximo O(1) O(1)
Específico O(1) O(k)
Assume-se 
que apenas 
existe um 
ponteiro 
para o início 
da lista
- size é o número de elementos existente
- k é a posição do elemento a aceder ou modificar (1≤ k ≤ size)LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 32
Inserção de componentes
„ Na operação de inserção de novos elementos em arrays, ou em 
listas, pode pretender-se
„ Inserir um novo elemento na primeira posição, deslocando todos os 
outros para a frente
„ Inserir um novo elemento na última posição sem afectar os já
existentes
„ Inserir um novo elemento numa posição intermédia pré-especificada, 
sem afectar os anteriores e deslocando os posteriores para a frente
„ Inserir um novo elemento de acordo com o seu valor ou em função 
do valor de algum qualificador associado com esse elemento (p. ex.: 
inserção ordenada)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 33
Eficiência na inserção
„ A eficiência da operações de inserção é condicionada pela 
estrutura escolhida para armazenar os dados
„ Assim
Inserção Array Lista
Primeiro O(size) O(1)
Último O(1) O(size)
Pré-especificado O(size-k) O(k)
Condicional O(size) O(k)
Assume-se 
que apenas 
existe um 
ponteiro 
para o início 
da lista
- size é o número de elementos existente antes da inserção
- k é a posição onde ficará o elemento a inserir (1≤ k ≤ size)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 34
Remoção de componentes
„ Na operação de remoção de elementos de tabelas ou de listas 
pode pretender-se
„ Apagar o primeiro elemento da primeira posição, deslocando todos os 
outros para trás.
„ Apagar o último elemento sem afectar os já existentes.
„ Apagar o elemento situado numa posição intermédia pré-especificada, 
sem afectar os anteriores e deslocando os posteriores para trás.
„ Apagar o elemento que possuir determinado valor, propriedade, etc.
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 35
Eficiência na remoção
„ A eficiência da operação de remoção é condicionada pela 
estrutura escolhida para armazenar os dados
„ Assim
Remoção Array Lista
Primeiro O(size) O(1)
Último O(1) O(size)
Pré-especificado O(size-k) O(k)
Condicional O(size) O(k)
Assume-se 
que apenas 
existe um 
ponteiro 
para o início 
da lista
- size é o número de elementos existente antes da remoção
- k é a posição onde está o elemento a remover (1≤ k ≤ size)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 36
Metodologia para determinação de complexidade (1)
„ Suponha o seguinte código
for (i = 0; i < n; ++i) { instruções; }
„ contabilização do número de instruções é simples: n iterações e em 
cada uma são executadas um número constante de instruções: O(n)
„ Suponha o código seguinte:
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
instruções;
}
}
„ contabilização do número de instruções é ainda simples: ciclo 
interno é O(n) e é executado n vezes: O(n2)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 37
Metodologia para determinação de complexidade (2)
„ Suponha o código seguinte:
for (i = 0; i < n; ++i) {
for (j = i; j < n; ++j) {
instruções;
}
}
„ contabilização do número de instruções é ainda simples: ciclo 
interno é executado 
n + (n-1) + (n-2) + … + 3 + 2 + 1 = n(n+1)/2 ∈ O(n2)
„ Infelizmente nem sempre a contabilização é assim tão simples...
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 38
Metodologia para determinação de complexidade (3)
„ Suponha o seguinte código
public static int func (int a[], int n) {
várias instruções;
b = func(a, n-1); return b; 
}
„ contabilização do número de instruções não parece ser simples
„ numa chamada à função executamos
„ algumas instruções sobre n objectos (digamos O(f(n)); pode ser 
constante, n, etc.)
„ depois voltamos a chamar a mesma função agora apenas com n-1
objectos
„ Número total de instruções executadas é
„ C(n) = C(n-1)+ O(f(n)) uma recorrência!
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 39
Recorrência e Funções recorrentes (1)
„ Um algoritmo recorrente é aquele que resolve um dado 
problema resolvendo uma ou mais instâncias de menor dimensão 
do mesmo problema
„ Para implementar algoritmos recorrentes em Java, utilizam-se 
métodos recorrentes – métodos em cujo corpo é invocado o 
próprio método
„ os métodos recorrentes em Java são especificados de forma 
equivalente às definições recorrentes de funções matemáticas
„ p. ex.: definição recorrente da função factorial
n! = n.(n-1)!, para n ≥ 1 com 0! = 1 
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 40
Recorrência e Funções recorrentes (2)
„ Implementação em Java:
„ Algoritmo recorrente
static int factorial(int n) { 
if (n == 0) return 1; 
return n*factorial(n-1); 
}
„ Algoritmo iterativo
static int factorial(int n) { 
int fact = 1;
for (int i = 1; i <= n; ++i) 
fact *= i;
return fact; 
}
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 41
Recorrência e Funções recorrentes (3)
„ É sempre possível transformar um programa recorrente num 
programa equivalente não recorrente
„ Inversamente, também é possível converter um programa 
iterativo num programa recorrente, expressando a computação 
sem usar ciclos 
„ A recorrência permite-nos expressar algoritmos complexos de 
uma forma compacta, sem contudo sacrificar a eficiência
„ Por forma a garantir que um algoritmo recorrente termina a 
execução é necessário garantir três condições:
1. recorrência deve ser sempre feita com instâncias do problema de 
menor dimensão
2. deve existir um caso base
3. o caso base tem que ser alcançável
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 42
Análise: Recorrências básicas (1)
„ Muitos algoritmos são baseados na ideia de "dividir para 
conquistar” (divide and conquer)
„ dividir recorrentemente um problema grande em vários problemas 
menores
„ Análise de algoritmos recorrentes
„ a cada algoritmo recorrente está associado uma função de 
complexidade f(n) desconhecida, onde n é a dimensão dos 
argumentos do algoritmo
„ de seguida, obtém-se a equação de recorrência, que define uma 
função por uma expressão que envolve a mesma função
„ resolvendo a equação de recorrência, obtém-se a medida de 
complexidade do algoritmo
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 43
Análise: Recorrências básicas (2)
„ Problema: encontrar o máximo de um array
„ Algoritmo iterativo
static int maxIterative(int array[]){
int max = array[0]; // Assume-se que o array não está vazio
int n = array.length;
for (int i = 1; i < n; ++i) {
if (array[i] > max) max = array[i];
}
return max;
}
„ Este algoritmo executa em tempo proporcional a O(n)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 44
Análise: Recorrências básicas (3)
„ Algoritmo recorrente
static int maxRecursive(int array[], int n, int maxActual) {
if (n == 0) return maxActual;
if (array[n-1] > maxActual) {
return maxRecursive(array, n-1, array[n-1]);
}
else {
return maxRecursive(array, n-1, maxActual);
}
}
„ Em cada passo executa O(1) instruções somadas às instruções 
realizadas na recorrência com n-1 elementos
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 45
Análise: Recorrências básicas (4)
Programa recorrente que calcula o máximo
Equação de recorrência: C(n)=C(n-1)+O(1) para n ≥ 2 com C(1)=O(1)
Solução: 
C(n) = O(n)
Demonstração: usar a
propriedade telescópica e
aplicar a fórmula a si própria
Importante: O carácter recorrente 
de um algoritmo reflecte-se 
directamente na sua análise 
C(n) = C(n-1) + O(1) 
= C(n-2) + O(1) + O(1)
= C(n-3) + O(1) + O(1) + O(1)
. . . 
= C(1) + O(1) + ... + O(1) 
= O(1) + O(1) + ... + O(1) 
= O(n)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 46
Análise:Recorrências básicas (5)
„ Problema: listar na saída os pares de índices cuja soma de 
valores é igual a x
„ Algoritmo iterativo
static void pairsIterative(int array[], int x) {
int n = array.length;
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
if (array[i]+array[j]==x) 
System.out.println(i + “ " + j);
}
}
}
„ Este algoritmo executa em tempo proporcional a O(n2)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 47
Análise: Recorrências básicas (6)
„ Algoritmo recorrente
static void pairsRecursive(int array[], int x, int n) {
if (n == 0) return;
for (int i = 0; i < n-1; ++i) {
if (array[n-1] + array[i] == x) {
System.out.println(n-1 + “ " + i);
}
}
pairsRecursive(array, x, n-1);
}
„ Em cada passo executa O(n) instruções somadas às instruções 
realizadas na recorrência com n-1 elementos
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 48
Análise: Recorrências básicas (7)
Programa recorrente que lista na saída os pares de índices cuja soma 
de valores é igual a x
Equação de recorrência: C(n)=C(n-1)+O(n) para n ≥ 2 com C(1)=O(1)
Solução: 
C(n) = O(n2)
Demonstração: usar a
propriedade telescópica e
aplicar a fórmula a si própria
Importante: O carácter 
recorrente de um algoritmo 
reflecte-se directamente 
na sua análise 
C(n) = C(n-1) + O(n) 
= C(n-2) + O(n – 1) + O(n)
= C(n-3) + O(n–2)+O(n–1) + O(n)
. . . 
= C(1)+O(2)+...+O(n–2)+O(n–1)+O(n) 
= O(1)+O(2)+...+O(n–2)+O(n–1)+O(n) 
= ⎟⎠
⎞⎜⎝
⎛ +
2
1)n(n
O
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 49
Algoritmos – Síntese da Aula 3
„ Operações sobre dados
„ determinação da complexidade
„ Metodologia para determinação de complexidade 
„ Recorrência e Funções recorrentes
„ Recorrências básicas 
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 50
Pesquisa binária
„ Problema: pesquisa binária ou dicotómica num array ordenado
„ Pesquisa binária - Algoritmo
„ se os números no array estão ordenados podemos eliminar metade 
deles comparando o que procuramos com o que está na posição do 
meio
„ se for igual temos sucesso
„ se for menor, aplicamos o mesmo método à primeira metade da 
tabela
„ se for maior aplicamos o mesmo método à segunda metade da 
tabela
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 51
Pesquisa binária
„ Algoritmo iterativo
static int binarySearchIterative(int a[], int v, int l, int r) { 
while (r >= l) {
int mid = (l+r)/2; 
if (v == a[mid]) return mid; 
if (v < a[mid]) r = mid-1; 
else l = mid+1; 
} 
return -1;
}
„ Função de complexidade do tempo de execução?
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 52
Pesquisa binária - Exemplo
5 7 9 13 32 33 42 54 56 88
0 1 2 3 4 5 6 7 8 9
Valor v a procurar é o 33
O array tem o seguinte conteúdo:
mid = (0 + 9) / 2 (que é 4)
33 > a[mid] (ou seja, 33 > a[4])
Então, se 33 se encontra no array, é um dos elementos:
33 42 54 56 88
5 6 7 8 9
Metade dos elementos são ignorados dado que o array 
está ordenado.
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 53
mid = (5 + 6) / 2 (que é 5)
33 == a[mid]
Encontrámos 33 no índice 5:
33
5
mid = (5 + 9) / 2 (que é 7)
33 < a[mid] (ou seja, 33 < a[7])
Então, se 33 se encontra no array, é um dos elementos:
33 42
5 6
Elimina
metade dos 
restantes
elementos
Pesquisa binária - Exemplo
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 54
Pesquisa binária
„ Algoritmo recorrente
static int binarySearchRecursive(int a[], int v, int l, int r) {
int result = -1, mid;
if (l > r) result = -1;
else { mid = (l + r)/2;
if (v == a[mid]) result = mid; 
else if (v < a[mid])
result = binarySearchRecursive (a, v, l, mid - 1);
else //(v > a[mid])
result = binarySearchRecursive (a, v, mid + 1, r);
}
return result; }
„ Em cada passo executa O(1) instruções (ver se encontrou) 
somadas às instruções realizadas na recorrência com n/2
elementos
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 55
Análise: Equação de recorrência
Programa recorrente que, em cada passo, divide em dois os dados de 
entrada
Equação de recorrência: C(n)=C(n/2)+O(1) para n ≥ 2 com C(1)=O(1)
Solução: C(n) = O(lg n)
Demonstração: 
considerar n = 2p (p = lg n) e
usar a propriedade telescópica e
aplicar a fórmula a si própria
C(2p) = C(2p-1) + O(1) 
= C(2p-2) + O(1) + O(1)
= C(2p-3) + O(3)
. . . 
= C(20) + O(p) 
= O(p + 1)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 56
Merge Sort – Um método de ordenação recorrente
„ Exemplo de algoritmo que usa a técnica “divide and conquer”
„ Divide o array ao meio e ordena as duas metades de forma 
recorrente
„ Combina as duas metades ordenadas, resultando no array
ordenado
„ Algoritmo:
Se o array a contém apenas um elemento, pára (caso base).
Senão, faz o seguinte (caso de recorrência):
Copia a primeira metade dos elementos de a para um array
chamado front.
Copia os restantes elementos de a para outro array chamado 
tail.
Ordena o array front com uma chamada recorrente.
Ordena o array tail com uma chamada recorrente. 
Combina os elementos dos arrays front e tail no array a.
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 57
Merge Sort – Um método de ordenação recorrente
public static void sort(int[] a) {
if (a.length >= 2) {
int middle = a.length/2;
int[] front = new int[middle];
int[] tail = new int[a.length-middle];
divide(a, front, tail);
/* ordenar o array front */
sort(front);
/* ordenar o array tail */
sort(tail);
/* junta os arrays no array a, ordenando-os */
merge(a, front, tail);
}
}
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 58
Merge Sort – Um método de ordenação recorrente
public static void divide(int[] a, int[] front, int[] tail) 
{
int i;
for (i = 0; i < front.length; ++i) 
front[i] = a[i];
for (i = 0; i < tail.length; ++i) 
tail[i] = a[front.length+i];
}
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 59
Merge Sort – Um método de ordenação recorrente
public static void merge(int[] a, int[] front, int[] tail) {
int indexF = 0, indexT = 0, indexA = 0;
while (indexF < front.length && indexT < tail.length) {
if (front[indexF] < tail[indexT]) { a[indexA] = front[indexF]; 
++indexF; }
else { a[indexA] = tail[indexT]; ++indexT; }
++indexA;
}
/* Se existir, copiar o resto de front */
while (indexF < front.length) {
a[indexA] = front[indexF]; ++indexF; ++indexA;
}
/* Se existir, copiar o resto de tail */
while (indexT < tail.length) {
a[indexA] = tail[indexT]; ++indexT; ++indexA;
}
}
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 60
Programa recorrente que, em cada passo, tem de examinar todos os
dados de entrada antes, durante ou depois de os dividir em duas 
metades
Equação de recorrência: C(n)=2C(n/2)+O(n) para n ≥ 2 com 
C(1)=O(1)
Solução: C(n) = O(n lg n)
Demonstração: 
considerar n = 2p (p = lg n) e
usar a propriedade telescópica e
aplicar a fórmula a si própria
Análise: Equação de recorrência
O(1)
2
)C(2
2
)C(2
)O(2)2C(2)C(2
1p
1p
p
p
p1pp
+=
+=
−
−
−
O(p)
O(1)O(1)
2
)C(2
2p
2p
=
=
++= −
−
K
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 61
Análise: Procura sequencial e procura binária
„ Dois algoritmos básicos que nos permitem ver se um elemento de 
uma sequência de objectos aparece num conjunto de objectos 
previamente guardados
„ permite ilustrar o processo de análise e comparação de algoritmos
„ Exemplo de aplicação:
„ companhia de cartões de crédito quer saber se as últimasM 
transacções envolveram algum dos N cartões dados como 
desaparecidos ou de maus pagadores 
„ Pretende-se estimar o tempo de execução dos algoritmos
„ N é muito grande (ex: 104 a 106) e M enormíssimo (106 a 109)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 62
Procura Sequencial - Solução trivial
„ Assumir que
„ os objectos são representados por números inteiros
„ dados armazenados num array
„ procura é sequencial no array
static int search(int a[], int v, int l, int r) { 
int i; 
for (i = l; i <= r; i++) {
if (v == a[i]) 
return i; 
}
return -1; 
} 
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 63
Procura Sequencial - Análise (1)
„ O tempo de execução depende se o objecto está ou não no array
„ se não estiver percorremos o array todo (N elementos)
„ se estiver podemos descobrir logo no início (ou no fim)
„ tempo depende dos dados! 
„ a melhor garantia que podemos dar é que não examinados mais do 
que N elementos
„ Para realizar previsões temos que assumir algo sobre os dados:
„ números são aleatórios (não relacionados entre si) ?
„ esta propriedade é crítica! 
„ Assumir algo sobre a procura
„ estudar o caso de sucesso e o de insucesso separadamente
„ tempo de comparação assumido constante
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 64
Procura Sequencial - Análise (2)
„ Propriedade: na procura sequencial o número de elementos do 
array que são examinados é:
„ N em caso de insucesso
„ em média aproximadamente N/2 em caso de sucesso
„ Tempo de execução é portanto proporcional a N (linear)!
„ Isto para cada elemento de entrada
„ Custo total é O(MN) que é enorme 
„ Como melhorar o algoritmo?
„ manter os números ordenados no array
„ na procura sequencial num array ordenado o custo é N no pior caso e 
N/2 em média (quer haja sucesso ou não)
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 65
Procura Binária
„ Se demorar c microsegundos a examinar um número e M =109, 
N =106
„ tempo total de verificação são 16c anos !!
„ Melhoramento: usar procura binária
„ Propriedade: A procura binária nunca examina mais do que 
⎣lg n⎦ + 1 números (propriedade demonstrada anteriormente 
com resolução de equação de recorrência)
„ Mostra que este tipo de pesquisa permite resolver problemas até
um milhão de dados com cerca de 20 comparações por procura
„ possivelmente menos do que o tempo que demora a ler ou escrever 
os números num computador real 
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 66
Estudo empírico de algoritmos de procura
S - Procura Sequencial B - Procura binária
M = 1000 M = 10000 M = 100000 
N S B S B S B
125 3 3 36 12 357 126
250 6 2 63 13 636 130
500 13 1 119 14 1196 137
1250 28 1 286 15 2880 146
2500 57 1 570 16 154
5000 113 1 1172 17 164
12500 308 2 3073 17 173
25000 612 1 19 183
50000 1217 2 20 196
100000 2682 2 21 209
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 67
Conclusões da análise do exemplo
„ Identificação de operações básicas de forma abstracta 
„ Utilização de análise matemática para estudar a frequência com 
que um algoritmo executa essas operações 
„ Utilizar resultados para deduzir uma estimativa funcional do 
tempo de execução 
„ Verificar e estender estudos empíricos 
„ Identificar e eventualmente optimizar as características mais 
relevantes de um dado algoritmo
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 68
Garantias, Previsões e Limitações (1)
„ O tempo de execução dos algoritmos depende criticamente dos 
dados.
„ Objectivo da análise é
„ eliminar essa dependência
„ inferir o máximo de informação assumindo o mínimo possível
„ O estudo do pior caso é importante:
„ permite obter garantias sobre o tempo de execução do programa
„ se o resultado no pior caso é aceitável, então a situação é favorável
„ é desejável utilizar algoritmos com bom desempenho no pior caso
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 69
Garantias, Previsões e Limitações (2)
„ O estudo do pior caso é importante:
„ se o resultado no pior caso for mau, pode ser problemático
„ não sabemos quão provável será aparecerem dados que levem a esse 
desempenho
„ p.ex. demonstra-se que o algoritmo de união rápida é O(M lg N) para 
dados típicos e O(MN) para o pior caso
„ importante não sobrevalorizar obtenção de valores baixos para o 
pior caso
„ não é relevante melhorar o desempenho no pior caso à custa de piorar o 
desempenho global do algoritmo em dados típicos
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 70
Garantias, Previsões e Limitações (3)
„ O estudo do desempenho no caso médio é atractivo: 
„ permite fazer previsões
„ bom quando é possível caracterizar muito bem os dados de entrada 
(tipo, frequência, etc.)
„ mau quando tal não é possível/fácil
„ ex: processar texto aleatório num ficheiro versus processar o texto de 
um livro de Eça de Queiroz!
„ análise pode ser não trivial em termos matemáticos
„ ex: no algoritmo de união rápida
„ saber o valor médio pode não ser suficiente
„ podemos ter de saber o desvio padrão ou outras características
„ na análise do caso médio estamos interessados em saber a 
probabilidade de o algoritmo ser dramaticamente mais lento que o
esperado
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 71
Garantias, Previsões e Limitações (4)
„ Análise descrita permite obter limites superiores ou valores 
esperados (em certos casos)
„ por vezes é relevante obter também limites inferiores! 
„ Se os limites inferiores e superiores forem próximos
„ é infrutífero tentar optimizar mais um algoritmo ou processo
„ mais vale tentar optimizar a implementação
„ Análise pode dar indicações preciosas sobre como e onde 
melhorar o desempenho de um algoritmo
„ nem sempre é o caso no entanto!
LEIC – AED – Inverno 2007/08 Análise de Algoritmos e Complexidade 72
Algoritmos – Síntese da Aula 4
„ Recorrências básicas (continuação)
„ Procura binária
„ Ordenação MergeSort
„ Exemplo: Procura
„ Procura sequencial versus Procura binária
„ Estudo empírico de métodos de procura
„ Conclusões do exemplo
„ Garantias, previsões e limitações
	Capítulo 2 - Análise de Algoritmos e Complexidade
	Análise de Algoritmos (1)
	Análise de Algoritmos (2)
	Análise de Algoritmos (3)
	Análise de Algoritmos (4)
	Tipos de dados de entrada (1)
	Tipos de dados de entrada (2)
	Análise: Crescimento de Funções (1)
	Análise: Crescimento de Funções (2)
	Análise: Crescimento de Funções (3)
	Análise: Crescimento de Funções (4)
	Análise: Crescimento de Funções (5)
	Análise: Crescimento de Funções (6)
	Análise: Resolução de grandes problemas (1)
	Análise: Resolução de grandes problemas (2)
	Análise: Complexidade
	Análise: Funções Relevantes
	Algoritmos – Síntese da Aula 1
	Análise: Notação "O grande" (1)
	Análise: Notação "O grande" (2)
	Análise: Notação "O grande" (3)
	Análise: Notação "O grande" (4)
	Análise: Notação "O grande" (5)
	Análise: Notação "O grande" (6)
	Análise: Notação "O grande" (7)
	Exemplo: vantagens da notação (1)
	Exemplo: vantagens da notação (2)
	Algoritmos – Síntese da Aula 2
	Operações sobre dados - Complexidade
	Acesso e modificação de variáveis
	Eficiência no acesso e modificação
	Inserção de componentes
	Eficiência na inserção
	Remoção de componentes
	Eficiência na remoção
	Metodologia para determinação de complexidade (1)
	Metodologia para determinação de complexidade (2)
	Metodologia para determinação de complexidade (3)
	Recorrência e Funções recorrentes (1)
	Recorrência e Funções recorrentes (2)
	Recorrência e Funções recorrentes (3)
	Análise: Recorrências básicas (1)Análise: Recorrências básicas (2)
	Análise: Recorrências básicas (3)
	Análise: Recorrências básicas (4)
	Análise: Recorrências básicas (5)
	Análise: Recorrências básicas (6)
	Análise: Recorrências básicas (7)
	Algoritmos – Síntese da Aula 3
	Pesquisa binária
	Pesquisa binária
	Pesquisa binária - Exemplo
	Pesquisa binária - Exemplo
	Pesquisa binária
	Análise: Equação de recorrência
	Merge Sort – Um método de ordenação recorrente
	Merge Sort – Um método de ordenação recorrente
	Merge Sort – Um método de ordenação recorrente
	Merge Sort – Um método de ordenação recorrente
	Análise: Equação de recorrência
	Análise: Procura sequencial e procura binária
	Procura Sequencial - Solução trivial
	Procura Sequencial - Análise (1)
	Procura Sequencial - Análise (2)
	Procura Binária
	Estudo empírico de algoritmos de procura
	Conclusões da análise do exemplo
	Garantias, Previsões e Limitações (1)
	Garantias, Previsões e Limitações (2)
	Garantias, Previsões e Limitações (3)
	Garantias, Previsões e Limitações (4)
	Algoritmos – Síntese da Aula 4