Conceitos Fundamentais de Análise de Algoritmos

Prévia do material em texto

Análise de Algoritmos
CONCEITOS FUNDAMENTAISCONCEITOS FUNDAMENTAIS
Bacharelado em Ciência da Computação
Flávia Coelho
flaviacoelho@ufersa.edu.br
Atualizado em Fevereiro de 2016
 
Conteúdo
● Introdução
● Análise de Algoritmos
● Complexidade Computacional
● Revisão Matemática
● Funções de Complexidade
● Notação Assintótica
● Técnicas de Análise de Algoritmos
● Leitura Recomendada
 
Problema Computacional
● Relaciona a entrada e a saída 
desejada
● Uma instância é um possível valor de 
entrada
ORDENAÇÃO
Entrada: Uma sequência de n números a
1
, a
2
, ..., a
n
Saída: Uma reordenação da sequência de entrada a
1
', a
2
', ..., 
 a
n
', onde a
1
' ≤ a
2
' ≤ … ≤ a
n
' (ordem crescente) ou 
 a
1
' ≥ a
2
' ≥ … ≥ a
n
' (ordem decrescente)
ORDENAÇÃO
Entrada: Uma sequência de n números a
1
, a
2
, ..., a
n
Saída: Uma reordenação da sequência de entrada a
1
', a
2
', ..., 
 a
n
', onde a
1
' ≤ a
2
' ≤ … ≤ a
n
' (ordem crescente) ou 
 a
1
' ≥ a
2
' ≥ … ≥ a
n
' (ordem decrescente)
50, 23, 10, 1, -8, 1004 é uma instância para a ordenação!50, 23, 10, 1, -8, 1004 é uma instância para a ordenação!
 
Algoritmo
● Representa um conjunto bem 
definido de instruções que toma 
um valor de entrada (ou conjunto 
de valores) e produz algum valor 
(ou conjunto de valores) como 
saída – solução de um problema
● Algoritmo é uma tecnologia!
● É tão importante quanto hardware 
rápido, interfaces intuitivas, sistemas 
orientados a objetos, etc.
 
Avaliação de Algoritmos
● Corretude
● Um algoritmo está correto se para toda entrada 
(legal) ele produz a saída correta
● Simplicidade
● Um algoritmo é simples se é de fácil entendimento, 
implementação e manutenção
● Eficiência (em função do tamanho da entrada)
● Busca-se melhor desempenho, qualidade de serviço e 
uso adequado de recursos de processamento e 
armazenamento
● Quanto tempo o algoritmo gasta para produzir a 
saída correta?
● Quanto espaço de memória é necessário?
 
Analisar um algoritmo é 
estudar o seu 
comportamento frente a 
diferentes tamanhos e valores 
de entrada para produzir a 
saída esperada 
 
Conteúdo
● Introdução
● Análise de Algoritmos
● Complexidade Computacional
● Revisão Matemática
● Funções de Complexidade
● Notação Assintótica
● Técnicas de Análise de Algoritmos
● Leitura Recomendada
 
Como Predizer a Eficiência de 
um Algoritmo?
● Estimativa de tempo e recursos 
consumidos
● Linguagem de programação utilizada
● Estruturas de dados utilizadas
● Estilo de programação
● Compilador
● Arquitetura de máquina
● Ambiente de execução
 
Possibilidades Reais para 
Analisar Algoritmos
● 1) Codificar o algoritmo usando uma 
linguagem de programação, executar o 
programa e medir o tempo gasto
● Há dificuldade de medir o tempo gasto
● Máquina, linguagem de programação, 
compilador, dados de entrada têm que ser 
idênticos para que a comparação entre 2 ou mais 
algoritmos seja coerente
● 2) Definir uma medida de custo para cada 
instrução do algoritmo e derivar uma 
operação matemática para o tempo de 
execução
 
Comparação entre 
Algoritmos
● Recursos tipicamente analisados
● Espaço de armazenamento
● Tempo de execução
● Para comparar os diferentes 
algoritmos, de forma justa, é 
necessário definir um modelo 
abstrato de máquina
 
Modelo RAM (Random-Access 
Machine)
● Modelo de computação genérico com um único 
processador
● Hirarquia de memória não modelada
● Tipos 
● Inteiros e ponto flutuante
● Instruções
● Aritméticas (adição, subtração, multiplicação, 
divisão, resto)
● Movimentação de dados (carregar, armazenar, 
copiar)
● Controle (desvio condicional e incondicional, 
chamada e retorno de rotina)
 
Tempo de Execução
● Vamos caracterizar o tempo de 
execução de um algoritmo como função 
do tamanho da entrada
● A medida de complexidade dá uma idéia 
de como varia o tempo de execução de 
uma implementação de um algoritmo 
quando varia o tamanho da entrada
● Por exemplo, numa inversão de matrizes, o 
número de operações (adição e multiplicação) 
varia com a dimensão da matriz, ou na 
ordenação de uma lista, varia com o número de 
elementos da lista
 
Medição Empírica do Tempo 
de Execução
● Obtenção do tempo através da execução 
propriamente dita (em um computador real)
● Resultados dependem do compilador, hardware, quantidade 
de memória disponível, etc...
● Experimentos são realizados sobre um conjunto limitado de 
entradas de teste 
● É difícil comparar os tempos de execução 
de 2 ou mais algoritmos, a menos que 
executados sob o mesmo ambiente 
(hardware + software) e condições
● É necessário implementar o algoritmo e executá-lo para 
estudar o tempo de execução
 
Medição Analítica do Tempo 
de Execução
● Obtenção de uma ordem de grandeza do 
tempo de execução independente do 
computador, linguagem de programação, 
compilador e condições locais de 
processamento
● Tem por base uma EXPRESSÃO MATEMÁTICA que 
traduz o comportamento do algoritmo
● Considera todas as entradas possíveis
● É fácil comparar os tempos de execução de 
2 ou mais algoritmos independente de 
hardware e software
● Pode ser efetuada considerando o algoritmo 
em si
 
Análise Analítica de 
Algoritmos
● Resulta em uma função T(n), real e 
não negativa
● n é o tamanho da entrada, n ≥ 0
● T(n) caracteriza o tempo de execução 
em função do tamanho da entrada n
● Representa a quantidade estimada de 
passos necessários para a execução do 
algoritmo para uma entrada de tamanho 
n
 
Passo
● É independente de máquina
● Operação com tempo de execução constante 
ou execução de um número fixo de operações 
básicas de tempo constante
● Exemplos
● Atribuição de valores a variáveis
● Chamadas de métodos
● Operações matemáticas
● Comparação entre 2 valores
● Seguir uma referência a um objeto
● Retorno de um método
 
Exemplo
● Passo = operação de atribuição
 
Na Prática...
● Estamos interessados em contar 
o número de passos executados
● Usamos tal valor como estimativa 
de tempo de execução de um 
algoritmo
● A contagem se relaciona com o 
tempo de execução no RAM, pois 
cada passo corresponde a uma 
instrução realizada em tempo 
constante
 
Exemplo
Encontrar o menor elemento de um vetor A de inteiros, 
com n elementos
int calculamenor (int A[], int n){
 int i, menor;
 menor = A[0];
 for (i = 1; i < n; i++){
 if (A[i] < menor)
 menor = A[i];
 }
 return menor;
}
São realizadas n-1 
comparações, 
então T(n) = n - 1
 
Medidas de Complexidade
Um algoritmo pode executar mais rapidamente sobre 
algumas entradas do que sobre outras do mesmo tamanho
● Pior caso
● Corresponde ao maior tempo de 
execução sobre todas as entradas 
de tamanho n
● Melhor caso
● Corresponde ao menor tempo de 
execução sobre todas as entradas 
de tamanho n
 
Medidas de Complexidade
Um algoritmo pode executar mais rapidamente sobre 
algumas entradas do que sobre outras do mesmo tamanho
● Caso médio (ou esperado)
● Comportamento médio do algoritmo frente a 
variados e significativos valores de entrada
● Para muitos algoritmos, é difícil determinar o 
caso médio 
– Seria preciso considerar as n! permutações de 
entrada ocorrem com a mesma probabilidade
● Estimativa razoável
– Média dos tempos de execução sobre todas as 
entradas de tamanho n
 
Exemplo
Pesquisa Sequencial
● Problema: acessar os registros de um 
arquivo
● Cada registro possui uma chave única que 
é utilizada para recuperaçãode registros 
do arquivo
● Dada uma chave qualquer, o problema 
consiste em localizar o registro que 
contenha esta chave
● O algoritmo de pesquisa mais simples que 
existe é o que faz uma pesquisa sequencial
 
Exemplo
Pesquisa Sequencial
● Seja T uma função de complexidade tal 
que T(n) é o número de registros 
consultados no arquivo, isto é, o número 
de vezes que a chave de consulta é 
comparada com a chave de cada registro
● Casos a considerar
● Melhor caso: T(n) = 1 
● Pior caso: T(n) = n
● Caso médio: T(n) = (n+1)/2
 
Exemplo
Pesquisa Sequencial
● O melhor caso ocorre quando o registro 
procurado é o primeiro consultado
● O pior caso ocorre quando o registro 
procurado é o último consultado, ou 
então não está presente no arquivo
● Para o caso médio vamos considerar 
que toda pesquisa recupera um registro, 
não existindo pois pesquisa sem 
sucesso e, assim, a pesquisa examina 
aproximadamente metade dos registros
 
Conteúdo
● Introdução
● Análise de Algoritmos
● Complexidade Computacional
● Revisão Matemática
● Funções de Complexidade
● Notação Assintótica
● Técnicas de Análise de Algoritmos
● Leitura Recomendada
 
Logaritmos
Propriedades
● logb1 = 0
● logbb = 1
● a = blogba
● logc(ab) = logca + logcb
● logban = n.logba
● logca = logba / logbc 
● logba = 1 / logab
 
Somatórios
Série Aritmética (PA )
● Dada uma PA finita, a soma de 
seus termos é dada por
● Onde a1 é o primeiro termo da 
sequência, an é o último e n, o 
número de elementos da soma
S n=∑
k=1
n
ak=
a1an. n
2
 
Somatórios
Série Geométrica (PG)
● Dada uma PG finita, a soma de 
seus termos é dada por
● Onde a1 é o primeiro termo da 
sequência, q é a razão da 
progressão e n, o número de 
elementos da soma
Sn=∑
k=1
n
ak=
a1 .q
n−1
q−1
 
Polinômios
 
Exercício de Fixação 01
Quanto vale k no final da execução 
do seguinte trecho de código?
 k = 0;
 for (i=1; i <= n; i++)
 for(j = i; j <= n; j++)
 k = k + 1;
 
Conteúdo
● Introdução
● Análise de Algoritmos
● Complexidade Computacional
● Revisão Matemática
● Funções de Complexidade
● Notação Assintótica
● Técnicas de Análise de Algoritmos
● Leitura Recomendada
 
Funções de Complexidade
● Função Constante
● Função Logaritmo
● Função Linear
● Função nlgn
● Função Quadrática
● Função Cúbica e Polinomiais
● Função Exponencial
● Função Fatorial
 
Função Constante
● f(n) = c, para alguma constante 
fixa c
● Para qualquer argumento n, f(n) 
atribui o valor c
● Útil para caracterizar o número de 
passos necessários para executar 
uma operação básica
● Por exemplo, adição de 2 valores, atribuição de um 
valor ou comparação de 2 valores
 
Função Logaritmo
● f(n) = logbn, para b > 1
● A aproximação de base 2 é típica em 
Análise de Algoritmos, pois uma 
operação comum em vários 
algoritmos é dividir 'repetidamente' 
uma entrada pela metade
● Por exemplo, na pesquisa binária!
● Útil para caracterizar algoritmos que 
resolver um problema transformando-
o em problemas menores
 
Função Linear
● f(n) = n
● Útil quando se executa uma 
operação básica sobre cada um 
dos n elementos da entrada
● Por exemplo, comparar o valor x 
com cada elemento de um arranjo 
de tamanho n, requer n 
comparações
 
Função nlgn
● f(n) = nlgn
● Útil para algoritmos que 
trabalham com o método de 
divisão-e-conquista
● Por exemplo, o algoritmo de 
ordenação rápida (QuickSort)
 
Função Quadrática
● f(n) = n2
● Útil para os algoritmos que 
possuem laços aninhados, com 
n.n operações
 
Função Cúbica e outras 
Polinomiais
● f(n) = n3
● f(n) = a0 +a1.n + a2.n2 + … + 
adnd, onde a0, a1, a2, …, ad ≠ 0 
são coeficientes, e d indica a 
maior potência (grau) do 
polinômio
 
Função Exponencial
● f(n) = bn, onde b é a base e n, o expoente
● Útil para algoritmos que, por exemplo, 
possuem um laço que inicia executando 
uma operação e dobra o número de 
operações a cada iteração
● O número de operações executadas na n-
ésima iteração é 2n
● Ocorrem quando se usa força bruta 
(pesquisa exaustiva) para resolver um 
problema
 
Taxas de Crescimento
 
Alguns Números
Custo Tamanho N
10 20 30 40 50 60
n 0,00001s 0,00002s 0,00003s 0,00004 s 0,00005s 0,00006s
n2 0,0001s 0,0004s 0,0009s 0,0016s 0,0025s 0,0036s
n3 0,001s 0,008s 0,027s 0,64s 0,125s 0,216s
n5 0,1s 3,2s 24,3s 1,7min 5,2min 13min
2n 0,001s 1s 17,9min 12,7dias 35,7ano 366sec
3n 0,059s 58min 6,5anos 3855sec 108sec 1013sec
 
Recomendação
● Operações de estruturas de dados 
devem executar em tempo constante ou 
logarítmico
● Algoritmos devem executar em tempo 
linear ou nlgn
● Algoritmos com tempo quadrático/cúbico 
são pouco práticos e os de tempo 
exponencial são impraticáveis (exceto 
para pequenas entradas)
 
Exercício de Fixação 02
● Para alguns problemas, podemos 
"estimar" a complexidade de 
execução de um algoritmo, com base 
em algumas de suas características...
● Que tipos de problemas ou algoritmos 
costumam ter complexidade da ordem de 
nlgn e como os identificamos?
● Quais problemas que possuem geralmente 
complexidade da ordem de lgn? 
● Quais os problemas que costumam ser 
exponenciais?
 
Conteúdo
● Introdução
● Análise de Algoritmos
● Complexidade Computacional
● Revisão Matemática
● Funções de Complexidade
● Notação Assintótica
● Técnicas de Análise de Algoritmos
● Leitura Recomendada
 
Notação Assintótica
● Notação matemática para funções que 
desconsidera fatores constantes
● Relacionando com as medidas de 
complexidade
● Tempo de execução no pior caso → limite 
superior do tempo de execução para qualquer 
entrada, expresso em funçaõ do seu tamanho
● Tempo de execução no melhor caso → limite 
inferior do tempo de execução para qualquer 
entrada, expresso em função do seu tamanho
 
Notação Assintótica
● Considera aproximações do tempo 
de execução para a quantidade de 
passos de um algoritmo em função 
de entradas suficientemente 
grandes e representativas
● O tempo de execução cresce de 
acordo com o tamanho da entrada 
n
 
Notação O (Big-Oh)
● Estabelece um limite assintótico 
superior
● g(n) domina assintoticamente 
outra função f(n)
● f(n) é O(g(n)) se para uma constante real 
c > 0 e uma constante inteira n0 ≥ 1, tal 
que f(n) ≤ cg(n), para n ≥ n0
 
Notação O (Big-Oh)
● Com a notação O, podemos 
afirmar que f(n) é menor que ou 
igual a outra função g(n) até um 
fator constante e de modo 
assintótico, à medida que n 
cresce para infinito
● Exemplos
● f(n) = 8n – 2 é O(n), para n ≥ 1
 
Propriedades da Notação O
● Se f(n) é um polinômio de grau d, f(n) 
= a0 + a1n + … + adnd, com ad > 0, 
então f(n) é O(nd)
● f(n) é O(f(n))
● c.O(f(n)) = O(f(n))
● O(f(n)) + O(f(n)) = O(f(n))
● O(f(n)) + O(g(n)) = O(max(f(n),g(n))
● O(f(n)).O(g(n)) = O(f(n).g(n))
● f(n).O(g(n)) = O(f(n).g(n))
 
Complexidade com a 
Notação O
 
O(1) 
O(log2n) 
O(n1/2) 
O(n) 
O(n.log2n) 
O(n²) 
O(n³) 
O(2n) 
O(n.2n) 
O(n!) 
 
Mais lento, maior crescimento Mais lento, maior crescimento 
nc = polinomiais 
Mais rápido, menor crescimento 
cn = exponencial 
 
Exercício de Fixação 03
Calcular formalmente a ordem 
de cada função a seguir, 
utilizando a notação O
● 5n2 + 3nlgn + 2n + 5
● 3lgn + 2
● 2n+2
 
Exercício de Fixação 04
● O número de operações 
executadas pelos algoritmos A e 
B é 8nlgn e 2n2, 
respectivamente. Determine n0 
tal que A seja melhor que B  n ≥ 
n0
 
Notação Ω (Ômega)
● Com essa notação,podemos afirmar 
que uma função é assintoticamente 
maior ou igual a outra, exceto por 
um fator constante 
● Limite assintótico inferior
● f(n) é Ω(g(n)) se g(n) é O(f(n)), ou 
seja, se existe uma constante c > 0 
e n0 ≥ 1, tal que f(n) ≥ cg(n), 
para n ≥ n0
 
Notação Ω (Ômega)
● Modo assintótico de informar que 
uma função cresce a uma taxa que 
é ”maior ou igual” a uma outra 
função
● Exemplos
● f(n) = 3nlgn + 2n é Ω(nlgn), para n 
≥ 2
● f(n) = 3n3 + 2n2 é Ω(n3), para n ≥ 0
 
Entendo as Notações O e Ω 
● Quando o tempo de execução de um algoritmo 
é O(n2), afirma-se que para qualquer valor de 
n, não importando que entrada específica de 
tamanho n seja escolhida, o tempo de 
execução sobre essa entrada tem um limite 
superior determinado por c.n2
● Quando o tempo de execução de um algoritmo 
é Ω(n2), significa que independentemente da 
entrada específica de tamanho n escolhida 
para cada valor de n, o tempo de execução 
sobre ela é pelo menos (limite inferior) c.n2, 
para um valor de n suficientemente grande
 
Exercício de Fixação 05
● Justifique porque as duas 
afirmações, a seguir, são 
equivalentes
● O tempo de execução do algoritmo 
A é O(f(n))
● No pior caso, o tempo de execução 
do algoritmo A é O(f(n))
 
Notação  (Theta)
● Utilizada para afirmar que 2 funções crescem 
à mesma taxa, até fatores constantes
● f(n) é (g(n)) se f(n) é O(g(n)) e f(n) é 
Ω(g(n)), ou seja, existem constantes c1 > 0 e 
c2 > 0 e n0 ≥ 1, tal que c1g(n) ≤ f(n) ≤ c2g(n), 
para n ≥ n0
● Exemplos
● f(n) = 4n + 5nlgn é (nlgn)
● f(n) = 2n2 – 3n é (n2)
 
Notação Assintótica
Propriedades Gerais
 
Notação Assintótica
Regras Úteis
● Constantes multiplicativas podem ser 
omitidas
● Exemplo: 14n2 torna-se n2
● na domina nb, se a > b
● Exemplo: n2 domina n
● Qualquer exponencial domina qualquer 
polinomial
● Exemplo: 3n domina n5
● Qualquer polinomial domina qualquer 
logaritmo
● Exemplo: n domina (lgn)3
 
Exercício de Fixação 06
● O professor Pardal conta para 
seus alunos que é 
assintoticamente mais rápido 
elevar um número de n bits ao 
quadrado do que multiplicar dois 
inteiros de n bits. Eles devem 
acreditar nele?
 
Exercício de Fixação 07
● Qual algoritmo você prefere: um 
que requer n100 passos ou um 
que requer 2n passos? Justifique
 
Exercício de Fixação 08
● Por que a frase ”O tempo de 
execução de um algoritmo é no 
mínimo O(n2)” não tem sentido. 
Existe outra notação assintótica 
que poderia ser usada nesta 
frase? 
 
Exercício de Fixação 09
● Dadas as expressões matemáticas, 
determine para cada uma delas
● (i) o comportamento assintótico de cada 
função
● (ii) o comportamento assintótico resultante 
(aplicando as propriedades da complexidade 
assintótica) para f(n) + g(n)
● (iii) comente qual é a função com menor 
tempo de execução e justifique
a) f(n) = n – 4 e g(n) = 2lgn 
b) f(n) = n + 2 e g(n) = 5n2 
 
Exercício de Fixação 10
● Suponha um algoritmo com 3 
trechos apresentando os 
seguintes tempos de execução: 
O(n2), O(n) e O(nlgn). Qual é o 
comportamento assintótico 
correspondente ao algoritmo? 
Justifique
 
Notação o
● Uma função g(n) é o(f(n)) se, para qualquer 
constante c > 0, então 0 ≤ g(n) < cf(n) para 
todo n ≥ n0
● g(n) tem um crescimento muito menor que f(n) 
quando n tende para o infinito
● Exemplo
● 2n é o(n2)
● Qual é a diferença entre o e O?
● Em g(n) = O(f(n)), a expressão 0 ≤ g(n) ≤ cf(n) é 
válida para alguma constante c > 0, mas em g(n) 
= o(f(n)), a expressão 0 ≤ g(n) < cf(n) é válida 
para todas as constantes c > 0
 
Notação 
● Uma função g(n) é (f(n)) se, para 
qualquer constante c > 0, então 0 
≤ cf(n) < g(n) para todo n ≥ n0
● Exemplo
● n2/2 é (n)
● A notação  está relacionada com a 
notação  da mesma forma que a 
notação o está relacionada à notação O
 
Conteúdo
● Introdução
● Análise de Algoritmos
● Complexidade Computacional
● Revisão Matemática
● Funções de Complexidade
● Notação Assintótica
● Técnicas de Análise de Algoritmos
● Leitura Recomendada
 
Técnicas de Análise
● Utilizam estratégias de matemática 
discreta
● Contagem ou enumeração de elementos 
de um conjunto que possuam uma 
propriedade em comum
● Manipulam somas, produtos, 
permutações, fatoriais, coeficientes 
binomiais, solução de equações de 
recorrência, entre outras operações...
 
Uma Proposta
● Não existe um conjunto completo 
de regras para a análise de 
algoritmos
● Vamos considerar as regras 
enumeradas por Aho, Hopcroft e 
Ullman (1993)
● Utilizando as propriedades da 
Notação O
 
Regra 1 – Comandos Básicos
● O tempo de execução de um comando 
de atribuição, de leitura ou de escrita 
pode ser considerado O(1)
● Complexidade constante
● Exemplo
a = b + 1;       → O(1)
● Existem exceções para as linguagens que 
permitem a chamada de funções em comandos 
de atribuição, ou quando atribuições envolvem 
vetores de tamanho arbitrariamente grandes
 
Regra 2 – Sequência de 
Comandos 
● O tempo de execução de uma seqüência 
de comandos é determinado pelo maior 
tempo de execução de qualquer comando 
da seqüência
● Exemplo
a = b + 1;    → O(1)
c = 1;        → O(1)
pesquisa(n)   → O(n)  [maior custo] 
O(n) 
 
Exercício de Fixação 11
● Dado um arranjo X com n 
elementos, o algoritmo B escolhe 
lgn elementos de X, 
aleatoriamente, e executa um 
cálculo em tempo O(n) para cada 
um. Qual é o pior caso em 
relação ao tempo de execução de 
B?
 
Regra 3 – Comandos de 
Decisão
● O tempo de execução de um comando 
de decisão é composto pelo tempo de 
execução dos comandos internos mais 
o tempo de avaliação da condição
● Avaliar a condição é O(1)
● Exemplo
se b > a então      → O(1)  
     b = a;         → O(1)
fimse   O(1)
 
Regra 4 – Laços 
● O tempo para execução de um laço 
compreende o tempo de execução do 
corpo do laço mais o tempo de avaliação 
da condição para terminação, multiplicado 
pelo número de iterações do laço
● Avaliar a condição é O(1)
● Exemplo
para i de 1 até n faça  → n.O(1) = O(n)
i = i + 1;         → O(1)
fimpara
 
Técnicas de Análise de 
Algoritmos
Exemplo – Soma Média Pré-Fixada
Algoritmo SomaMédiaPréFixada
Entrada: Arranjo X com n elementos
Saída: Arranjo A com n elementos, tal que A[i] é 
a média de X[0] até X[i] = Si/(i+1)
Seja A um arranjo de n valores
S = 0 
para i = 0 até (n-1) faça
 S = S + X[i]
 A[i] = S/(i+1)
retorne A
→ O(1)
→ O(1)
→ O(1)
→ O(n), pois i = 0 a (n-1) = 
(n-1) – 0 + 1 = n vezes
→ O(n)
 
Exercício de Fixação 12
● O algoritmo A executa uma 
computação em tempo O(lgn) 
para cada entrada de um arranjo 
de n elementos. Qual o pior caso 
em relação ao tempo de 
execução de A?
 
Técnicas de Análise de 
Algoritmos
Exemplo – Ordenação 
● Considere a ordenação de n elementos 
de um vetor v
● Selecione o menor elemento do vetor
● Troque esse elemento com o primeiro 
elemento v[0]
● Repita as operações anteriores com os 
n-1 elementos restantes, depois com 
os n-2 elementos, até que reste 
apenas 1 elemento
 
public class Ordenacao{
 public static void ordena(int v[], int n){
 for (int i = 0; i < n – 1; i++){
 int min = i;
 for (int j = i + 1; j <= n; j++)
 if(v[j] < v[min])
 min = j;
 int x = v[min];
 v[min] = v[i];
 v[i] = x;
 }
 } }
→ O(1)
→ O(1)
→ O(1)
→ O(n-i), 
pois j = i+1 
a n → n – 
(i+1) + 1 = 
n - i vezes
O(n2), pois i = 0 a 
n-2 (ou de 1 a n-1) = (n - 1) vezes
O laço interno é 
executado 1 + 2 + 
3 + … + (n-1) 
vezes! 
Portanto, (1+(n-1)
(n-1))/2  O(n2)
→ O(1)
Técnicas de Análise de 
Algoritmos
Exemplo – Ordenação
→ O(1)
→ O(1)
 
Exercício de Fixação 13
Efetue a análise assintótica do seguinte 
código
Algoritmo Exemplo
 Entrada: um arranjo A que armazena n ≥ 
1 elementos
 Saída: a soma dos elementos de A
 s ← A[0]
 para i ← 1 até n-1 faça
 s ← s + A[i]
 retorna s
 
Algoritmo MédiaPréFixada
Entrada: Arranjo X com n elementos
Saída: Arranjo A com n elementos, tal que A[i] é 
a média de X[0] até X[i]
Seja A um arranjo de n elementos
para i = 0 até (n-1) faça
 a = 0 
 para j = 0 até i faça
 a = a + X[j]
 A[i] = a/(i+1)
retorne A
→ O(1)
→ O(1)
→ O(1)
→ O(n2), pois j = 1 a i = i – 0 
+ 1 = (i + 1) vezes
O laço interno é executado 1 
+ 2 + 3 + … + n vezes! 
Portanto, (1+n)n/2  O(n2)
→ O(n)
Técnicas de Análise de 
Algoritmos
Exemplo – Média Pré-Fixada
 
Exercício de Fixação 14
Efetue a análise assintótica do seguinte código
Algoritmo Exemplo
 Entrada: um arranjo A que armazena n ≥ 1 
elementos
 Saída: a soma da soma dos prefixos de A
 s ← 0
 para i ← 0 até n-1 faça
 s ← s + A[0]
 para j ← 1 até i faça
 s ← s + A[j]
 retorna s
 
Exercício de Fixação 15
● Em função do tamanho n da 
entrada, qual o número de vezes 
que a operação m = m + c[i][j] é 
executada no laço for mais 
interno do seguinte trecho de 
programa? Justifique
for(i = 1; i < n-1; i++) 
for(j = 0; j < i; j++) 
 m = m + c[i][j]; 
 
Exercício de Fixação 16
● Efetue a análise da complexidade para o melhor, pior 
e médio caso
void ordena (int n, int* v){
 int i,j;
 for (i = n-1; i >= 1; i--)
 for (j = 0; j < i; j++)
 if (v[j] > v[j+1]){ /*troca*/
 int temp = v[j];
 v[j] = v[j+1];
 v[j+1] = temp;
 }
}
 
Exercício de Fixação 17
● A solidez de um vetor A[p..r] é a soma de um segmento de 
soma máxima. Se o vetor não tem elementos negativos, sua 
solidez é a soma de todos os elementos. Se todos os 
elementos são negativos, a solidez é o valor de seu elemento 
menos negativo. Analise a complexidade do algoritmo
solidez (A, p, r){
 x ← A[r]
 para q ← r – 1 decrescendo até p faça
 s ← 0
 para j ← q até r faça
 s ← s + A[j]
 se s > x então x ← s
 devolva x
}
 
Exercício de Fixação 18
● Analise a complexidade do 
seguinte algoritmo
x ← 0
para i ← 1 até n faça
 para j ← i+1 até n faça
 para k ← 1 até j-1 faça
 x ← x + 1 
 
Regra 5 – Algoritmos Não-
Recursivos
● O tempo de execução de cada 
procedimento deve ser computado 
separadamente um-a-um, iniciando pelos 
procedimentos que não chamam outros 
procedimentos
● Em seguida, devem ser avaliados os 
procedimentos que chamam 
procedimentos que não chamam outros, 
utilizando os tempos dos procedimentos já 
avaliados 
● Este processo é repetido até chegar ao 
programa principal
 
Regra 5 – Exemplo 
PA; /*procedimento A*/  
c = c + 1;                  → O(1) 
PB; /*procedimento B*/
PA | d = 1;          → O(1) [Procedimento que chama outro]       
   | PC; /*procedimento C*/
   | e = d + 100;
PB | f = 1;          → O(1) [Procedimento que não chama outro]
   | g = f + 6;
  
PC | h = 8;          → O(1) [Procedimento que não chama outro]      
 
Regra 6 – Algoritmos 
Recursivos
● Quando o programa possui procedimentos 
recursivos, para cada procedimento é associada 
uma função de complexidade f(n) desconhecida, 
onde n mede o tamanho dos argumentos para o 
procedimento, utilizando relações de recorrência
● Exemplo
pesquisa (n){
    se n   1≤
       então retorne n;   //recursivo
    senão pesquisa (n/2);
}
   f(1) = 1, f(n) = f(n/2)
 
Entendendo Recorrências
● Uma função que chama a si mesma 
é dita recursiva
● Exemplo
● O fatorial de um número n, para n ≥ 
0, é definido por
● Implementando 
n !={ 1, se n=0 ou n=1n∗n−1! , sen1}
int fatorial (int n){
 int res;
 if (n == 0 || n == 1)
 res = 1;
 else 
 res = n * fatorial (n-1);
 return res;
}
 
Recorrência
● É uma equação ou desigualdade que 
descreve uma função em termos de 
seu valor em entradas menores
● A idéia para resolver recorrências é 
expandir a recorrência e expressá-la 
como um somatório de termos 
dependentes de N e das condições 
iniciais
● Para o exemplo do fatorial, tem-se a 
recorrência T n={ 1, se n=0ou n=1T n−11, se n1}
 
Recorrência 
Exemplo 
● Para o fatorial, temos
● T(n) = T(n-1) + 1, para n > 1 e T(1)=1, 
portanto
T(n) = T(n-2) + 1 + 1
 = T(n-3) + 1 + 1 + 1
 …
 = T(n-k) + k
● Precisamos conhecer o valor de k
– Quando n-k=1, T(1) = 1 (condição de 
parada)
 
Recorrência 
Exemplo 
T(n) = T(n-k) + k
● k = n-1, portanto
T(n) = T(1) + (n-1)
 = 1 + (n-1)
● Sendo assim, para o fatorial, tem-
se o tempo de execução
T(n) = n
 
Recorrência
Método da Expansão Telescópica
● A idéia básica é expandir a relação 
de recorrência até que possa ser 
detectado o seu comportamento no 
caso geral
● Foi exatamente o que fizemos para 
a relação de recorrência do fatorial!
● Para tanto, consideramos que uma 
relação de recorrência sempre é 
obtida de um algoritmo recursivo 
que, por sua vez, possui uma 
condição de parada para a 
recursão
 
Recorrência
Exemplo, usando o método da expansão
● T(N) = T(N-1) + N para n≥2, T(1)=1 (i)
● Como T(N-1) = T((N-1)-1) + (N-1) = T(N-2) + 
(N-1)
● Substituindo T(N-1) em (i), temos
T(N) = T(N-2) + (N-1) + N
● Fazendo o mesmo para T(N-2), obtemos
T(N) = T(N-3) + (N-2) + (N-1) + N
● E assim, sucessivamente...
T(N) = T(N-4) + (N-3) + (N-2) + (N-1) + N
T(N) = T(N-k) + (N -(k-1)) + (N-(k-2)) + … + 
N
 
Recorrência
Exemplo, usando o método da expansão
T(N) = T(N-k) + (N -(k-1)) + (N-(k-2)) + … + N
● Temos que obter N-k = 1 para finalizarmos a 
recorrência
● Portanto, k = N-1
● Substituindo...
T(N) = T(N-(N-1)) + (N-((N-1)-1) + (N-((N-1)-2)) + … 
+ N
● T(N) = T(1) + 2 + 3 + … + N
● T(N) = 1 + 2 + 3 + … + N, já que T(1)=1
 
Exercício de Fixação 19
● O algoritmo pesquisa inspeciona os n elementos de um conjunto e 
faz uma chamada recursiva sobre as 2 metades (n/2) de elementos
void pesquisa(int n){
 if (n <= 1)
 inspecione elemento e termine
 else{
 para cada um dos n elementos inspecione elemento;
 pesquisa(n/2); //primeira metade
 pesquisa(n/2); //segunda metade
 }
}
● Apresente a relação de recorrência que descreve o comportamento 
do algoritmo
● Apresente a complexidade computacional do algoritmo para o 
melhor e o pior caso
 
Recorrência
Método do Teorema Mestre
● Teorema para resolver recorrências 
na forma T(n) = a.T(n/b) + O(nd), 
sendo a > 0, b > 1 e d  0
● a subproblemas de tamanho n/b e 
combinando as soluções em tempo 
O(nd)
T (n)=
O (nd ) , se d> log a
b
O (nd lgn) , se d=log a
b
O (n
log a
b) , se d< log a
b
 
Recorrência
Exemplos, usando o Teorema Mestre
● T(n) = 9T(n/3) + n3
Identificamos que a = 9, b = 3, n3 é 
O(n3), d = 3
Calculamos logb a = log3 9 = 2
Assim, aplicamos o CASO 1 do 
Teorema Mestre
– Portanto, T(n) é O(nd) = O(n3)
Se d > logb 
a → T(n) é O(nd)
 
Recorrência
Exemplos, usando o Teorema Mestre
● T(n) = T(2n/3) + 1
Identificamos que a = 1, b = 3/2, 1 é 
O(n0), d =0
Calculamos logb a = log3/2 1 = 0
Assim, aplicamos o CASO 2 do 
Teorema Mestre
– Portanto, T(n) é O(nd.lgn) = O(1.lgn) = 
O(lgn)
Se d = logb 
a → T(n) é O(ndlgn)
 
Recorrência
Exemplos, usando o Teorema Mestre
● T(n) = 4.T(n/2) + n
Identificamos que a = 4, b = 2, n é 
O(n), d = 1
Calculamos logb a = log2 4 = 2
Assim, aplicamos o CASO 3 do 
Teorema Mestre
– Portanto, T(n) é O(nlog b a) = O(n2)
 Se d < logb 
a → T(n) é O(nlogba) 
 
Exercício de Fixação 20
● Use o Teorema Mestre, se for 
possível, para apresentar a 
complexidade assintótica para as 
seguintes recorrências
a) T(n) = 4T(n/2) + n
b) T(n) = 4T(n/2) + n2
c) T(n) = 4T(n/2) + n3
 
Exercício de Fixação 21
● Apresente a análise da complexidade do algoritmo 
P
algoritmo P
 Entrada: Uma base a  R e um expoente n  N
 Saída: Potência an
 if n = 1 then
 return a
 else 
 x := P(a, n/2)
 return x * x
 endif
 
Técnicas de Análise de 
Algoritmos
Exemplo – Pesquisa Ternária
void pesquisa(n){
 if(n <= 1)
 'inspecione elemento' e termine
 else{
 Para cada um dos n elementos 'inspecione elemento'
 pesquisa(n/3);
 }
}
→ O(1)
→ O(1)
O(n) → 
T(n) = T(n/3) + n
T(1) = 1
 
Técnicas de Análise de 
Algoritmos
Exemplo – Pesquisa Ternária
● Desenvolvendo a recorrência (método do 
teorema mestre)
● T(n) = T(n/3) + n
Identificamos que a = 1, b = 3, n é O(n), d = 1 
Calculamos logb a = log3 1 = 0
Assim, aplicamos o CASO 1 do Teorema Mestre
– Portanto, T(n) é O(nd) = O(n)
 
Técnicas de Análise de 
Algoritmos
Exemplo – Pesquisa Ternária
● Desenvolvendo a recorrência (método da expansão 
telescópica)
T(n) = n + T(n/3)
 = n + n/3 + n/3/3 + … + T(n/3/3.../3)
 = n + n(1/3) + n(1/32) + … + T(n/3k)
Portanto, uma PG de razão 1/3, multiplicada por n e 
adicionada de T(n/3k)
Precisamos descobrir o valor de k...
n/3k = 1 → n = 3k → k = log3n
 
Técnicas de Análise de 
Algoritmos
Exemplo – Pesquisa Ternária
● Desenvolvendo a recorrência
T(n) = n + n(1/3) + n(1/32) + … + T(n/3k)
E lembrando que 
Temos...
a
log b
a=b Sn=∑
k=1
n
ak=
a1 .1−q
n
1−q
T (n)=n .∑
k=0
log n
3
(1 /3)k
T n=n . 1−1/3log n31−1 /3 
 
Técnicas de Análise de 
Algoritmos
Exemplo – Pesquisa Ternária
● Continuando...
T n=n . 1−1/3log n32 /3  a logba=b
T n=n . 1−1/n log332 /3 
T n=n . 1−1/n2 /3 
 
Técnicas de Análise de 
Algoritmos
Exemplo – Pesquisa Ternária
● Continuando...
T n=n . n−1/n2 /3 
T (n)=n .( 3(n−1)2n )
T (n)=
3(n−1)
2
 
Exercício de Fixação 22
● Efetue a análise da complexidade do algoritmo para o 
cálculo da potência
algoritmo potencia(x, n):
 Entrada: um número x e um inteiro n  0 
 Saída: o valor de xn
 se n = 0 entao
 retorna 1
 se n é ímpar entao
 y = potencia(x, (n-1)/2)
 retorna x*y*y
 senao
 y = potencia(x, n/2)
 retorna y*y
 
Exercício de Fixação 23
● Resolva as recorrências e determine a 
complexidade assintótica, usando a 
Notação O correspondente
a) T(N) = c + T(N-1), para N > 1 e T(1) = 0
b) T(N) = T(N/2) + 1, para N ≥ 2 e T(1) = 
1
c) T(N) = 2T(N/2) + N, para N ≥ 2 e T(1) = 
0
d) T(N) = 2T(N-1) + 1, para N≥ 2 e T(1) = 
1
 
Exercício de Fixação 24
● Suponha que é preciso escolher entre 2 
algoritmos distintos
● Algoritmo A soluciona problemas de tamanho n 
resolvendo recursivamente 2 subproblemas de 
tamanho n/2 e combinando as soluções em tempo 
O(1)
● Algoritmo B soluciona problemas de tamanho n 
calculando 9 valores em tempo constante e 
combinando as respostas em tempo O(n2)
Para ambos, considere T(1) = 1. Apresente a 
função de tempo de execução para cada 
algoritmo e indique-o em notação O. Qual você 
indicaria? Justifique
 
Exercício de Fixação 25
● Suponha que você precisa escolher entre os seguintes 
seguintes algoritmos
● Algoritmo A resolve problemas dividindo-os em cinco 
subproblemas de metade do tamanho, solucionando 
cada subproblema recursivamente e, então, combinando 
as soluções em tempo linear
● Algoritmo B resolve problemas de tamanho n resolvendo 
recursivamente dois subproblemas de tamanho (n-1) e, 
então, combinando as soluções em tempo constante
● Algoritmo C soluciona problemas de tamanho n 
dividindo-os em nove subproblemas de tamanho n/3, 
resolvendo recursivamente cada subproblema e, então, 
combinando as respostas em tempo O(n2)
Qual o tempo de execução de cada algoritmo (em notação 
O) e qual você escolheria? Justifique
 
Leitura Recomendada
N. Ziviani. Projeto de Algoritmos com 
Implementações em Java e C++. Thompson 
Learning, 2007, pp. 3-24, 74, 390-403
M. T. Goodrich, R. Tamassia. Estruturas de Dados e 
Algoritmos em Java. Quarta Edição, Bookman, 
2006, pp. 150-168
T. H. Cormen, C. E. Leiserson, R. L. Rivest. C. Stein. 
Algoritmos. Teoria e Prática. Campus, 2002, pp. 3-
7, 16-20, 32-39
A. F. G. Ascencio, G. S. Araújo. Estruturas de Dados: 
Algoritmos, Análise da Complexidade e 
Implementações em Java e C/C++. Pearson 
Prentice Hall, 2010, pp. 1-20
 
Referências
Material didático elaborado por Jorge César 
Abrantes de Figueiredo, UFCG (Universidade 
Federal de Campina Grande)
Material didático elaborado por Lourdes Mattos 
Brasil, UNB (Universidade de Brasília)
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73
	Slide 74
	Slide 75
	Slide 76
	Slide 77
	Slide 78
	Slide 79
	Slide 80
	Slide 81
	Slide 82
	Slide 83
	Slide 84
	Slide 85
	Slide 86
	Slide 87
	Slide 88
	Slide 89
	Slide 90
	Slide 91
	Slide 92
	Slide 93
	Slide 94
	Slide 95
	Slide 96
	Slide 97
	Slide 98
	Slide 99
	Slide 100
	Slide 101
	Slide 102
	Slide 103
	Slide 104
	Slide 105
	Slide 106
	Slide 107
	Slide 108
	Slide 109
	Slide 110
	Slide 111
	Slide 112
	Slide 113
	Slide 114