Análise e Projeto de Algoritmos

Prévia do material em texto

Análise e Projeto de Algoritmos
Análise de Complexidade
Prof. Rodrigo Freitas Silva
rodrigo.f.silva@ufes.br
Prof. Rodrigo Freitas Silva / UFES 1
Bibliografias utilizadas
1. Aho, A. V.; Hopcroft, J. E.; Ullman, J. D.; The Design and Analysis of 
Computer Algorithms, 1ed, Ed. Addison Wesley, 1974
2. T.H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein; Algoritmos: Teoria e 
Prática, ed.2, Campus, 2002. 
3. Jayme Luiz Swarcfiter, Lilian Markenzon, Estruturas de Dados e Seus
Algoritmos, 2a edition
4. Nivio Ziviani , Projeto De Algoritmos, 2º ed. , 2004
5. Papadimitriou, C. H.; Computational Complexity. 1ed, Ed. Addison Wesley, 
1994. 
6. Garey, M. R.; Johnson, D. S.; Computers and intractability: A guide to the 
theory of NP-completeness. Ed. Freeman, 1979. 
7. Toscani, L. V.; Veloso, P. A. S.; Complexidade de Algoritmos, 2ed, Ed. 
Bookman, 2008. 
Prof. Rodrigo Freitas Silva / UFES 2
Análise de Complexidade dos Algoritmos
Aconselho os meus alunos a terem muito cuidado quando decidirem 
não estudar mais Matemática. Nesse momento, eles devem estar 
preparados para ouvirem o som de portas se fechando 
-- James Caballero
Prof. Rodrigo Freitas Silva / UFES 3
Algoritmos
o Segundo Dijkstra, um algoritmo corresponde a uma descrição de um 
padrão de comportamento, expresso em termos de um conjunto 
finito de ações
o Executando a operação a+b percebemos um padrão de comportamento, 
mesmo que a operação seja realizada para valores diferentes de a e b
Prof. Rodrigo Freitas Silva / UFES 4
Algoritmos: Definições
o Introduction to Algorithms, 2001, 2a ed. (T.H. Cormen):
o Informalmente, um algoritmo é qualquer procedimento computacional 
bem definido que toma algum valor ou conjunto de valores como entrada 
e produz algum valor ou conjunto de valores como saída. Portanto, um 
algoritmo é uma sequência de passos computacionais que transformam a 
entrada na saída
Prof. Rodrigo Freitas Silva / UFES 5
Por que estudar algoritmos?
“Algoritmo é muito mais do que um ramo da ciência da computação. 
É o núcleo da ciência da computação, e com toda a imparcialidade, 
pode ser considerado relevante para a maioria das ciências, negócios 
e tecnologia”
-- David Harel
Prof. Rodrigo Freitas Silva / UFES 6
Observações sobre as definições
o Necessidade de Regras
o Conjunto de regras é finito
o Tempo finito de execução
o Regras são executadas por um computador
Prof. Rodrigo Freitas Silva / UFES 7
Observações sobre as definições: Consequências
o Deve-se definir um repertório finito de regras
o Linguagem de programação
o A maior parte dos algoritmos utiliza métodos de organização de 
dados envolvidos na computação
o Estruturas de dados
o Tempo finito não é uma eternidade
o A maior parte das pessoas não está interessada em algoritmos que levam 
anos, décadas, séculos, milênios para executarem
o Existem diferentes “tipos de computadores”
o Existem diferentes modelos computacionais
Prof. Rodrigo Freitas Silva / UFES 8
Algoritmos como uma Tecnologia
o Suponha que os computadores fossem infinitamente rápidos e a 
memória do computador fosse grátis. Será que você ainda teria 
alguma razão para estudar algoritmos ????
Prof. Rodrigo Freitas Silva / UFES 9
Algoritmos como uma Tecnologia
o Suponha que os computadores fossem infinitamente rápidos e a 
memória do computador fosse grátis. Será que você ainda teria 
alguma razão para estudar algoritmos?
R: A resposta é sim, pois você ainda gostaria de demonstrar 
que seu método de solução termina e o faz com a resposta 
correta.
Prof. Rodrigo Freitas Silva / UFES 10
Algoritmos como uma Tecnologia
o Naturalmente, os computadores podem ser rápidos, mas não são 
infinitamente rápidos.
o A memória pode ser barata, mas não é gratuita
o Tempo de processamento e espaço na memória são recursos limitados
o Estes recursos devem então ser usados com sabedoria, e algoritmos 
que sejam eficientes em termos de tempo ou espaço irá ajudá-lo
Prof. Rodrigo Freitas Silva / UFES 11
Algoritmos: Eficiência
o Diferentes algoritmos podem ser desenvolvidos para resolver o 
mesmo problema, muitas vezes diferem drasticamente em sua 
eficiência. Essas diferenças podem ser muito mais significativas do 
que as diferenças devido à hardware e software
o Exemplo: algoritmos de ordenação
o Merge Sort X Insertion Sort
Prof. Rodrigo Freitas Silva / UFES 12
Algoritmos: Eficiência
o Exemplo: Merge Sort X Insertion Sort
o Insertion sort leva um tempo de aproximadamente c1n
2 para ordenar n
elementos
o Merge sort leva um tempo de aproximadamente c2n lg n
o Onde c1 e c2 são constantes, lg n siginifica log2n, e c1 < c2
o Insertion sort é usualmente mais rápido para pequenos valores de entrada;
o Desde que o tamanho da entrada seja grande o suficiente, o merge sort leva 
vantagem de lg n versos n
Prof. Rodrigo Freitas Silva / UFES 13
Algoritmos: Eficiência
o Exemplo: Merge Sort (c2n lg n) X Insertion Sort (c1n2)
o Suponha dois computadores A e B
• A executa 1G (109) instruções por segundo
• B executa 10M (107) instruções por segundo
• Ou seja, A é 100 vezes mais rápido que B
o Insertion Sort (digamos 2n2) implementado em A
o Merge Sort (digamos 50n log n) implementado em B
o O que acontece quando ordenamos um vetor de um milhão (106) de elementos?
o Qual algoritmo é mais rápido?
Prof. Rodrigo Freitas Silva / UFES 14
Algoritmos: Eficiência
o Exemplo: Merge Sort (c2n lg n) X Insertion Sort (c1n2)
o Insertion Sort (digamos 2n2) implementado em A (109 instruções/segundo)
2(106)2 𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠
109 𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠/𝑠𝑒𝑔𝑢𝑛𝑑𝑜
= ~ 2000 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠
o Merge Sort (digamos 50n log n) implementado em B (107 instruções/segundo)
50 106 log106 𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠
107 𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠/𝑠𝑒𝑔𝑢𝑛𝑑𝑜
= ~ 100 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠
Prof. Rodrigo Freitas Silva / UFES 15
o B executou 20 vezes mais rápido do que A !!!
o Se o vetor tivesse 10 milhões de elementos, a razão seria de 2.3 dias para 20 minutos !!!
Algoritmos: Eficiência
o O uso de um algoritmo no lugar de outro pode levar a ganhos 
extraordinários de desempenho
o Isso é tão importante quanto o projeto de hardware
o A melhoria obtida pode ser tão significativa que não poderia ser obtida 
simplesmente com o avanço da tecnologia
Prof. Rodrigo Freitas Silva / UFES 16
Algoritmos: Aspectos
o Estático:
o Contém instruções que devem ser executadas em uma ordem definida, 
independente do aspecto temporal
o Dinâmico:
o Execução de instruções a partir de um conjunto de valores iniciais, que 
evolui no tempo
o Dificuldade:
o Relacionamento entre o aspecto estático e dinâmico
Prof. Rodrigo Freitas Silva / UFES 17
Algoritmo e Modelo Computacional
o Modelo Computacional: modelo de tecnologia de implementação 
que será usada
o Definição: Esquema que descreve como é o modelo abstrato do 
processamento de algoritmos
o Importância: Um algoritmo não existe, ou seja, não é possível escrevê-lo, 
se antes não for definido o modelo computacional associado
(como será executado)
o Conceito básico no projeto de qualquer algoritmo.
Prof. Rodrigo Freitas Silva / UFES 18
Algoritmo e Modelo Computacional
o Quais modelos existem?
o Literalmente dezenas deles.
o Se não estiver satisfeito, invente o seu!
o O mais popular (usado) de todos: Modelo de computação genérico 
com um único processador
o Modela o computador tradicional e outros elementos computacionais.
Prof. Rodrigo Freitas Silva / UFES 19
Algoritmo e Modelo Computacional: Modelo RAM
o Elementos do modelo:
o Um único processador
o Memória
o Considerações:
o Podemos ignorar os dispositivos de entrada e saída (teclado, monitor, etc)
• Assumindo que a codificação do algoritmo e os dados já estão 
armazenados na memória
o Em geral, não é relevante para a modelagem do problema saber como o 
algoritmo e os dados foram armazenados na memória
Prof. Rodrigo Freitas Silva / UFES 20
Algoritmo e Modelo Computacional: Modelo RAM
o Computação nesse modelo:
o Processadorbusca instrução/dado da memória.
o Uma única instrução é executada de cada vez.
o Cada instrução é executada sequencialmente, sem operações concorrentes.
o Cada operação executada pelo processador, incluindo cálculos 
aritméticos, lógicos e acesso a memória, implica num custo de tempo:
o Função de complexidade de tempo.
o Cada operação e dado armazenado na memória, implica num custo de 
espaço:
o Função de complexidade de espaço.
Prof. Rodrigo Freitas Silva / UFES 21
Complexidade de Tempo e Espaço
o A complexidade de tempo não representa tempo diretamente, mas o 
número de vezes que determinada operação considerada relevante é 
executada.
o A complexidade de espaço representa a quantidade de memória (em 
uma unidade qualquer) que é necessária para armazenar as estruturas 
de dados associadas ao algoritmo.
o Usa-se a notação assintótica para representar essas complexidades:
o O (O grande);
o Ω (Ômega grande);
o Θ (Theta);
o o (o pequeno);
o ω (ômega pequeno).
Prof. Rodrigo Freitas Silva / UFES 22
Complexidade de Tempo e Espaço
o Atualmente, a quantidade extra de memória requerida por um 
algoritmo não é tão importante, ainda que exista uma diferença 
entre memória principal, secundária e cache
o Porém, o tempo continua sendo importante, pois, problemas cada 
vez mais complexos são tratados
o → abordaremos somente eficiência temporal
Prof. Rodrigo Freitas Silva / UFES 23
Análise de Algoritmos
o Em geral, o tempo de execução de um algoritmo cresce com o 
tamanho da entrada
o Assim é tradicional definir o tempo de execução de um algoritmo como 
uma função do tamanho de sua entrada
o Tamanho da entrada: depende do problema que está sendo estudado, a 
medida mais natural é o número de itens na entrada, exemplo o tamanho 
do vetor n para ordenação 
o Tempo de execução de um algoritmo em uma determinada entrada é o 
número de operações primitivas ou “etapas” executadas.
Prof. Rodrigo Freitas Silva / UFES 24
Medida do tempo de execução de um programa
o O projeto de algoritmos é fortemente influenciado pelo estudo de 
seus comportamentos
o Depois que um problema é analisado e decisões de projeto são 
finalizadas, é necessário estudar as várias opções de algoritmos a 
serem utilizados, considerando os aspectos de tempo de execução e 
espaço ocupado
Prof. Rodrigo Freitas Silva / UFES 25
Tipos de problemas na análise de algoritmos –
Análise de um algoritmo particular
o Qual é o custo de usar um dado algoritmo para resolver um 
problema específico?
o Características que devem ser investigadas:
1. Número de vezes que cada parte do algoritmo deve ser executada
2. Quantidade de memória necessária
o Não será estudado
Prof. Rodrigo Freitas Silva / UFES 26
Tipos de problemas na análise de algoritmos –
Análise de uma classe de algoritmos
o Qual é o algoritmo de menor custo possível para resolver um 
problema particular?
o Toda uma família de algoritmos é investigada
o Procura-se identificar um que seja o melhor possível
o Colocam-se limites para a complexidade computacional dos algoritmos 
pertencentes à classe
Prof. Rodrigo Freitas Silva / UFES 27
Custo de um algoritmo
o Determinando o menor custo possível para resolver problemas de 
uma dada classe, temos a medida da dificuldade inerente para 
resolver o problema
o Quando o custo de um algoritmo é igual ao menor custo possível, o 
algoritmo é ótimo para a medida de custo considerada
o Podem existir vários algoritmos para resolver o mesmo problema
o Se a mesma medida de custo é aplicada a diferentes 
algoritmos, então é possível compará-los e escolher o mais 
adequado
Prof. Rodrigo Freitas Silva / UFES 28
Medida do custo pela execução do programa em
uma plataforma real
o Tais medidas são bastante inadequadas e os resultados jamais devem ser 
generalizados:
o Os resultados são dependentes do compilador que pode favorecer algumas 
construções em detrimento de outras
o Os resultados dependem do hardware
o Apesar disso, há argumentos a favor de se obterem medidas reais de tempo
o Por exemplo, quando há vários algoritmos distintos para resolver um mesmo tipo 
de problema, todos com um custo de execução dentro de uma mesma ordem de 
grandeza
o Assim, são considerados tanto os custos reais das operações como os custos não 
aparentes, tais como alocação de memória, indexação, carga, dentre outros
Prof. Rodrigo Freitas Silva / UFES 29
Medida do custo por meio de métodos analíticos
o O objetivo é determinar uma expressão matemática que traduza o 
comportamento de tempo de um algoritmo
o O método analítico visa aferir o tempo de execução de forma independente 
do computador utilizado, da linguagem e compiladores empregados e das 
condições locais de processamento
o Ao invés da execução propriamente dita do algoritmo, é 
possível obter uma ordem de grandeza do tempo de 
execução através de métodos analíticos
Prof. Rodrigo Freitas Silva / UFES 30
Medida do custo por meio de Métodos analíticos
o Deve ser especificado o conjunto de operações e seus custos de 
execuções
o É mais USUAL ignorar o custo de algumas das operações e considerar 
apenas as operações mais significativas (ou a operação dominante)
o A operação dominante é a de maior frequência de execução no algoritmo
o Por exemplo, algoritmos de ordenação:
o consideramos o número de comparações entre os elementos do conjunto 
a ser ordenado e ignoramos as operações aritméticas, de atribuição e 
manipulações de índices, caso existam
Prof. Rodrigo Freitas Silva / UFES 31
Medida do custo por meio de Métodos analíticos
o O custo de execução de um algoritmo pode ser 
interpretado então como sendo o número de 
execuções da operação dominante
Prof. Rodrigo Freitas Silva / UFES 32
Função de complexidade
o Para medir o custo de execução de um algoritmo é comum definir uma função de 
custo ou função de complexidade f
o f(n) é a medida do tempo necessário para executar um algoritmo para um 
problema de tamanho n
o Função de complexidade de espaço: f(n) mede a memória necessária para 
executar um algoritmo para um problema de tamanho n
o Função de complexidade de tempo: f(n) mede o tempo necessário para 
executar um algoritmo para um problema de tamanho n
o OBS: utilizaremos f para denotar uma função de complexidade de tempo daqui para a 
frente
o Lembrando: na realidade, a complexidade de tempo não representa tempo diretamente, 
mas o número de vezes que determinada operação considerada relevante é executada
Prof. Rodrigo Freitas Silva / UFES 33
Exemplo: Algoritmo para encontrar o menor elemento
o Considere o algoritmo para encontrar o menor elemento de um vetor de 
inteiros A[1..n]; n ≥ 1 
Function Min (var A: Vetor): integer;
var i, Temp: integer;
begin
Temp := A[1];
for i:=2 to n do
if Temp > A[i] then
Temp := A[i];
Min := Temp;
end;
o Seja f uma função de complexidade tal que f(n) é o número de comparações 
entre os elementos de A. Se A contiver n elementos, qual é o número de 
comparações executadas pelo algoritmo???Prof. Rodrigo Freitas Silva / UFES 34
Exemplo: Algoritmo para encontrar o menor elemento
o Considere o algoritmo para encontrar o menor elemento de um vetor de 
inteiros A[1..n]; n ≥ 1 
Function Min (var A: Vetor): integer;
var i, Temp: integer;
begin
Temp := A[1];
for i:=2 to n do
if Temp > A[i] then
Temp := A[i];
Min := Temp;
end;
o Se A contiver n elementos, temos:
o f(n) = n – 1 para n ≥ 1
o Vamos provar que o algoritmo apresentado no programa acima é ótimo
Prof. Rodrigo Freitas Silva / UFES 35
Exemplo: Algoritmo para encontrar o menor elemento
o Teorema: Qualquer algoritmo para encontrar o menor elemento de 
um conjunto com n elementos, n ≥ 1, faz pelo menos n - 1 
comparações
o Prova: Cada um dos n - 1 elementos tem de ser mostrado, por meio 
de comparações, que é menor do que algum outro elemento
o Logo n - 1 comparações são necessárias
O teorema acima nos diz que, SE o número de comparaçõesfor utilizado 
como medida de custo, então a função Min do programa anterior é ótima
Prof. Rodrigo Freitas Silva / UFES 36
POSCOMP 2003
o Qual é o número mínimo de comparações necessárias para 
encontrar o menor elemento de um conjunto qualquer não ordenado 
de n elementos?
a) 1
b) n – 1
c) n
d) n + 1
e) n log n
Prof. Rodrigo Freitas Silva / UFES 37
POSCOMP 2003
o Qual é o número mínimo de comparações necessárias para 
encontrar o menor elemento de um conjunto qualquer não ordenado 
de n elementos?
a) 1
b) n – 1
c) n
d) n + 1
e) n log n
Prof. Rodrigo Freitas Silva / UFES 38
o Quanto vale k no fim da execução do seguinte trecho de código?
a) n – 1
b) N
c) (n2 - n)/2
d) n(n + 1)/2
e) n3
POSCOMP 2004
k = 0
for (i = 1; i <= n; i++)
for (j = i; j <= n; j++ )
k = k + 1
Prof. Rodrigo Freitas Silva / UFES 39
o Quanto vale k no fim da execução do seguinte trecho de código?
a) n – 1
b) N
c) (n2 - n)/2
d) n(n + 1)/2
e) n3
o Equivale a verificar o número de operações de atribuição (k = k + 1) são executadas, 
sendo que cada operação desta possui custo 1. Logo:
σ𝑖=1
𝑛 σ𝑗=𝑖
𝑛 1 = σ𝑖=1
𝑛 𝑖 = 1 + 2 + ... + (n - 2) + (n – 1) + n = 
𝑛(𝑛+1)
2
POSCOMP 2004
k = 0
for (i = 1; i <= n; i++)
for (j = i; j <= n; j++ )
k = k + 1
Prof. Rodrigo Freitas Silva / UFES 40
Tamanho da entrada de dados
o A medida do custo de execução de um algoritmo depende 
principalmente do tamanho da entrada dos dados
o É comum considerar o tempo de execução de um programa como uma 
função do tamanho da entrada
o Para alguns algoritmos, o custo de execução é uma função da entrada 
particular dos dados, não apenas do tamanho da entrada
o No caso da função Minx do exemplo, o custo é uniforme sobre todos os 
problemas de tamanho n
o Já para um algoritmo de ordenação isso não ocorre: se os dados de entrada já 
estiverem quase ordenados, então o algoritmo pode ter que trabalhar menos
Prof. Rodrigo Freitas Silva / UFES 41
Melhor caso, pior caso e caso médio
o Pior caso:
o Maior tempo de execução sobre todas as entradas de tamanho n
o Se f é uma função de complexidade baseada na análise de pior caso, o custo de 
aplicar o algoritmo nunca é maior do que f(n)
o O termo complexidade é comumente empregado com o significado de pior caso
Prof. Rodrigo Freitas Silva / UFES 42
Melhor caso, pior caso e caso médio
o Melhor caso:
o Menor tempo de execução sobre todas as entradas de tamanho n
Prof. Rodrigo Freitas Silva / UFES 43
Melhor caso, pior caso e caso médio
o Caso médio (ou caso esperado):
o Média dos tempos de execução de todas as entradas de tamanho n
Seja A um algoritmo, {E1, ..., En} o conjunto de todas as entradas possíveis 
de A. Denota-se ti o número de execuções da operação analisada no 
algoritmo (comumente a operação dominante) quando a entrada for Ei
Define-se:
Complexidade do caso médio = σ𝑖=1
𝑛 𝑝𝑖𝑡𝑖
onde pi é probabilidade de ocorrência da entrada Ei
Prof. Rodrigo Freitas Silva / UFES 44
Melhor caso, pior caso e caso médio
o Em geral, nos concentramos apenas nas descobertas do 
tempo de execução do pior caso
(o tempo de execução mais longo para qualquer entrada de tamanho n)
Pois:
o O tempo de execução do pior caso de um algoritmo é um limite superior sobre 
o tempo de execução para qualquer entrada. Conhecê-lo nos dá uma garantia 
de que o algoritmo nunca irá demorar mais tempo
o Muitas vezes o caso médio é quase tão ruim quando o pior caso. Por exemplo 
o algoritmo de ordenação por inserção, apesar do tempo de execução do caso 
médio ser menor, ainda assim é uma função quadrática do tamanho da 
entrada, exatamente como o tempo de execução do pior caso
Prof. Rodrigo Freitas Silva / UFES 45
Caso médio
o Na análise do caso médio, supõe-se uma distribuição de 
probabilidades sobre o conjunto de entradas de tamanho n e o 
custo médio é obtido com base nessa distribuição
o Em diversos caso essa distribuição é desconhecida
o A análise do caso médio é geralmente muito mais difícil de obter do que 
as análises do melhor e do pior caso
o O cálculo de σ𝑝𝑖𝑡𝑖 é frequentemente de tratamento matemático complexo
o É comum supor uma distribuição de probabilidades em que todas as 
entradas possíveis são igualmente prováveis
o Na prática isso nem sempre é verdade
Prof. Rodrigo Freitas Silva / UFES 46
Exemplo Caso Médio: Registros de um Arquivo
o Problema 1: Considere o problema de acessar um arquivo com n
registros. Cada registro contém uma chave única que é utilizada para
recuperar registros do arquivo. O algoritmo de pesquisa mais
simples é o que faz a pesquisa sequencial. Portanto, dada uma chave
qualquer, pede-se que localize o registro que contenha esta chave.
Leve em conta que toda pesquisa recupera um registro e que todos
os registros possuem a mesma probabilidade de serem acessados,
sendo pi a probabilidade do i-ésimo registro ser procurado. Qual é a
expressão da complexidade desse problema no melhor caso, no pior
caso e no caso médio?
Prof. Rodrigo Freitas Silva / UFES 47
Exemplo Caso Médio: Registros de um Arquivo
o Problema 1: Considere o problema de acessar um arquivo com n registros. Cada registro contém uma chave
única que é utilizada para recuperar registros do arquivo. O algoritmo de pesquisa mais simples é o que faz a
pesquisa sequencial. Portanto, dada uma chave qualquer, pede-se que localize o registro que contenha esta chave.
Leve em conta que toda pesquisa recupera um registro e que todos os registros possuem a mesma probabilidade de
serem acessados, sendo pi a probabilidade do i-ésimo registro ser procurado. Qual é a expressão da complexidade
desse problema no melhor caso, pior caso e caso médio?
o Seja f uma função de complexidade tal que f(n) é o número de registros consultados no arquivo
(nº de vezes que a chave de consulta é comparada com a chave de cada registro)
o Melhor caso: f(n) = 1 (registro procurado é o primeiro consultado)
o Pior caso: f(n) = n (registro procurado é o último consultado ou não está 
presente no arquivo)
o Caso médio: f(n) = 
𝑛+1
2
(Como calcular? Utilize: complexidade do caso médio = σ𝑖=1
𝑛 𝑝𝑖𝑡𝑖 )
Prof. Rodrigo Freitas Silva / UFES 48
o Complexidade do caso médio: 
o Toda pesquisa recupera um registro
o Seja pi for a probabilidade do i-ésimo registro ser procurado, e que para recuperar o i-
ésimo registro são necessárias i comparações, então
f(n) = 1 x p1 +2 x p2 +3 x p3 + ... +n x pn
o Para calcular f(n) basta conhecer a distribuição de probabilidades pi.
o Considerando que cada registro tenha a mesma probabilidade de ser acessado que todos 
os outros, então pi = 1/n; 1 ≤ i ≤ n. 
o Complexidade do caso médio = σ𝑖=1
𝑛 𝑝𝑖𝑡𝑖 = 
1
𝑛
(1+2+3+...+n) = 
1
𝑛
(n(n+1)
2
= 
n+1
2
o A análise do caso médio revela que uma pesquisa com sucesso examina 
aproximadamente metade dos registros
Exemplo Caso Médio : Registros de um Arquivo
Prof. Rodrigo Freitas Silva / UFES 49
POSCOMP 2002
o Considere o algoritmo da busca sequencial de um elemento em um 
conjunto com n elementos? A expressão que representa o tempo 
médio de execução desse algoritmo para uma busca bem sucedida é?
a) n2
b) n(n + 1)/2
c) log2n
d) (n + 1)/2
e) n log n
Prof. Rodrigo Freitas Silva / UFES 50
POSCOMP 2002
o Considere o algoritmo da busca sequencial de um elemento em um 
conjunto com n elementos? A expressão que representa o tempo 
médio de execução desse algoritmo para uma busca bem sucedida é?
a) n2
b) n(n + 1)/2
c) log2n
d) (n + 1)/2
e) n log n
Prof. Rodrigo Freitas Silva / UFES 51
POSCOMP 2006
o Dada uma lista linear de n+1 elementos ordenados e alocados 
sequencialmente, qual é o número médio (número esperado) de 
elementos que devem ser movidos para que se faça uma inserção na 
lista, considerando-se igualmente prováveis as n+1 posições de 
inserção?
a) n /2
b) (n + 2)/2
c) (n - 1)/2
d) n(n + 3 + 2/n)/2
e) (n + 1)/2
Prof. Rodrigo Freitas Silva / UFES 52
POSCOMP 2006o Dada uma lista linear de n+1 elementos ordenados e alocados 
sequencialmente, qual é o número médio (número esperado) de 
elementos que devem ser movidos para que se faça uma inserção na 
lista, considerando-se igualmente prováveis as n+1 posições de 
inserção?
a) n /2
b) (n + 2)/2
c) (n - 1)/2
d) n(n + 3 + 2/n)/2
e) (n + 1)/2
Prof. Rodrigo Freitas Silva / UFES 53
POSCOMP 2006
o Dada uma lista linear de n+1 elementos ordenados e alocados sequencialmente, qual é o número 
médio (número esperado) de elementos que devem ser movidos para que se faça uma inserção na lista, 
considerando-se igualmente prováveis as n+1 posições de inserção?
o Considerando n+1 entradas sendo Ei, 1 ≤ i ≤ n+1, e que:
o Se a inserção for na 1º posição, n+1 nº seriam movidos
o Se a inserção for na 2º posição, n nº seriam movidos
o Se a inserção for na 3º posição, n-1 nº seriam movidos
o ...
o Se a inserção for na penúltima posição, 1 nº seria movidos
o Se a inserção for na última posição, 0 nº seriam movidos
o Probabilidade pi =
1
𝑛+1
Complexidade do caso médio = σ𝑖=1
𝑛+1 𝑝𝑖𝑡𝑖 = 
1
𝑛+1
∗ (1+2+...+n+(n+1)) =
1
𝑛+1
* 
𝑛+1(𝑛+1+1)
2
= 
𝑛+2
2
Prof. Rodrigo Freitas Silva / UFES 54
Exemplo Caso Médio : Registros de um Arquivo
o Problema 2: Vamos considerar agora que NEM toda pesquisa
recupera um registro e que q é a probabilidade de sucesso no
resultado da busca. Continue supondo que cada registro possui a
mesma probabilidade pi de ser acessado que todos os outros. Qual é a
expressão de complexidade do caso médio desse problema?
Prof. Rodrigo Freitas Silva / UFES 55
Exemplo Caso Médio : Registros de um Arquivo
o Problema 2: Vamos considerar agora que NEM toda pesquisa recupera um registro e que q é a
probabilidade de sucesso no resultado da busca. Continue supondo que cada registro possui a mesma
probabilidade pi de ser acessado que todos os outros. Qual é a expressão de complexidade do caso
médio desse problema?
Para entradas em que a chave procurada se encontra na posição 1, posição 2, 
..., posição n
 Seja Ei, 1 ≤ i ≤ n, uma entrada em que a chave procurada ocupa a i-ésima
posição na lista
Entradas em que a chave não se encontra na lista
 Seja E0 a entrada que corresponda a busca sem sucesso
Prof. Rodrigo Freitas Silva / UFES 56
Exemplo Caso Médio : Registros de um Arquivo
o As probabilidades das entradas são:
o p(Ei) = q * 1/n = q/n
o Dado que cada registro possui a mesma probabilidade de ser acessado que 
todos os outros, ou seja, 1/n
o p(E0) = 1 - q
o Logo, a expressão da complexidade média é:
σ𝑖=0
𝑛 𝑝 𝐸𝑖 𝑡 𝐸𝑖 = (1 - q)n + σ𝑖=1
𝑛 𝑞
𝑛
𝑖 = n – qn + q
n+1
2
Prof. Rodrigo Freitas Silva / UFES 57
Exemplo Caso Médio : Registros de um Arquivo
o Sabendo que a expressão da complexidade média é:
σ𝑖=0
𝑛 𝑝 𝐸𝑖 𝑡 𝐸𝑖 = (1 - q)n + σ𝑖=1
𝑛 𝑞
𝑛
𝑖 = n – qn + q
n+1
2
Analisando os resultados: Em casos particulares, como:
o Se q = 1 (a chave está sempre na lista), a complexidade é 
n+1
2
o Se q = ½ , a função cresce para ≈ 3n/4
o Se q = 0, a complexidade média atinge o valor n
Prof. Rodrigo Freitas Silva / UFES 58
o Problema 3: Considere o algoritmo da busca sequencial de um
elemento em um vetor com n elementos. Considere que o elemento
procurado tenha probabilidade de
3
4
de estar na primeira metade do
vetor, ou seja, de estar em 1, ... ,
𝑛
2
, e que tenha probabilidade de
1
4
de estar na segunda metade do vetor, ou seja, em
𝑛
2
+1, ... ,𝑛 . Qual é
o número médio de comparações efetuadas nesse algoritmo para
uma busca bem sucedida?
Exemplo Caso Médio : Busca Sequencial
Prof. Rodrigo Freitas Silva / UFES 59
Posição 
Vetor
ti pi
1 1 6
4𝑛
2 2 6
4𝑛
... ... 6
4𝑛
𝑛
2
𝑛
2
6
4𝑛
𝑛
2
+1
𝑛
2
+1 2
4𝑛
𝑛
2
+2
𝑛
2
+2 2
4𝑛
... ... 2
4𝑛
n n 2
4𝑛
o Problema 3: Considere o algoritmo da busca sequencial de um elemento em um vetor com n elementos. Considere
que o elemento procurado tenha probabilidade de
3
4
de estar na primeira metade do vetor, ou seja, de estar em ቂ1,
Exemplo Caso Médio : Busca Sequencial
Prof. Rodrigo Freitas Silva / UFES 60
Probabilidade 
de ocorrência
3
4
1
4
൙
3
4
𝑛
2
=
6
4𝑛
൙
1
4
𝑛
2
=
2
4𝑛
Posição 
Vetor
ti pi
1 1 6
4𝑛
2 2 6
4𝑛
... ... 6
4𝑛
𝑛
2
𝑛
2
6
4𝑛
𝑛
2
+1
𝑛
2
+1 2
4𝑛
𝑛
2
+2
𝑛
2
+2 2
4𝑛
... ... 2
4𝑛
n n 2
4𝑛
o Problema 3: Considere o algoritmo da busca sequencial de um elemento em um vetor com n elementos. Considere
que o elemento procurado tenha probabilidade de
3
4
de estar na primeira metade do vetor, ou seja, de estar em
1, ... ,
𝑛
2
, e que tenha probabilidade de
1
4
de estar na segunda metade do vetor, ou seja, em
𝑛
2
+1, ... ,𝑛 . Qual é o
número médio de comparações efetuadas nesse algoritmo para uma busca bem sucedida?
Exemplo Caso Médio : Busca Sequencial
Prof. Rodrigo Freitas Silva / UFES 61
𝑓 𝑛 =෍
𝑖=1
𝑛
𝑝𝑖𝑡𝑖 =෍
𝑖=1
𝑛
2
6
4𝑛
𝑖 + ෍
𝑖=
𝑛
2
+1
𝑛
2
4𝑛
𝑖 =
6
4𝑛
෍
𝑖=1
𝑛
2
𝑖 +
2
4𝑛
෍
𝑖=
𝑛
2
+1
𝑛
𝑖
o Sabe-se que:
Soma dos termos de uma PA = 
𝑛(𝑎1+𝑎𝑛)
2
Posição 
Vetor
ti pi
1 1 6
4𝑛
2 2 6
4𝑛
... ... 6
4𝑛
𝑛
2
𝑛
2
6
4𝑛
𝑛
2
+1
𝑛
2
+1 2
4𝑛
𝑛
2
+2
𝑛
2
+2 2
4𝑛
... ... 2
4𝑛
n n 2
4𝑛
o Problema 3: Considere o algoritmo da busca sequencial de um elemento em um vetor com n elementos. Considere
que o elemento procurado tenha probabilidade de
3
4
de estar na primeira metade do vetor, ou seja, de estar em
1, ... ,
𝑛
2
, e que tenha probabilidade de
1
4
de estar na segunda metade do vetor, ou seja, em
𝑛
2
+1, ... ,𝑛 . Qual é o
número médio de comparações efetuadas nesse algoritmo para uma busca bem sucedida?
Exemplo Caso Médio : Busca Sequencial
Prof. Rodrigo Freitas Silva / UFES 62
𝑓 𝑛 =෍
𝑖=1
𝑛
𝑝𝑖𝑡𝑖 =෍
𝑖=1
𝑛
2
6
4𝑛
𝑖 + ෍
𝑖=
𝑛
2
+1
𝑛
2
4𝑛
𝑖 =
6
4𝑛
෍
𝑖=1
𝑛
2
𝑖 +
2
4𝑛
෍
𝑖=
𝑛
2
+1
𝑛
𝑖
𝑓 𝑛 =
3
4
𝑛
2
∗
𝑛
2
1 +
𝑛
2
2
+
1
4
𝑛
2
∗
𝑛
2
𝑛
2
+ 1 + 𝑛
2
𝑓 𝑛 =
3+
3𝑛
2
8
+
𝑛
2
+1+𝑛
8
=
3𝑛+4
8
o Considere o problema de encontrar o maior e o menor elemento de 
um vetor de inteiros A[1..n], n ≥ 1.
o Um algoritmo simples pode ser derivado do algoritmo apresentado 
no programa para achar o maior elemento.
procedure MaxMin1 (var A: Vetor; var Max, Min: 
integer);
var i: integer;
begin
Max := A[1]; Min := A[1];
for i := 2 to n do
begin
if A[i] > Max then Max := A[i]; 
if A[i] < Min then Min := A[i]; 
end;
end.
Exemplo: Maior e menor elementos (1)
Prof. Rodrigo Freitas Silva / UFES 63
procedure MaxMin1 (var A: Vetor; var Max, Min: integer);
var i: integer;
begin
Max := A[1]; Min := A[1];
for i := 2 to n do
begin
if A[i] > Max then Max := A[i]; 
if A[i] < Min then Min := A[i]; 
end;
end.
o Seja f(n)o número de comparações entre os elementos de A
o Logo: f(n) = 2(n - 1);
o Para n > 0, para o melhor caso, pior caso e caso médio
Exemplo: Maior e menor elementos (1)
Prof. Rodrigo Freitas Silva / UFES 64
Exemplo: Maior e menor elementos (2)
o MaxMin1 pode ser facilmente melhorado:
o A comparação A[i] < Min só é necessária quando o resultado da 
comparação A[i] > Max for falso.
procedure MaxMin2 (var A: Vetor; var Max, Min: 
integer);
var i: integer;
begin
Max := A[1]; Min := A[1];
for i := 2 to n do
if A[i] > Max then Max := A[i]
else if A[i] < Min then Min := A[i];
end;
end.
Prof. Rodrigo Freitas Silva / UFES 65
Exemplo: Maior e menor elementos (2)
o Para essa implementação tem-se:
o Melhor caso: f(n) = n - 1 (quando os elementos estão em ordem crescente);
o Pior caso: f(n) = 2(n - 1) (quando os elementos estão em ordem decrescente);
o Caso médio: f(n) = 
3𝑛−3
2
Prof. Rodrigo Freitas Silva / UFES 66
procedure MaxMin2 (var A: Vetor; var Max, Min: integer);
var i: integer;
begin
Max := A[1]; Min := A[1];
for i := 2 to n do
if A[i] > Max then Max := A[i]
else if A[i] < Min then Min := A[i];
end;
end.
Exemplo: Maior e menor elementos (2)
oCaso médio:
o Supondo que: A[i] é maior do que Max a metade das vezes
o f(n) = σ𝑖=1
(𝑛−1)
1 + σ𝑖=1
(𝑛−1)/2
1 = (n-1)+ 
(n−1)
2
= 
3n−3
2
Prof. Rodrigo Freitas Silva / UFES 67
procedure MaxMin2 (var A: Vetor; var Max, Min: integer);
var i: integer;
begin
Max := A[1]; Min := A[1];
for i := 2 to n do
if A[i] > Max then Max := A[i]
else if A[i] < Min then Min := A[i];
end;
end.
Exemplo: Maior e menor elementos (3)
o Considerando o número de comparações realizadas, existe a 
possibilidade de obter um algoritmo mais eficiente:
1. Compare os elementos de A aos pares, separando-os em dois subconjuntos (maiores em um e 
menores em outro), a um custo de 
┌
n/2
┐
comparações
2. O máximo é obtido do subconjunto que contém os maiores elementos, a um custo de ┌n/2┐ - 1 
comparações
3. O mínimo é obtido do subconjunto que contém os menores elementos, a um custo de ┌n/2┐ - 1 
comparações
Prof. Rodrigo Freitas Silva / UFES 68
Exemplo: Maior e menor elementos (3)
procedure MaxMin3(var A: Vetor; var Max, Min: integer);
var i, FimDoAnel: integer;
begin
if (n mod 2) > 0 then
begin
A[n+1] := A[n];
FimDoAnel := n;
end
else FimDoAnel := n-1;
if A[1] > A[2] then
Max := A[1]; Min := A[2];
else
Max := A[2]; Min := A[1];
i:= 3;
while i <= FimDoAnel do
begin
if A[i] > A[i+1] then
begin
if A[i] > Max then Max := A[i];
if A[i+1] < Min then Min := A[i+1];
end
else
begin
if A[i] < Min then Min := A[i];
if A[i+1] > Max then Max := A[i+1];
end;
i:= i + 2;
end;
end; Prof. Rodrigo Freitas Silva / UFES 69
{Garante uma qte par de elementos no 
vetor para evitar caso de exceção}
{Determina maior e menor elementos 
iniciais}
o Lembrando: f(n)é o número de comparações entre os elementos de A
o Os elementos de A são comparados dois a dois e
o Os elementos maiores são comparados com Max
o Os elementos menores são comparados com Min
o Quando n é ímpar, o elemento que está na posição A[n] é duplicado na 
posição A[n+1] para evitar um tratamento de exceção
Exemplo: Maior e menor elementos (3)
Prof. Rodrigo Freitas Silva / UFES 70
o Lembrando: f(n)é o número de comparações entre os elementos de A
o Análise da complexidade:
o Para o melhor caso, pior caso e caso médio tem-se:
f(n) = 1 + 
𝑛−2
2
+ 
𝑛−2
2
+ 
𝑛−2
2
= 
3𝑛
2
- 2 
 OBS:
 1 é de A[1] > A[2] 

𝑛−2
2
é de A[i] > A[i+1] 

𝑛−2
2
é de A[i] > Max 

𝑛−2
2
é de A[i+1] < Min 
Exemplo: Maior e menor elementos (3)
Prof. Rodrigo Freitas Silva / UFES 71
Comparação entre os algoritmos
MaxMin1, MaxMin2 e MaxMin3
o A tabela abaixo apresenta uma comparação entre os algoritmos dos programas MaxMin1, 
MaxMin2 e MaxMin3, considerando o número de comparações como medida de 
complexidade
o Os algoritmos MaxMin2 e MaxMin3 são superiores ao algoritmo MaxMin1 de forma geral
o O algoritmo MaxMin3 é superior ao algoritmo MaxMin2 com relação ao pior caso e bastante 
próximo quanto ao caso médio
Prof. Rodrigo Freitas Silva / UFES 72
Comportamento Assintótico de funções
o O parâmetro n fornece uma medida da dificuldade para se resolver o 
problema
o Para valores suficientemente pequenos de n, qualquer algoritmo custa 
pouco para ser executado, mesmo os ineficientes
o A escolha do algoritmo não é um problema crítico para problemas de 
tamanho pequeno
o Logo, a análise de algoritmos é realizada para valores grandes de n
Prof. Rodrigo Freitas Silva / UFES 73
Comportamento Assintótico de funções
o Estuda-se o comportamento assintótico das funções de custo
o (comportamento de suas funções de custo para valores grandes de n)
o Grandes o suficiente para tornar relevante apenas a ordem de 
crescimento do tempo de execução
o O comportamento assintótico de f(n) representa o limite do 
comportamento do custo quando n cresce
Prof. Rodrigo Freitas Silva / UFES 74
Dominação assintótica
o A análise de um algoritmo geralmente conta com apenas algumas 
operações elementares
o A medida de custo ou medida de complexidade relata o crescimento 
assintótico da operação considerada
o Definição: Uma função f(n) domina assintoticamente outra 
função g(n) se existem duas constantes positivas c e n0 tais que, para 
n ≥ n0, temos c |f(n)| ≥ |g(n)| 
Prof. Rodrigo Freitas Silva / UFES 75
Dominação assintótica
o Exemplo:
o Sejam f(n) = n2 e g(n) = (n+1)2
o As funções f(n) e g(n) dominam assintoticamente uma a outra, já que:
4|n2| ≥ |(n+1)2| para n ≥ 1 
|(n+1)2 | ≥ |n2| para n ≥ 0
Prof. Rodrigo Freitas Silva / UFES 76
Como medir o custo de execução de um algoritmo?
o Função de Custo (ou Função de Complexidade)
f(n) = medida de custo necessário para executar um algoritmo para um problema de 
tamanho n
o Se f(n) é uma medida da quantidade de tempo necessário para executar um algoritmo para um 
problema de tamanho n, então f é chamada função de complexidade de tempo de algoritmo
o Se f(n) é uma medida da quantidade de memória necessária para executar um algoritmo para um 
problema de tamanho n, então f é chamada função de complexidade de espaço de algoritmo
o Observação: 
o É importante lembrar que a complexidade de tempo na realidade não representa tempo 
diretamente, mas o número de vezes que determinada operação considerada relevante é 
executada
Prof. Rodrigo Freitas Silva / UFES 77
Custo Assintótico de Funções
o Relembrando:
o É interessante comparar algoritmos para valores grandes de n
o O custo assintótico de uma função f(n) representa o limite do 
comportamento de custo quando n cresce
o Em geral, o custo aumenta com o tamanho n do problema
Observação:
o Para valores pequenos de n, mesmo um algoritmo ineficiente não custa 
muito para ser executado.
Prof. Rodrigo Freitas Silva / UFES 78
Taxa de crescimento das funções
o É a taxa de crescimento (ordem de crescimento) do tempo de 
execução que realmente nos interessa 
o Por exemplo, um algoritmo com tempo de execução do pior caso com a 
seguinte fórmula an2 + bn + c
o Consideraremos apenas o termo inicial dessa fórmula (ex. an2)
o Os termos de mais baixa ordem são relativamente insignificantes para 
grandes valores de n
o O coeficiente constante do termo inicial também é ignorado, já que fatores 
constantes são menos significativos que a taxa de crescimento na 
determinação da eficiência computacional para grandes entradas
Prof. Rodrigo Freitas Silva / UFES 79
Taxa de crescimento das funções: exercícios
o O algoritmo de ordenação por inserção, por exemplo, tem um tempo de 
execução do pior caso igual a Θ(n2) (lido como “theta de n ao quadrado”)
o A notação Θ será estudada mais adiante
o Exercícios:
1. Expresse a função n3/1000 – 100n2 + 3 em termos da notação Θ
2. Expresse a função 
1
2
n2 – 3n em termos da notação Θ
Quais são as respostas??????
Lembrando: Constantes aditivas e multiplicativas são desprezadas
Prof. Rodrigo Freitas Silva / UFES 80
Taxa de crescimento das funções: exercícios
o Expresse a função n3/1000 – 100n2 + 3 em termos da notação Θ
Resposta: Θ(n3)
o Expresse a função 
1
2
n2 – 3n em termos da notação Θ
Resposta: Θ(n2)
Prof. Rodrigo Freitas Silva / UFES 81
Notação Assintótica de Funções
o Existem três notações principais na análise assintótica de funções:
o Notação Θ (theta)
o Notação O (“O” grande)
o Notação Ω (ômega)
Prof. Rodrigo Freitas Silva / UFES 82
Notação Θ
o A notação Θ limita a função por fatores constantes
o Escreve-se f(n) = Θ(g(n)), se existirem constantes positivas c1, c2 e n0 tais 
que para n ≥ n0, o valor de f(n) está sempre entre c1g(n) e c2g(n) inclusive
o Pode-se dizer que g(n) é um limite assintótico firme (ou restrito) para f(n)
Observe que a notação define um conjunto de funções:
Prof. Rodrigo Freitas Silva / UFES 83
Notação Θ
o Θ(g(n)) é um conjunto
o Poderíamos escrever “f(n)  Θ(g(n))” indicando que f(n) é um membro 
de (ou pertence) a Θ(g(n))
o Em vez disso, escrevemos “f(n) = Θ(g(n))”
o A definição Θ(g(n)) exige que todo membro f(n) deva ser assintoticamente
não negativoo Consequentemente a própria função g(n) deve ser assintoticamente não negativo, 
ou então o conjunto Θ(g(n)) é vazio
o Logo, vamos supor que toda função utilizada dentro das notações assintóticas 
(Θ, Ω, O) sejam assintoticamente não negativas
Prof. Rodrigo Freitas Silva / UFES 84
Notação Θ
Prof. Rodrigo Freitas Silva / UFES 85
Notação Θ: Exemplo 1
o Lembra-se: Que a noção informal da notação Θ consistia em descartar os 
termos de mais baixa ordem e ignorar o coeficiente inicial do termo de mais 
alta ordem?
o Vamos justificar isso usando a definição formal
o Mostre que 
1
2
n2 – 3n = Θ (n2).
FAÇAM !!!!
Prof. Rodrigo Freitas Silva / UFES 86
Notação Θ: Exemplo 1
Prof. Rodrigo Freitas Silva / UFES 87
o Mostrar que: 
1
2
n2 – 3n = Θ (n2)
Para provar esta afirmação, devemos achar as constantes c1 > 0, c2 > 0, n > 0, 
tais que:
c1n
2 ≤ 
1
2
n2 – 3n ≤ c2n
2 para todo n ≥ no
Se dividirmos a expressão acima por n2 temos:
c1 ≤ 
1
2
-
3
𝑛
≤ c2
Notação Θ: Exemplo 1
o A inequação mais a direita será sempre válida para qualquer valor de n ≥1 ao 
escolhermos c2 = 
1
2
o A inequação mais a esquerda será sempre válida para qualquer valor de n≥7 ao 
escolhermos c1 = 
1
14
Assim, ao escolhermos c1 = 
1
14
, c2 = 
1
2
e n0 = 7, podemos verificar que que:
1
2
n2 – 3n = Θ(n2)
c1 ≤ 
1
2
-
3
𝑛
≤ c2
Prof. Rodrigo Freitas Silva / UFES 88
Notação Θ: Exemplo 1
o Note que existem outras escolhas para as constantes c1 e c2, mas o fato 
importante é que a escolha existe
o Note também que a escolha destas constantes depende da função 
1
2
n2 – 3n 
o Uma função diferente pertencente a Θ(n2) irá provavelmente requerer outras 
constantes
Prof. Rodrigo Freitas Silva / UFES 89
Notação Θ: Exemplo 2
 Usando a definição formal de Θ prove que 6n3 ≠ Θ(n2).
Prof. Rodrigo Freitas Silva / UFES 90
Notação Θ: Exemplo 2
 Usando a definição formal de Θ prove que 6n3 ≠ Θ(n2).
Resposta !!!!
c1n
2 ≤ 6n3 ≤ c2n
2

c1n
2
𝑛2
≤ 
6n3
𝑛2
≤ 
c2n
2
𝑛2
 c1 ≤ 6n ≤ c2
 n ≤ c2/6 ????
Não é válido para um valor de n arbitrariamente grande, pois c2 é constante
Prof. Rodrigo Freitas Silva / UFES 91
Notação Θ
Em geral, para qualquer polinômio p(n) = σ𝑖=0
𝑑 𝑎𝑖𝑛𝑖 , onde ai são 
constantes e ai > 0, tem-se:
p(n) = Θ(nd)
Como qualquer constante é um polinômio de grau 0, podemos 
expressar qualquer função constante Θ(n0) ou Θ(1)
Prof. Rodrigo Freitas Silva / UFES 92
Notação O
o A notação Θ limita assintoticamente uma função acima e abaixo
o Quando temos apenas um limite assintótico superior, usamos a notação O
o A notação O define então um limite superior para a função, por um 
fator constante
o Escreve-se f(n) = O(g(n)), se existirem constantes positivas c e n0
tais que para n ≥ n0, o valor de f(n) é menor ou igual a cg(n)
o Pode-se dizer que g(n) é um limite assintótico superior para f(n)
Observe que a notação O define um conjunto de funções:
Prof. Rodrigo Freitas Silva / UFES 93
Notação O
Prof. Rodrigo Freitas Silva / UFES 94
Notação O
o Observe que f(n) = Θ(g(n)) implica f(n) = O(g(n))
o Pois a notação Θ é mais forte que a notação O
o Em termos de teoria dos conjuntos, tem-se:
o Θ(g(n))  O(g(n))
o Logo, qualquer função quadrática (an2 + bn + c com a > 0) está em 
Θ(n2), também está em O(n2)
o Surpreendente é o fato que qualquer função linear (an + b) 
está em O(n2)
o Facilmente verificado fazendo-se c = a + |b| e no = 1 pois:
0 ≤ f(n) ≤ cg(n)
 0 ≤ an + b ≤ (a + |b|)n2
Prof. Rodrigo Freitas Silva / UFES 95
Notação O
o Você acha estranho escrever, por exemplo, n = O(n2) ??
o Saiba que a notação O é as vezes usada de modo informal para descrever 
limites assintoticamente restritos (definido pela notação Θ)
Neste curso f(n) = O(g(n)) significa simplesmente uma afirmação que 
algum múltiplo constante de g(n) é um limite assintótico superior 
sobre f(n), sem qualquer menção sobre o quanto um limite superior é 
restrito
Prof. Rodrigo Freitas Silva / UFES 96
Notação O
o Lembra-se do algoritmo de ordenação por inserção?
o O limite O(n2) no tempo de execução do pior caso também se aplica a seu 
tempo de execução sobre toda entrada
o Porém, o limite Θ(n2) no tempo de execução do pior caso não implica 
Θ(n2) no tempo de execução em toda entrada
o Por exemplo, quando a entrada já está ordenada, o tempo de 
execução é Θ(n)
Prof. Rodrigo Freitas Silva / UFES 97
Notação O
Consequentemente:
Quando a notação O é usada para expressar o tempo de execução de um 
algoritmo no pior caso, está se definindo também o limite (superior) do 
tempo de execução desse algoritmo para todas as entradas
Prof. Rodrigo Freitas Silva / UFES 98
Notação O
o Tecnicamente é um abuso dizer que o tempo de execução do 
algoritmo de ordenação por inserção é O(n2)
(i.e., sem especificar se é para o pior caso, melhor caso, ou caso médio)
o O tempo de execução desse algoritmo depende de como os dados de 
entrada estão arranjados
o Se os dados de entrada já estiverem ordenados, este algoritmo tem um 
tempo de execução de O(n), ou seja, o tempo de execução do algoritmo de 
ordenação por inserção no melhor caso é O(n)
Prof. Rodrigo Freitas Silva / UFES 99
Notação O
O que se quer dizer quando se fala que “o tempo de execução” é O(n2)” 
é que no pior caso o tempo de execução é O(n2)
Independente de como os dados de entrada estão arranjados
Prof. Rodrigo Freitas Silva / UFES 100
Notação O: Exemplos
o Escreva as seguintes funções em notação O 
(Mostre o limite assintótico restrito)
1. f(n) = 100n
2. f(n) = 2n3 + 100n
3. Mostre que f(n) = n1.5 está em O(n2)
4. f(n) = (n+1)2.
5. 302
6. Seja f(n) = n e g(n) = n2. Mostre que g(n) não é O(n) !!!!
FAÇAM !!!!
Prof. Rodrigo Freitas Silva / UFES 101
Notação O: Resolução dos Exemplos
1. Seja f(n) = 100n
Logo f(n) é O(n), quando n0 = 1 e c = 100, já que
100n ≤ 100n para n ≥ 1
2. Seja f(n) = 2n3 + 100n
Logo f(n) é O(n3), quando n0 = 100 e c = 3, já que
2n3 + 100n ≤ 2n3 + n * n * n = 3n3 para n ≥ 100
3. Mostre que f(n) = n1.5 está em O(n2)
De fato n1.5 ≤ n0.5n1.5 = n2
Prof. Rodrigo Freitas Silva / UFES 102
Notação O: Resolução dos Exemplos
4. Seja f(n) = (n+1)2
Logo f(n) é O(n2), quando n0 = 1 e c = 4, já que
(n+1) 2 ≤ 4n2 para n ≥ 1
5. Seja f(n) = 302
Logo, f(n) = O(1), quando n0 = 1 e c = 302, já que
302 ≤ 302 * 1 para n ≥ 1
6. Seja f(n) = n e g(n) = n2. Mostre que g(n) não é O(n)
o Sabemos que f(n) é O(n2), pois para n ≥ 0, n ≤ n2
o Suponha que existam constantes c e n0 tais que para todo n ≥ n0, n
2 ≤ cn
Assim, c ≥ n para qualquer n ≥ n0. No entanto, não existe uma constante c que 
possa ser maior ou igual a n para todo n
Prof. Rodrigo Freitas Silva / UFES 103
Notação O : mais um exemplo
o Mostre através da definição que g(n) = 3n3 +2n2 +n é O(n3).
FAÇAM !!!!!
Prof. Rodrigo Freitas Silva / UFES 104
Notação O : mais um exemplo
o Mostre através da definição que g(n) = 3n3 +2n2 +n é O(n3)
o Basta mostrar que 3n3 +2n2 +n ≤ 6n3, para n ≥ 0, pois:
3n3 +2n2 +n ≤ 3n3 +2n3 +n3 ≤ 6n3
o A função g(n) = 3n3 +2n2 +n é também O(n4), entretanto esta afirmação 
é mais fraca do que dizer que g(n) é O(n3)
Prof. Rodrigo Freitas Silva / UFES 105
Notação O 
o Podemos definir o seguinte algoritmo para calcular a ordem de 
complexidade de algoritmos não recursivos:
1. Escolher o parâmetro que indica o tamanho da entrada
2. Identificar a operação básica (comparação, atribuição)
3. Estabeleça uma soma que indique quantas vezes sua operação básica foi 
executada (pior caso)
4. Utilize regras para manipulação de soma e formulas definindo uma 
função de complexidade
5. Encontre a ordem de complexidade
Prof. Rodrigo Freitas Silva / UFES 106
o Exercícios:
a) Baseando-se no algoritmo mostrado, determine a ordem de complexidade do 
algoritmo abaixo:
b) Podemos dizer que o algoritmo abaixo é O(n2)? Justifique.
MaxMin(vetor v)
max=v[1]; min=v[1]; i = 2;
whilei ≤ n faca
se v[n]> max entao max=v[n]; fimse
se v[n]< min entao min=v[n]; fimse
i=i+1;
fimwhile;
fim.
Notação O 
Prof. Rodrigo Freitas Silva / UFES 107
Notação O 
MaxMin(vetor v)
max=v[1]; min=v[1]; i = 2;
while i ≤ n faca
se v[n]> max entao max=v[n]; fimse
se v[n]< min entao min=v[n]; fimse
i= i+1;
fimwhile;
fim.
Respostas:
A)
o A escolha do parâmetro é n, que indica a quantidade de elementos do vetor
o A operação básica (dominante) é a comparação
• (neste exemplo, todas as comparações são contabilizadas)
o A complexidade é dada por 3(n-1)
o O algoritmo é da ordem de complexidade O(n)
B)
o Como n é O(n2), podemos dizer que o algoritmo é O(n2), entretanto estamos interessados sempre no limite 
mínimo superior, logo é melhor dizer que o algoritmo é O(n)
Prof. Rodrigo Freitas Silva / UFES 108
Notação O 
* Por que muitas vezes damos atenção apenas ao pior caso dos 
algoritmos??? Explique o porque !!!!
Resposta: Porque normalmente desejamos saber qual o limite máximo 
gasto para executar o determinado algoritmo.
Prof. Rodrigo Freitas Silva / UFES 109
Notação O: mais exemplos
1) f (n) = n2 – 1  f(n) = O(n2)
2) f (n) = n2 – 1  f(n) = O(n3)
3) f (n) = 403  f(n) = O(1)
4) f (n) = 5 + 2log n + 3log2n  f(n) = O(log2n )
5) f (n) = 5 + 2log n + 3log2n  f(n) = O(n )
6) f (n) = 3n + 5log n + 2  f(n) = O(n )
7) f (n) = 2 * 2n + 5n10  f(n) = O(2n )
Prof. Rodrigo Freitas Silva / UFES 110
Notação O: Propriedades
o f(n) = O(f(n))
o c * O(f(n)) = O(f(n)) sendo c = constante
o O(f(n))+O(f(n)) = O(f(n))
o O(O(f(n)) = O(f(n))
o O(f(n))+O(g(n)) = O(max(f(n); g(n)))
o O(f(n))O(g(n)) = O(f(n)g(n))
o f(n)O(g(n)) = O(f(n)g(n))
Prof. Rodrigo Freitas Silva / UFES 111
Operações com a notação O
o Regra da soma O(f(n)) + O(g(n))
o Suponha três trechos cujos tempos de execução são O(n), O(n2) e O(n lg n)
o O tempo de execução dos dois primeiros trechos é O(max(n; n2)), que é 
O(n2)
o O tempo de execução de todos os três trechos é então O(max(n2; n lg n)), 
que é O(n2)
1) Exercícios: O produto de [lg n+k +O(1/n)] por [n+O(√n)] é ?????
FAÇAM !!!!
Prof. Rodrigo Freitas Silva / UFES 112
Operações com a notação O: Exemplos
1) Resposta: O produto de [lg n+k +O(1/n)] por [n+O(√n)] =
= n lg n + lg n (O(√n)) + kn + k O(√n) + n O(1/n) + O(1/n) O(√n) =
= n lg n + O(lg n √n) + kn + O(√n) + O(n * 1/n) + O(1/n * √n) =
= n lg n + kn + O(max(lg n √n; √n; 1; 1/n * √n)) =
= n (lg n + k) + O(lg n √n) 
Atenção às propriedades utilizadas:
o c x O(f(n)) = O(f(n)) sendo c = constante
o O(f(n))+O(g(n)) = O(max(f(n); g(n)))
o O(f(n))O(g(n)) = O(f(n)g(n))
o f(n)O(g(n)) = O(f(n)g(n))
Prof. Rodrigo Freitas Silva / UFES 113
Notação Ω
o A notação Ω (ômega) define um limite inferior para a função, por 
um fator constante
o Escreve-se f(n) = Ω(g(n)), se existirem constantes positivas c e n0 tais que 
para n ≥ n0, o valor de f(n) é maior ou igual a cg(n)
o Pode-se dizer que g(n) é um limite assintótico inferior para f(n)
o Observe que a notação Ω define um conjunto de funções:
Prof. Rodrigo Freitas Silva / UFES 114
Notação Ω
Prof. Rodrigo Freitas Silva / UFES 115
Notação Ω
o Quando a notação Ω é usada para expressar o tempo de execução de 
um algoritmo no melhor caso, está se definindo também o limite 
(inferior) do tempo de execução desse algoritmo para todas as 
entradas
o Por exemplo, o algoritmo de ordenação por inserção é Ω(n) no melhor caso
o O tempo de execução do algoritmo de ordenação por inserção é Ω(n)
Prof. Rodrigo Freitas Silva / UFES 116
Notação Ω
o O tempo de execução da ordenação por inserção recai sobre Ω(n) e O(n2)
o Fica em qualquer lugar entre uma função linear de n e uma função 
quadrática de n
o Esses limites são assintoticamente tão restritos quanto possível
o O tempo de ordenação NÂO é Ω(n2) pois existe uma entrada na qual a 
ordenação é executada no tempo Θ(n) (quando a entrada já está ordenada)
o Contudo: Não é contraditório dizer que o tempo de execução do PIOR 
CASO da ordenação por inserção é Ω(n2), já que existe uma entrada que faz o 
algoritmo demorar o tempo Ω(n2)
Prof. Rodrigo Freitas Silva / UFES 117
Notação Ω
o O que significa dizer que “o tempo de execução” (i.e., sem especificar 
se é para o pior caso, melhor caso, ou caso médio) é Ω(g(n))?
o O tempo de execução desse algoritmo é pelo menos (melhor caso) uma 
constante vezes g(n) para valores suficientemente grandes de n
Prof. Rodrigo Freitas Silva / UFES 118
Notação Ω: Exemplos
o Para mostrar que f(n) = 3n3 + 2n2 é Ω(n3) basta fazer c = 1, e então:
3n3 +2n2 ≥ n3 para n ≥ 0
o Mostrar que f(n) = n3 + 100n é Ω(n3) , pois n3 + 100n ≥ n3 para 
todo n
Prof. Rodrigo Freitas Silva / UFES 119
Notação Ω: Exercícios
1) Mostrar que f(n) = n2 - 2n é Ω(n2).
2) Mostrar que f(n) = n log n é Ω(n).
3) Mostrar que f(n) = 100 n não está em Ω(n2).
FAÇAM !!!!
Prof. Rodrigo Freitas Silva / UFES 120
Notação Ω: Resolução dos Exercícios
1. Mostrar que f(n) = n2 - 2n é Ω(n2).
De fato n2 - 2n ≥ ½ n2 para todo n ≥ 4, pois:
n2 - 2n ≥ n2 - ½ n2 = ½ n2 
2. Mostrar que f(n) = n log n é Ω(n).
De fato para todo n ≥ 2 tem-se lg n ≥ 1 e portanto (n log n ≥ n)
3. Mostrar que f(n) = 100 n não está em Ω(n2).
100n ≥ c*n2  100 ≥ c*n
Logo, percebemos que 100 não é maior que n para n suficientemente grande
Prof. Rodrigo Freitas Silva / UFES 121
Teorema
o Para quaisquer funções f(n) e g(n), tem-se:
f(n) = Θ(g(n)) se e somente se, 
f(n) = O(g(n)), e
f(n) = Ω(g(n))
Prof. Rodrigo Freitas Silva / UFES 122
POSCOMP 2007
o Observe as funções representadas no gráfico abaixo e assinale a alternativa 
FALSA sobre o crescimento assintótico dessas funções.
A. f(n) = O(h(n)) e i(n) = Ω(g(n)) D. g(n) = O(i(n)), i(n) = O(f(n)) e, portanto, g(n) = O(f(n))
B. f(n) = Θ(h(n)) e i(n) = Ω(h(n)) E. h(n) = Ω(i(n)), logo, i(n) = O(h(n))
C. g(n) = O(i(n)) e h(n) = Ω(g(n))
Prof. Rodrigo Freitas Silva / UFES 123
POSCOMP 2007
o Observe as funções representadas no gráfico abaixo e assinale a alternativa 
FALSA sobre o crescimento assintótico dessas funções.
A. f(n) = O(h(n)) e i(n) = Ω(g(n)) D. g(n) = O(i(n)), i(n) = O(f(n)) e, portanto, g(n) = O(f(n))
B. f(n) = Θ(h(n)) e i(n) = Ω(h(n)) E. h(n) = Ω(i(n)), logo, i(n) = O(h(n))
C. g(n) = O(i(n)) e h(n) = Ω(g(n))
Prof. Rodrigo Freitas Silva / UFES 124
POSCOMP 2003
o Quais das seguintes igualdades são verdadeiras?
I. n2 = O(n3)
II. 2*n + 1 = O(n2)
III. n3 = O(n2)
IV. 3*n + 5*n log n = O(n)
V. log n + 𝑛= O(n)
A. Somente I e II
B. Somente II, III e IV
C. Somente III, IV e V
D. Somente I, II e V
E. Somente I, III e IV
Prof. Rodrigo Freitas Silva / UFES 125
POSCOMP 2003
o Quais das seguintes igualdades são verdadeiras?
I. n2 = O(n3)
II. 2*n + 1 = O(n2)
III. n3 = O(n2)
IV. 3*n + 5*n log n = O(n)
V. log n + 𝑛= O(n)
A. Somente I e II
B. Somente II, III e IV
C. Somente III, IV e V
D. Somente I, II e V
E. Somente I, III e IV
Prof. Rodrigo Freitas Silva / UFES 126
Mais sobre notação assintótica
o Existem duas outras notações na análise assintótica de funções:
Notação o (“O” pequeno)
Notação ω (ômega pequeno)
o Estas duas notações não são usadas normalmente, mas é importante saber 
seus conceitos e diferenças em relação às notações O e Ω, respectivamente
Prof. Rodrigo Freitas Silva / UFES 127
Notação o
o O limite assintótico superior definido pela notação O pode ser 
assintoticamente firme (restrito) ou não
 Por exemplo, o limite 2n2 = O(n2) é assintoticamente firme, mas o limite 
2n = O(n2) não é
o A notação o é usada para definir um limite superior que NÃO É 
assintoticamente firme
o Formalmente a notação o é definida como:
 Exemplo: 2n = o(n2) mas 2n2 ≠ o(n2).
Prof. Rodrigo Freitas Silva / UFES 128
Notação o
o A principal diferença entre O e o:
o f(n) = O(g(n)), o limite 0 ≤ f(n) ≤ c g(n) é valido para alguma constante c > 0
o f(n) = o(g(n)), o limite 0≤ f(n) < c g(n) é valido para todas constante c > 0 
o Intuitivamente, a função f(n) tem um crescimento muito menor que 
g(n) quando n tende para infinito. Isto pode ser expresso da seguinte 
forma:
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= 0
o Alguns autores usam este limite como a definição de o
Prof. Rodrigo Freitas Silva / UFES 129
o Por analogia, a notação ω está relacionada com a notação Ω da mesma 
forma que a notação o está relacionada com a notação O
o Formalmente a notação ω é definida como:
 Por exemplo, 
n2
2
= ω(n), mas 
n2
2
≠ ω(n2)
o A relação f(n) = ω(g(n)) implica em:
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= ∞
se o limite existir.
Notação ω
Prof. Rodrigo Freitas Silva / UFES 130
Uma forma de comparar o “tamanho” das notações
O ≈ ≤ 
Ω ≈ ≥
Θ ≈ =
o ≈ <
ω ≈ >
Dizemos que f(n) é assintoticamente menor que g(n) se f(n)=o(g(n)), 
e que f(n) é assintoticamente maior que g(n) se f(n)=ω(g(n))
Prof. Rodrigo Freitas Silva / UFES 131
o Normalmente, a notação assintótica é usada em fórmulas 
matemáticas
o Por exemplo, usando a notação O pode-se escrever que:
o n = O(n2)
o 2n2 + 3n + 1 = 2n2 + Θ(n)
o Como se interpreta uma fórmula como esta?
Notação assintótica em funções
Prof. Rodrigo Freitas Silva / UFES 132
Notação assintótica em funções
o Notação assintótica sozinha no lado direito de uma equação, 
como em n = O(n2)
o Sinal de igualdade significa que o lado esquerdo é um membro do conjunto O(n2)
n  O(n2) ou n  O(n2) 
o Nunca deve-se escrever uma igualdade onde a notação O aparece sozinha 
com os lados trocados
o Caso contrário, poderia se deduzir UM ABSURDO como n2 = n de igualdades 
como em O(n2) = n
o Quando se trabalha com a notação O e em qualquer outra fórmula que 
envolve quantidades não precisas, o sinal de igualdade é unidirecional
o Daí vem o fato que o sinal de igualdade ("=") realmente significa  ou , usados 
para inclusão de conjuntos
Prof. Rodrigo Freitas Silva / UFES 133
Notação assintótica em funções
Se uma notação assintótica aparece numa fórmula, isso significa que 
essa notação está substituindo uma função que não é importante 
definir precisamente (por algum motivo)
o Por exemplo, a equação:
2n2 + 3n + 1 = 2n2 + Θ(n)
significa que
2n2 + 3n + 1 = 2n2 + f(n)
onde f(n) é alguma função no conjunto Θ(n). Neste caso, f(n) = 3n + 1, que 
de fato está em Θ(n).
Prof. Rodrigo Freitas Silva / UFES 134
o O uso da notação assintótica desta forma ajuda a eliminar detalhes 
que não são importantes
o Por exemplo, pode-se expressar uma equação de recorrência como:
T(n) = 2T(n - 1) + Θ(n)
o Se deseja determinar o comportamento assintótico de T(n) então 
não é necessário determinar exatamente os termos de mais baixa 
ordem
o Entende-se que eles estão incluídos numa função f(n) expressa no 
termo Θ(n)
Notação assintótica em funções
Prof. Rodrigo Freitas Silva / UFES 135
Notação assintótica em funções
o Em alguns casos, a anotação assintótica aparece do lado esquerdo de uma 
equação como em:
2n2 + Θ(n) = Θ(n2)
A interpretação de tais equações deve ser feita usando a seguinte regra:
o É possível escolher uma função f(n) para o lado esquerdo da igualdade de tal 
forma que existe uma função g(n) para o lado direito que faz com que a 
equação seja válida
o O lado direito da igualdade define um valor não tão preciso quanto o lado 
esquerdo
Por exemplo:
2n2 +3n+1 = 2n2 + Θ(n)
2n2 + Θ(n) = Θ(n2)
Prof. Rodrigo Freitas Silva / UFES 136
Notação assintótica em funções
o Equações:
1. 2n2 +3n+1 = 2n2 + Θ(n)
2. 2n2 + Θ(n) = Θ(n2)
o As equações (1) e (2) podem ser interpretadas da seguinte maneira:
o (1) diz que existe alguma função f(n)  Θ(n) tal que
2n2 + 3n+1 = 2n2 + f(n) para todo n
o (2) diz que para qualquer função g(n)  Θ(n), existe uma função h(n) 
Θ(n2) tal que 2n2 +g(n) = h(n) para todo n
Prof. Rodrigo Freitas Silva / UFES 137
Notação assintótica em funções
o Equações:
1. 2n2 +3n+1 = 2n2 + Θ(n)
2. 2n2 + Θ(n) = Θ(n2)
o Note que esta interpretação implica que 2n2 + 3n + 1 = Θ(n2), que é o que 
estas duas equações querem dizer
Logo  2n2 +3n+1 = Θ(n2)
Prof. Rodrigo Freitas Silva / UFES 138
Notação assintótica em funções
o Exercícios:
1) Sejam f(n) e g(n) funções assintoticamente não negativas. Usando a 
definição básica da notação Θ, prove que max(f(n), g(n)) = Θ(f(n) + g(n))
2) Mostre que, para quaisquer constantes reais a e b, onde b > 0, 
(n + a)b = Θ(nb)
3) É verdade que 2n+1 = O(2n) ??? É verdade que 22n = O(2n) ???
4) f(n) = O(g(n)) implica g(n) = O(f(n)) ????
Prof. Rodrigo Freitas Silva / UFES 139
Notação assintótica em funções
o Exercícios - Resolução
1) Sejam f(n) e g(n) funções assintoticamente não negativas. Usando a definição 
básica da notação Θ, prove que max(f(n), g(n)) = Θ(f(n) + g(n)).
R: Mostrar que max(f(n), g(n)) = Θ(f(n) + g(n)) significa dizer que existem 
constantes positivas c1, c2 e n0 tal que:
0 ≤ c1(f(n) + g(n)) ≤ max(f(n), g(n)) ≤ c2(f(n) + g(n)) para todo n ≥ n0
o Se escolhermos c2 = 1, a terceira inequação é claramente satisfeita, já que a maior das 
duas funções deve ser menor que sua soma.
o Poderíamos escolher c1 como ½, já que a maior das funções é sempre maior do que a 
média entre f(n) e g(n) Prof. Rodrigo Freitas Silva / UFES 140
o Exercícios - Resolução
2) Mostre que, para quaisquer constantes reais a e b, onde b > 0, (n + a)b = Θ(nb)
R: Precisaremos achar as constantes positivas c1, c2 e n0 > 0, tal que:
0 ≤ c1n
b ≤ (n + a)b ≤ c2n
b para todo n ≥ n0
Note que: n + a ≤ n + |a| ≤ 2n quando |a| ≤ n
n + a ≥ n - |a| ≥ ½ n quando |a| ≤ ½ n  n ≥ 2|a|
Logo:
0 ≤ ½ n ≤ n + a ≤ 2n
 0 ≤ (½ n)b ≤ (n + a)b ≤ (2n)b
 0 ≤ (½)b nb ≤ (n + a)b ≤ 2bnb
Assim, c1 = (1/2)b, c2 = 2b, e n0 = 2|a| satisfaz a definição.
Notação assintótica em funções
Prof. Rodrigo Freitas Silva / UFES 141
Notação assintótica em funções
o Exercícios - Resolução
3) É verdade que 2n+1 = O(2n) ??? É verdade que 22n = O(2n) ???
R: Para mostrar que 2n+1 = O(2n) devemos achar as constantes 
c, n0 > 0 que:
0 ≤ 2n+1 ≤ c (2n) para todo n ≥ n0
Já que 2n+1 = 2(2n) para todo n, a definição é satisfeita com c = 2 e n0 = 1 
Prof. Rodrigo Freitas Silva / UFES 142
Notação assintótica em funções
o Exercícios - Resolução
3) É verdade que 2n+1 = O(2n) ??? É verdade que 22n = O(2n) ???
R: Vamos assumir que existam constantes c, n0 > 0 tais que:
0 ≤ 22n ≤ c (2n) para todo n ≥ n0
Logo 22n = (2n)2 = 2n(2n) ≤ c (2n)  2n ≤ c
Mas nenhuma constante é maior que todos 2n
Assim, 22n ≠ O(2n) 
Prof. Rodrigo Freitas Silva / UFES 143
Notação assintótica em funções
o Exercícios - Resolução
4) f(n) = O(g(n)) implica g(n) = O(f(n)) ????
o Não, f(n) = O(g(n)) não implica g(n) = O(f(n)).
o Como contra-exemplo tem-se: f(n) = n e g(n) = n2
Logo:
n = O(n2) mas n2 ≠ O(n)
Prof. Rodrigo Freitas Silva / UFES 144
POSCOMP 2002
Quais das seguintes afirmações sobre crescimento assintótico de 
funções não é verdadeira?
a) 2n2 + 3n + 1 = O(n2)
b) Se f(n) = O(g(n)) então g(n) = O(f(n))
c) log n2 = O(log n)
d) Se f(n) = O(g(n)) e g(n) = O(h(n)) então f(n) = O(h(n)) 
e) 2n+1 = O(2n)
Prof. Rodrigo Freitas Silva / UFES 145
POSCOMP 2002
Quais das seguintes afirmações sobre crescimento assintótico de 
funções não é verdadeira?
a) 2n2 + 3n + 1 = O(n2)
b) Se f(n) = O(g(n)) então g(n) = O(f(n))
c) log n2 = O(log n)
d) Se f(n) = O(g(n)) e g(n) = O(h(n)) então f(n) = O(h(n)) 
e) 2n+1 = O(2n)
Prof. Rodrigo Freitas Silva / UFES 146
Comparação de Programas
o Podemos avaliar programas comparando as funções de 
complexidade, negligenciando as constantes de proporcionalidade
o Um programa com tempo de execução O(n) é melhor que outro com 
tempo O(n2)
o Porém, as constantes de proporcionalidade podem alterar esta 
consideração
o Exemplo:um programa leva 100n unidades de tempo para ser executado e 
outro leva 2n2. Qual dos dois programas é melhor?
Prof. Rodrigo Freitas Silva / UFES 147
Comparação de Programas
o Exemplo: um programa leva 100n unidades de tempo para ser 
executado e outro leva 2n2. Qual dos dois programas é melhor?
o Depende do tamanho do problema
o Para n < 50, o programa com tempo 2n2 é melhor do que o que possui 
tempo 100n
o Para problemas com entrada de dados pequena é preferível usar o 
programa cujo tempo de execução é O(n2)
o Entretanto, quando n cresce, o programa com tempo de execução O(n2) 
leva muito mais tempo que o programa O(n)
Prof. Rodrigo Freitas Silva / UFES 148
Classes de Comportamento Assintótico
Complexidade Constante
o f(n) = O(1)
o Mais rápido, impossível !!!!!
o O uso do algoritmo independe do tamanho de n.
o As instruções do algoritmo são executadas um número fixo de vezes.
o O que significa um algoritmo ser O(2) ou O(5)?
Prof. Rodrigo Freitas Silva / UFES 149
Classes de Comportamento Assintótico
Complexidade Logarítmica
o f(n) = O(log n)
o Ocorre tipicamente em algoritmos que resolvem um problema 
transformando em problemas menores
o Supondo que a base do logaritmo seja 2:
o Para n = 1 000, log2 1 000 ≈ 10.
o Para n = 1 000 000, log2 1 000 000 ≈ 20.
o Exemplo:
o Algoritmo de pesquisa binária.
Prof. Rodrigo Freitas Silva / UFES 150
Classes de Comportamento Assintótico
Complexidade Logarítmica
62
4
751 3
o Algoritmo de pesquisa binária (Árvore binária completa)
o Complexidade do algoritmo em relação ao número de comparações 
realizadas
o Número de comparações feitas depende da altura da árvore
o Lema: Seja T uma árvore binária completa com n > 0 nós. Então T 
possui altura h mínima. Além disso, h = 1 + └ log2 n ┘
o Complexidade do algoritmo de busca em uma árvore binária completa é O(log2 n)
Prof. Rodrigo Freitas Silva / UFES 151
Classes de Comportamento Assintótico
Complexidade Linear
o f(n) = O(n)
o Em geral, um pequeno trabalho é realizado sobre cada elemento de 
entrada
o Esta é a melhor situação possível para um algoritmo que tem que 
processar/produzir n elementos de entrada/saída.
o Cada vez que n dobra de tamanho, o tempo de execução também dobra.
o Exemplos:
o Algoritmo de pesquisa sequencial
o Algoritmo para teste de planaridade de um grafo
Prof. Rodrigo Freitas Silva / UFES 152
Classes de Comportamento Assintótico
Complexidade Linear Logarítmica
o f(n) = O(n log n)
o Este tempo de execução ocorre tipicamente em algoritmos que resolvem 
um problema quebrando-o em problemas menores, resolvendo cada um 
deles independentemente e depois agrupando as soluções
o Caso típico dos algoritmos baseados no paradigma divisão-e-conquista
o Exemplo:
o Algoritmo de ordenação MergeSort.
Prof. Rodrigo Freitas Silva / UFES 153
Classes de Comportamento Assintótico
Complexidade Quadrática
o f(n) = O(n2)
o Algoritmos desta ordem de complexidade ocorrem quando os itens de 
dados são processados aos pares, muitas vezes em um loop dentro do 
outro
o Sempre que n dobra, o tempo de execução é multiplicado por 4
o Para n = 1 000, o número de operações é da ordem de 1 000 000
o Algoritmos deste tipo são úteis para resolver problemas de tamanhos 
relativamente pequenos
o Exemplos:
o Algoritmos de ordenação simples como seleção e inserção
Prof. Rodrigo Freitas Silva / UFES 154
Classes de Comportamento Assintótico
Complexidade Cúbica
o f(n) = O(n3)
o Algoritmos desta ordem de complexidade geralmente são úteis apenas 
para resolver problemas relativamente pequenos
o Sempre que n dobra o tempo de execução é multiplicado por 8
o Exemplo:
o Algoritmo para multiplicação de matrizes
Prof. Rodrigo Freitas Silva / UFES 155
Classes de Comportamento Assintótico
Complexidade Exponencial
o f(n) = O(2n)
o Algoritmos desta ordem de complexidade não são úteis sob o ponto de 
vista prático
o Eles ocorrem na solução de problemas quando se usa a força bruta para 
resolvê-los
o Sempre que n dobra o tempo de execução fica elevado ao quadrado
o Exemplo:
o Algoritmo do Caixeiro Viajante
Prof. Rodrigo Freitas Silva / UFES 156
Classes de Comportamento Assintótico
Complexidade Exponencial
o f(n) = O(n!)
o Um algoritmo de complexidade O(n!) é dito ter complexidade 
exponencial, apesar de O(n!) ter comportamento muito pior do que O(2n).
o Geralmente ocorrem quando se usa força bruta na solução do problema
o Considerando:
o n = 20, temos que 20! = 2432902008176640000, um número com 19 
dígitos
o n = 40 temos um número com 48 dígitos
Prof. Rodrigo Freitas Silva / UFES 157
Hierarquia de funções
o A seguinte hierarquia de funções pode ser definida do ponto de vista 
assintótico:
onde є e c são constantes arbitrárias com 0 < є < 1 < c.
o Em casa, desenhe os gráficos dessas funções, quando n -> ∞ !!!!!
Prof. Rodrigo Freitas Silva / UFES 158
Algoritmo exponencial X Algoritmo polinomial
o Funções de complexidade:
o Algoritmo exponencial no tempo de execução: um algoritmo cuja função 
de complexidade é O(cn); c > 1
o Algoritmo polinomial no tempo de execução: um algoritmo cuja função de 
complexidade é O(p(n)), onde p(n) é um polinômio de grau n
Prof. Rodrigo Freitas Silva / UFES 159
Algoritmo exponencial X Algoritmo polinomial
o Funções de complexidade:
o Algoritmo exponencial no tempo de execução
o Algoritmo polinomial no tempo de execução
o A distinção entre estes dois tipos de algoritmos torna-se significativa 
quando o tamanho do problema a ser resolvido cresce
o Esta é a razão porque algoritmos polinomiais são muito mais úteis 
na prática do que algoritmos exponenciais
o Geralmente, algoritmos exponenciais são simples variações de pesquisa 
exaustiva
Prof. Rodrigo Freitas Silva / UFES 160
A distinção entre algoritmos polinomiais eficientes e algoritmos 
exponenciais ineficientes possui várias exceções:
o Exemplo: um algoritmo com função de complexidade f(n) = 2n é mais 
rápido que um algoritmo g(n) = n5 para valores de n menores ou iguais a 20
o Também existem algoritmos exponenciais que são muito úteis na prática
o Exemplo: o algoritmo Simplex para programação linear possui complexidade de 
tempo exponencial para o pior caso mas executa muito rápido na prática
o Tais exemplos não ocorrem com frequência na prática, e muitos algoritmos 
exponenciais conhecidos não são muito úteis
Algoritmo exponencial X Algoritmo polinomial
Prof. Rodrigo Freitas Silva / UFES 161
Exercício 1
Dois algoritmos A e B possuem complexidade n5 e 2n, respectivamente. 
Você utilizaria o algoritmo B ao invés do A? Em qual caso? 
Exemplifique.
Prof. Rodrigo Freitas Silva / UFES 162
Exercício 1
Dois algoritmos A e B possuem complexidade n7 e 3n, respectivamente. 
Você utilizaria o algoritmo B ao invés do A? Em qual caso? 
Exemplifique.
Resposta: Sim. Apesar do algoritmo ser exponencial, quando o 
valor de n é pequeno, esta função produz um tempo de complexidade 
menor do que a função do algoritmo A. Por exemplo para valores de n
de 2 a 15 
Prof. Rodrigo Freitas Silva / UFES 163
Algoritmo de Ordenação por Inserção
o Algoritmo eficiente para ordenar um número pequeno de elementos
o Funciona da maneira como muitas pessoas ordenam as cartas em um jogo
o Inicia-se com a mão esquerda vazia e as cartas viradas com a face para baixo na mesa
o Em seguida remove-se uma carta de cada vez da mesa, inserindo-a na posição correta na mão 
esquerda
o Para encontrar a posição correta de uma carta, vamos compará-la a cada uma das cartas que já 
estão na mão, da direita para a esquerda
Prof. Rodrigo Freitas Silva / UFES 164
Algoritmo de Ordenação por Inserção
o Exemplo para o vetor A = [5, 2, 4, 6, 1, 3]
Prof. Rodrigo Freitas Silva / UFES 165
Algoritmo de Ordenação por Inserção
Custo de tempo de cada instrução
o Será apresentado a função Insertion-Sort com o custo de tempo de cada 
instrução e o número de vezes que cada instrução é executada
o OBS: Quando um loop for ou while terminadevido ao teste no cabeçalho 
do loop, O TESTE É EXECUTADO UMA VEZ ALÉM DO CORPO DO LOOP 
o Comentários não são instruções executáveis, por isso não demandam 
nenhum custo.
Prof. Rodrigo Freitas Silva / UFES 166
Algoritmo de Ordenação por Inserção
Custo de tempo de cada instrução (levando em consideração que o teste do loop é executado uma vez 
a mais além do seu corpo)
tj é o n
o de vezes que o teste do loop while na linha 5 é executado para esse valor de j
Prof. Rodrigo Freitas Silva / UFES 167
Algoritmo de Ordenação por Inserção
Custo de tempo de cada instrução (levando em consideração que o teste do loop é executado uma vez 
a mais além do seu corpo)
o O tempo de execução do algoritmo é a soma dos tempos de execução para cada 
instrução executada
T(n) = c1n + c2(n-1) + c4(n-1) + c5σ𝑗=2
𝑛 𝑡𝑗 + c6σ𝑗=2
𝑛 (𝑡𝑗 − 1) + c7σ𝑗=2
𝑛 (𝑡𝑗 − 1) + c8(n-1)
Prof. Rodrigo Freitas Silva / UFES 168
Algoritmo de Ordenação por Inserção
Custo de tempo de cada instrução – MELHOR CASO
o O melhor caso ocorre quando o vetor já está ordenado, não entrando no laço 
while nenhuma vez, logo:
T(n) = c1n + c2(n-1) + c4(n-1) + c5σ𝑗=2
𝑛 𝑡𝑗 + c6σ𝑗=2
𝑛 (𝑡𝑗 − 1) + c7σ𝑗=2
𝑛 (𝑡𝑗 − 1) + c8(n-1) 
= c1n + c2(n-1) + c4(n-1) + c5(n-1) + c8(n-1) 
= (c1 + c2 + c4 + c5 + c8)n – (c2 + c4 + c5 + c8)
o Esse tempo de execução pode ser expresso como an + b para constantes a e b 
que dependem dos custos de instrução ci
o Logo, é uma função linear de n
Prof. Rodrigo Freitas Silva / UFES 169
Algoritmo de Ordenação por Inserção
Custo de tempo de cada instrução – PIOR CASO (levando em consideração que o teste do loop é 
executado uma vez a mais além do seu corpo)
o O pior caso ocorre quando o vetor estiver em ordem inversa (decrescente)
o Sabe-se que:
o σ𝑗=2
𝑛 𝑗 = 
𝑛(𝑛+1)
2
-1
o σ𝑗=2
𝑛 (𝑗 − 1) = σ𝑗=1
𝑛−1 𝑗 = 
𝑛(𝑛−1)
2
T(n) = c1n + c2(n-1) + c4(n-1) + c5σ𝑗=2
𝑛 𝑡𝑗 + c6σ𝑗=2
𝑛 (𝑡𝑗 − 1) + c7σ𝑗=2
𝑛 (𝑡𝑗 − 1) + c8(n-1) 
= c1n + c2(n-1) + c4(n-1) + c5
𝑛(𝑛+1)
2
−1 + c6
𝑛(𝑛−1)
2
+ c7
𝑛(𝑛−1)
2
+ c8(n-1) 
= 
c5
2
+
c6
2
+
c7
2
n2 + c1 + c2 + c4 +
c5
2
−
c6
2
−
c7
2
+ 𝑐8 n – (c2 + c4 + c5 + c8)
Prof. Rodrigo Freitas Silva / UFES 170
Funções de custo (em relação ao no de comparações) do 
algoritmo de ordenação por Inserção
Prof. Rodrigo Freitas Silva / UFES 171
o Levando em consideração somente o custo C5
(custo unitário para cada comparação) :
o No loop mais interno, na i-ésima iteração, o valor de C5 é:
• melhor caso: C5 (n) = 1
• pior caso: C5 (n) = j
• caso médio: C5(n) = 1/j (1 + 2 + ... + j) = (j+1)/2
o Assumindo que todas as permutações de n são igualmente prováveis:
• melhor caso: C5 (n) = σ𝑗=2
𝑛 1 = n – 1
• pior caso: C5 (n) = σ𝑗=2
𝑛 𝑗 = 
𝑛(𝑛+1)
2
-1 = n2/2 + n/2 - 1
• caso médio : C5 (n) = ½ (3 + 4 + ... + n + 1) = n
2/4 + 3n/4 - 1
Funções de custo (em relação ao no de comparações) do 
algoritmo de ordenação por Inserção
Prof. Rodrigo Freitas Silva / UFES 172
Funções de custo e notações assintóticas do algoritmo de 
ordenação por Inserção
Prof. Rodrigo Freitas Silva / UFES 173
Algoritmo de Ordenação por Inserção
Custo em relação ao no de comparações 
Insertion-Sort(A)
for j := 2 to length[A] do
key := A[j]
i := j – 1
(Insere A[j] na sequencia ordenada A[1 . . j – 1])
while i > 0 and A[i] > key do
A[i + 1] := A[i]
i := i – 1
end
A[i + 1] := key
end
o Cmelhor_caso (n) = n-1
o Vetor já ordenado
o Não entra no laço ENQUANTO nenhuma vez
Melhor Caso
Prof. Rodrigo Freitas Silva / UFES 174
Algoritmo de Ordenação por Inserção
Custo em relação ao no de comparações (levando em consideração que o teste do loop é executado 
uma vez a mais além do seu corpo)
Insertion-Sort(A)
for j := 2 to length[A] do
key := A[j]
i := j – 1
(Insere A[j] na sequencia ordenada A[1 . . j – 1])
while i > 0 and A[i] > key do
A[i + 1] := A[i]
i := i – 1
end
A[i + 1] := key
end
o Cpior_caso (n) = (2+3+...+n) = (σ𝑖=2
𝑛 (𝑖) ) = (σ𝑖=1
𝑛 (𝑖) ) -1 = 
𝑛(𝑛+1)
2
-1 = 
𝑛2
2
+ 
𝑛
2
-1
o Vetor em ordem decrescente
o Entra no laço ENQUANTO todas as vezes e faz todas trocas possíveis
Pior Caso
175
Algoritmo de Ordenação por Inserção
Custo em relação ao no de comparações (teste do loop NÂO é executado uma vez a mais)
Insertion-Sort(A)
for j := 2 to length[A] do
key := A[j]
i := j – 1
(Insere A[j] na sequencia ordenada A[1 . . j – 1])
while i > 0 and A[i] > key do
A[i + 1] := A[i]
i := i – 1
end
A[i + 1] := key
end
o Avaliação curto-circuito: A[i] > key não é verificado na última avaliação do while para cada
iteração de j pois i é menor que zero 
o Cpior_caso (n) = (1+2+...+n-1) = (σ𝑖=1
𝑛−1(𝑖) ) = (σ𝑖=1
𝑛 (𝑖) ) -n = 
𝑛(𝑛+1)
2
-n = 
𝑛2
2
-
𝑛
2
o Vetor em ordem decrescente
o Entra no laço ENQUANTO todas as vezes e faz todas trocas possíveis
Pior Caso
Limites do algoritmo de ordenação por inserção
o O tempo de execução do algoritmo de ordenação por inserção está 
entre Ω(n) e O(n2).
o Estes limites são assintoticamente os mais firmes possíveis.
o Por exemplo, o tempo de execução deste algoritmo não é Ω(n2), pois o 
algoritmo executa em tempo Θ(n) quando a entrada já está ordenada.
o Não é contraditório dizer que o tempo de execução deste algoritmo 
no pior caso é Ω(n2), já que existem entradas para este algoritmo 
que fazem com que ele execute em tempo Ω(n2).
Prof. Rodrigo Freitas Silva / UFES 177
Algoritmo de Ordenação por Inserção
Insertion-Sort(A)
for j := 2 to length[A] do
key := A[j]
i := j – 1
(Insere A[j] na sequencia ordenada A[1 . . j – 1])
while i > 0 and A[i] > key do
A[i + 1] := A[i]
i := i – 1
A[i + 1] := key
end
end
o Pergunta: Hoje, dos algoritmo de ordenação mais utilizados, o que possui menor 
complexidade é o inserção, considerando o seu melhor caso, O(n). Podemos dizer que nenhum 
outro algoritmo poderá atingir uma complexidade melhor do que esta? Justifique.
Prof. Rodrigo Freitas Silva / UFES 178
Algoritmo de Ordenação por Inserção
Exercício 1
o Pergunta: Hoje, dos algoritmo de ordenação mais utilizados, o que possui 
menor complexidade é o inserção, considerando o seu melhor caso, Θ(n). Podemos 
dizer que nenhum outro algoritmo poderá atingir uma complexidade melhor do que 
esta? Justifique.
o Resposta: Sim. Para resolver o problema é necessário que todos os valores 
pertencentes a entrada sejam avaliados, ou seja, podemos dizer que qualquer 
algoritmo proposto será no mínimo Ω(n).
Prof. Rodrigo Freitas Silva / UFES 179
Algoritmo de Ordenação por Seleção
Levando em consideração o custo de tempo de cada instrução e que o teste do loop é executado uma 
vez a mais além do seu corpo
Exercício 2
Considere a ordenação de n números armazenados no vetor A, localizando 
primeiro o menor elemento de A e permutando esse elemento com o elemento 
contido em A[1]. Em seguida, encontre o segundo menor elemento de A e o troque 
pelo elemento A[2]. Continue dessa maneira para os n-1 elementos de A. Escreva o 
pseudocódigo para esse algoritmo, conhecido como ordenação por seleção. 
Porque ele só precisa ser executado para os n-1 elementos, e não para todos os n 
elementos? Forneça os tempos de execução do melhor caso e do pior caso da 
ordenação por seleção em notação Θ. 
OBS: Leve em consideração o custo de tempo de cada instrução 
o Resposta: Próximos slides.
Prof. Rodrigo Freitas Silva / UFES 180
Algoritmo de Ordenação por Seleção
Levando em consideração o custo de tempo de cada instrução e que o teste do loop é 
executado uma vez a mais além do seu corpo 
Exercício 2 - Resposta Cost times
c1 n
c2 n-1
c3 σ𝑗=2
𝑛 𝑗
c4 σ𝑗=1
𝑛−1 𝑗
c5 σ𝑗=1
𝑛−1 𝑗 tj,i
c6 n-1
• tj,i = 1 quando o if for verdadeiro e, tj,i = 0 caso contrário
Prof. Rodrigo Freitas Silva / UFES 181
Algoritmo de Ordenação por Seleção
Levando em consideração o custo de tempo de cada instrução e que o teste do loop é executado umavez a mais além do seu corpo
o Exercício 2 - Resposta
o O tempo de execução do algoritmo é a soma dos tempos de execução para cada 
instrução executada
o Lembre-se: ti,j = 1 quando o if for verdadeiro e, ti,j = 0 caso contrário
Logo:
o T(n) = c1n + c2 (n - 1) + c3(σ𝑗=2
𝑛 𝑗) + c4(σ𝑗=1
𝑛−1 𝑗) + c5 (σ𝑗=1
𝑛−1 𝑗 tj,i) + c6 (n – 1)
182
Algoritmo de Ordenação por Seleção
Levando em consideração o custo de tempo de cada instrução e que o teste do loop é executado uma 
vez a mais além do seu corpo
o Exercício 2 – Resposta
o Sabe-se que:
o ti,j = 1 quando o if for verdadeiro e, ti,j = 0 caso contrário
o σ𝑗=2
𝑛 𝑗 = 
𝑛(𝑛+1)
2
-1
o σ𝑗=1
𝑛−1 𝑗 = 
𝑛(𝑛−1)
2
o σ𝑗=1
𝑛−1 𝑗 tj,i = 
𝑛(𝑛−1)
2
quando tj,i = 1 e 0 caso contrário
o Lembre-se:
T(n) = c1n + c2 (n - 1) + c3(σ𝑗=2
𝑛 𝑗) + c4(σ𝑗=1
𝑛−1 𝑗) + c5 (σ𝑗=1
𝑛−1 𝑗 tj,i) + c6 (n – 1)
Prof. Rodrigo Freitas Silva / UFES 183
Algoritmo de Ordenação por Seleção
Levando em consideração o custo de tempo de cada instrução e que o teste do loop é executado uma 
vez a mais além do seu corpo
o Exercício 2 – Resposta
T(n) = c1n + c2 (n - 1) + c3(σ𝑗=2
𝑛 𝑗) + c4(σ𝑗=1
𝑛−1 𝑗) + c5 (σ𝑗=1
𝑛−1 𝑗 tj,i) + c6 (n – 1)
Logo:
o MELHOR CASO: o if é sempre falso (todos tj,i = 0)
T(n) = c1n + c2 (n - 1) + c3
𝑛(𝑛+1)
2
−1 + c4 
𝑛(𝑛−1)
2
+ c5 (0) + c6 (n – 1) = 
= 
c3
2
+
c4
2
n2 + c1 + c2 +
c3
2
−
c4
2
+ 𝑐6 n - (c2 + c3 + c6)
o PIOR CASO: o if é sempre verdadeiro (todos tj,i = 1)
T(n) = c1n + c2 (n - 1) + c3
𝑛(𝑛+1)
2
−1 + c4 
𝑛(𝑛−1)
2
+ c5 
𝑛(𝑛−1)
2
+ c6 (n – 1) = 
= 
c3
2
+
c4
2
+
c5
2
n2 + c1 + c2 +
c3
2
−
c4
2
−
c5
2
+ 𝑐6 n - (c2 + c3 + c6)
Prof. Rodrigo Freitas Silva / UFES 184
Algoritmo de Ordenação por Seleção
Levando em consideração o custo de tempo de cada instrução e que o teste do loop é executado uma 
vez a mais além do seu corpo
o Exercício 2 – Resposta
o MELHOR CASO: 
T(n) = 
c3
2
+
c4
2
n2 + c1 + c2 +
c3
2
−
c4
2
+ 𝑐6 n - (c2 + c3 + c6)
o PIOR CASO:
T(n) = 
c3
2
+
c4
2
+
c5
2
n2 + c1 + c2 +
c3
2
−
c4
2
−
c5
2
+ 𝑐6 n - (c2 + c3 + c6)
o Em ambos os casos tem-se: T(n) = an2 + bn + c
Logo temos que T(n) = Θ(n2)
Prof. Rodrigo Freitas Silva / UFES 185
Algoritmo de Ordenação por Seleção
CONSIDERANDO SOMENTE O NÚMERO DE COMPARAÇÕES
o Exercício 2 – Resposta
o MELHOR CASO e PIOR CASO : 
T(n) = (n-1) + (n-2) + ... + 2 + 1 = σ𝑗=1
𝑛−1 𝑗 = 
𝑛(𝑛−1)
2
Lembre-se: Leva em consideração somente o custo 4 (c4)
Logo temos que T(n) = Θ(n2)
186
Algoritmo de Ordenação por Seleção
Exercício 2 - Resposta
R: Após os primeiros n-1 elementos, o subvetor A[1 .. n-1] contém 
ordenado os menores n-1 elementos, e por isso o elemento A[n] será o maior 
elemento.
O tempo de execução do algoritmo é Θ(n2) para todos os casos.
Prof. Rodrigo Freitas Silva / UFES 187
Algoritmo de Ordenação – Bubblesort
CONSIDERANDO SOMENTE O NÚMERO DE COMPARAÇÕES
Exercício 3 - Como é o tempo de execução do pior caso do bubblesort? Como 
ele se compara ao tempo de execução do algoritmo de ordenação por inserção?
o OBS: Quando no enunciado do problema não menciona quais operações do 
algoritmo devemos considerar em sua análise de complexidade, usualmente 
consideramos apenas as suas operações mais significativas, nesse caso em 
relação as comparações efetuadas na linha 3
188
Algoritmo de Ordenação – Bubblesort
Considerando somente o número de comparações
Exercício 3 - Como é o tempo de execução do pior caso do bubblesort? Como 
ele se compara ao tempo de execução do algoritmo de ordenação por inserção?
R: O tempo de execução depende do número de iterações do loop for das linhas 2 a 
4. Logo:
T(n) = (n-1) + (n-2) + ... + 2 + 1 = σ𝑗=1
𝑛−1 𝑗 = 
𝑛(𝑛−1)
2
Assim, o tempo de execução do bubblesort é Θ(n2) em todos os casos
O tempo de execução no pior caso é o mesmo do algoritmo de ordenação por 
inserção
Prof. Rodrigo Freitas Silva / UFES 189
Técnicas de análise de algoritmos
o Determinar o tempo de execução de um programa pode ser um 
problema matemático complexo
o Determinar a ordem do tempo de execução, sem preocupação com o 
valor da constante envolvida, pode ser uma tarefa mais simples
o A análise utiliza técnicas de matemática discreta, envolvendo contagem 
ou enumeração dos elementos de um conjunto:
o manipulação de somas
o produtos
o permutações
o fatoriais
o coeficientes binomiais
o solução de equações de recorrência
Prof. Rodrigo Freitas Silva / UFES 190
Análise do tempo de execução
o Comando de atribuição, de leitura ou de escrita: O(1).
o Sequência de comandos: determinado pelo maior tempo de 
execução de qualquer comando da sequência.
o Comando de decisão: tempo dos comandos dentro do comando 
condicional, mais tempo para avaliar a condição, que é O(1).
o Loop ou anel: soma do tempo de execução do corpo do anel mais o 
tempo de avaliar a condição para terminação (geralmente O(1)), 
multiplicado pelo número de iterações.
Prof. Rodrigo Freitas Silva / UFES 191
Análise do tempo de execução
o Procedimentos não recursivos:
o Cada um deve ser computado separadamente um a um, iniciando com os 
que não chamam outros procedimentos
o Avalia-se então os que não chamam os já avaliados (utilizando os tempos 
desses)
o O processo é repetido até chegar no programa principal
o Procedimentos recursivos:
o É associada uma função de complexidade f(n) desconhecida, onde n mede 
o tamanho dos argumentos
Prof. Rodrigo Freitas Silva / UFES 192
Procedimento não recursivo
o Algoritmo para ordenar os n elementos de um conjunto A -
Novamente o algoritmo de Ordenação por Seleção
procedure Ordena (var A: Vetor);
var i, j, min, x: integer;
begin
for i := 1 to n-1 do
begin
min := i;
for j := i+1 to n do
if A[j] < A[min] then min := j;
x := A[min];
A[min] := A[i];
A[i] := x;
end;
end;
Prof. Rodrigo Freitas Silva / UFES 193
Análise do procedimento não recursivo: loop interno
o Contém um comando de decisão (if), com um comando apenas de atribuição. Ambos 
levam tempo constante para serem executados
o Quanto ao corpo do comando de decisão, devemos considerar o pior caso, assumindo 
que será sempre executado
o O tempo para incrementar o índice do anel e avaliar sua condição de terminação é 
O(1)
o O tempo combinado para executar uma vez o anel é O(max(1, 1, 1)) = O(1), conforme 
regra da soma para a notação O
o Como o número de iterações é n - i, o tempo gasto no anel é O((n - i) x 1) = O(n - i), 
conforme regra do produto para a notação O
Prof. Rodrigo Freitas Silva / UFES 194
Análise do procedimento não recursivo: loop externo
o Contém, além do loop interno, quatro comandos de atribuição:
o O(max(1, (n - i), 1, 1, 1)) = O(n - i).
o O loop externo é executado n - 1 vezes, e o tempo total para executar o programa está 
limitado ao produto de uma constante pelo somatório de (n - i):
o σ𝑖=1
𝑛−1(𝑛 − 𝑖) = 
𝑛(𝑛−1)
2
= 
𝑛2
2
-
𝑛
2
= O(n2)
o Considerarmos o número de comparações como a medida de custo relevante, o 
programa faz 
𝑛2
2
-
𝑛
2
comparações para ordenar n elementos
o Se considerarmos o número de trocas, o programa realiza exatamente n – 1 trocas
Prof. Rodrigo Freitas Silva / UFES 195
Algoritmos recursivos 
o Um objeto é recursivo quando é definido parcialmente em termos de 
si mesmo
o Exemplo : Função fatorial
o (a) 0! = 1
o (b) se n > 0 então n! = n(n - 1)!
Prof. Rodrigo Freitas Silva / UFES 196
Eliminando a Recursividade
o Algoritmos recursivos são apropriados quando o problema é definido em 
termos recursivos
o Entretanto, uma definição recursiva não implica necessariamente que a 
implementação recursiva é a melhor solução
Prof. Rodrigo Freitas Silva / UFES 197
Outro Exemplo – série de fibonacci
0 1 1 2 3 5 8 13 21 ...
o Para cada chamada a Fib(n), Fib é ativada 2 vezes
Prof. Rodrigo Freitas Silva / UFES 198
Solução óbvia
Eliminando a Recursividade
o Complexidade de tempo: T(n) = n - 1
Prof. Rodrigo FreitasSilva / UFES 199
Procedimento Recursivo: Recorrência
o Quando um algoritmo contém uma chamada recursiva a ele próprio, seu 
tempo pode frequentemente ser descrito por uma recorrência
o Recorrência é uma equação ou desigualdade que descreve uma função em 
termos de seu valor em entradas menores
o Alguns métodos para resolver recorrência:
o Método da iteração (ou expansão)
o Método da substituição
o Método de árvore de recursão
o Método Mestre (Teorema Mestre)
Prof. Rodrigo Freitas Silva / UFES 200
Análise de algoritmos recursivos
o Comportamento é descrito por uma equação de recorrência
o Enfoque possível: Método da Iteração (expansão)
o Usar a própria recorrência para substituir para T(m), m < n até que todos 
os termos tenham sido substituídos por fórmulas envolvendo apenas T(0) 
ou o caso base
Prof. Rodrigo Freitas Silva / UFES 201
Procedimento Recursivo: Exemplo 1
o Para cada procedimento recursivo é associada uma função de complexidade 
f(n) desconhecida, onde n mede o tamanho dos argumentos para o 
procedimento
o Obtemos uma equação de recorrência para f(n)
Prof. Rodrigo Freitas Silva / UFES 202
Análise do procedimento recursivo: Exemplo 1
o Seja T(n) uma função de complexidade que represente o número de inspeções 
nos n elementos do conjunto.
o O custo de execução das linhas (1) e (2) é O(1) e da linha (3) é O(n).
o Usa-se uma equação de recorrência para determinar o número de 
chamadas recursivas.
o O termo T(n) é especificado em função dos termos anteriores T(1), T(2), ... , T(n - 1).
T(n) = 
1 𝑛 = 1
n + T(
└
n/3
┘
) 𝑛 > 1
o Por exemplo: T(3) = T(3/3)+3 = 4, T(9) = T(9/3)+9 = 13, e assim por diante.
o Para calcular o valor da função seguindo a definição são necessários alguns 
passos para computar o valor de T(3k).
Prof. Rodrigo Freitas Silva / UFES 203
Resolvendo a equação de recorrência: Método da Iteração
o Itera-se sobre a recorrências até encontrar um somatório que 
dependa somente de n e das condições iniciais 
o Logo, substitui-se os termos T(k), k < n, até que todos os termos T(k), 
k > 1, tenham sido substituídos por fórmulas contendo apenas T(1)
T(n) = n + T(n/3)
T(n/3) = n/3 + T(n/32)
T(n/32) = n/32 + T(n/33)
...
T(n/3k) = n/3k + T(n/3k+1)
o Consequentemente:
T(n) = n + n(1/3) + n(1/32) + n(1/33) + ... + (n/3/3 ... /3) 
que representa a soma de uma série geométrica (PG) de razão 1/3, multiplicada por 
n, e adicionada de T(n/3/3/3), que é menor ou igual a 1.
204
Resolvendo a equação de recorrência - Método da Iteração
T(n) = n + n(1/3) + n(1/32) + n(1/33) + ... + (n/3/3 ... /3) 
o Se desprezarmos o termo T(n/3/3 ... /3), quando n tende para infinito, então:
o Se considerarmos o termo T(n/3/3 ... /3) e denominarmos x o número de subdivisões 
por 3 do tamanho do problema, então 
𝑛
3𝑥
será ≤ 1, logo 
𝑛
3𝑥
= 1 (igual a uma inspeção)
Prof. Rodrigo Freitas Silva / UFES 205
Resolvendo a equação de recorrência - Método da Iteração
T(n) = n + n(1/3) + n(1/32) + n(1/33) + ... + (n/3/3 ... /3) 
o Exemplo: T(9) = n + n/3 + 1 (possui 2 subdivisões, i.e. x = 2)
o Logo, o programa do exemplo é O(n)
Prof. Rodrigo Freitas Silva / UFES 206
Resolvendo a equação de recorrência - Método da Iteração
o Ou simplesmente, 
de T(n) = n + n(1/3) + n(1/32) + n(1/33) + ... + (n/3/3 ... /3) 
Supondo n = 3k → k = log3 n
T(3k) = T(30) ... + 3k-2 + 3k -1 + 3k 
= T(1) + σ𝑖=1
𝑘 3𝑖
= 
3n−1
2
T(n) = 
3n−1
2
T(n) = O(n)
o Logo, o programa do exemplo é O(n)
Prof. Rodrigo Freitas Silva / UFES 207
3n−1
2
− 1
onde k = log3 n
Comentários sobre recursividade
o Evitar o uso de recursividade quando existe uma solução óbvia por 
iteração
o Exemplos:
o Fatorial
o Série de Fibonacci
Prof. Rodrigo Freitas Silva / UFES 208
Análise da função fatorial (fat)
function fat(n : integer) : integer;
begin
if n <= 1 then fat := 1
else fat := n * fat(n-1);
end;
o Seja a seguinte equação de recorrência para esta função:
T(n) = 
𝑑 𝑛 = 1
𝑐 + 𝑇 𝑛 − 1 𝑛 > 1
o Esta equação diz que quando n = 1 o custo para executar fat é igual a d.
o Para valores de n maiores que 1, o custo para executar fat é c mais o custo para 
executar T(n - 1)
o Vamos ver a solução desta recorrência !!!
209
Análise da função fatorial (fat)
Resolvendo pelo método da iteração
o A equação de recorrência pode ser expressa da seguinte forma:
T(n) = c + T(n-1) = c + (c + T(n-2)) = c + c + (c + T(n-3)) = ... 
= ... c + c + ... + (c + T(1)) = 𝑐 + 𝑐 … + 𝑐 + 𝑑 = c(n-1) + d
o Em cada passo, o valor do termo T é substituído pela sua definição (ou seja, esta 
recorrência está sendo resolvida pelo método da expansão (iteração))
o A última equação mostra que depois da expansão existem n - 1 constantes do 
tipo c, correspondentes aos valores de 2 até n
o Desta forma, a recorrência pode ser expressa como:
T(n) = c(n - 1)+d = O(n) 
Prof. Rodrigo Freitas Silva / UFES 210
Alguns somatórios úteis para resolução de equações de 
recorrência
o σ𝑖=1
𝑛 𝑖 =
𝑛(𝑛+1)
2
o σ𝑖=0
𝑛 2𝑖 = 2n+1 – 1
o σ𝑖=0
𝑘 1
2𝑖
= 2 -
1
2𝑘
o σ𝑖=0
𝑛 𝑎𝑖 =
𝑎𝑛+1−1
𝑎 − 1
o σ𝑖=0
∞ 𝑖𝑎𝑖 =
𝑥
1 − 𝑎 2
para |x| < 1
o σ𝑖=0
∞ 𝑎𝑖 =
1
1 − 𝑎
o σ𝑖=0
𝑛 𝑖2 =
𝑛(𝑛+1)(2𝑛+1)
6
o σ𝑖=0
𝑛 𝑖3 =
𝑛2(𝑛+1)2
4
Prof. Rodrigo Freitas Silva / UFES 211
Exemplo de recorrências básicas: exemplo 1
T(n) = T(n/2) + 1 (n ≥ 2)
T(1) = 0 (n = 1)
Resolva mais esta recorrência !!!
Prof. Rodrigo Freitas Silva / UFES 212
Exemplo de recorrências básicas: exemplo 1
T(n) = T(n/2) + 1 (n ≥ 2)
T(1) = 0 (n = 1)
Resolução:
Vamos supor que n = 2k → k = log2 n
Resolvendo por expansão tem-se:
T(2k) = T(2k-1) + 1 = (T(2k-2) + 1) + 1 = (T(2k-3) + 1) + 1 + 1 = ...
... = (T(2) + 1) + 1 + ... + 1 = (T(1) + 1) + 1 + ... + 1 = 0 + 1 + ... + 1 = k
T(n) = log2 n 
T(n) = O(log2 n)
Prof. Rodrigo Freitas Silva / UFES 213
Exemplo de recorrências básicas: exemplo 2
T(n) = 2T(n/2) + n (n ≥ 2)
T(1) = 0 (n = 1)
Resolva !!!!
Prof. Rodrigo Freitas Silva / UFES 214
Exemplo de recorrências básicas: exemplo 2
T(n) = 2T(n/2) + n (n ≥ 2)
T(1) = 0 (n = 1)
Resolução: Vamos supor que n = 2k → k = log2 n
Resolvendo por expansão tem-se:
T(2k) = 2T(2k-1) + 2k = 2(2T(2k-2) + 2k-1) + 2k = 2(2(2T(2k-3) + 2k-2) + 2k-1)+ 2k = ...
... = 2(2(...(2(2T(1) + 22) + 23)+ ... )+ 2k-1 ) + 2k = (k-1) 2k + 2k = k2k
Ou simplesmente fazendo:
T(2k) = 2T(2k-1) + 2k = 2(2T(2k-2) + 2k-1) + 2k = 22T(2k-2) + 2k + 2k = 23T(2k-3) + 2k + 2k + 2k = .... = 
.... = 2i T(2k-i) + i * 2k = ... = 2kT(1) + k2k = 0 + k2k
Para chegarmos a T(1) = T(20)  k - i = 0  k = i
Prof. Rodrigo Freitas Silva / UFES 215
Exemplo de recorrências básicas: exemplo 2
T(n) = 2T(n/2) + n (n ≥ 2)
T(1) = 0 (n = 1)
Resolução: Como supomos que: n = 2k → k = log2 n
Exemplo: para k = 4:
T(2) = 2T(1) + 2 = 2 = 1* 21
T(22) = 2T(2) + 22 = 22 + 22 = 2*22
T(23) = 2T(22) + 23 = 23 + 23 + 23 = 3*23
T(24) = 2T(23) + 24 = 24 + 24 + 24 + 24 = 4*24 
T(2k) = 2T(2k) + 2k = 2k + 2k + ... + 2k + 2k = k*2k 
T(n) = n log2 n 
T(n) = O(n log2 n)
Prof. Rodrigo Freitas Silva / UFES 216
Bibliografias utilizadas
1. Aho, A. V.; Hopcroft, J. E.; Ullman, J. D.; The Design and Analysis of 
Computer Algorithms, 1ed, Ed. Addison Wesley, 1974
2. T.H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein; Algoritmos: Teoria e 
Prática, ed.2, Campus, 2002. 
3. Jayme Luiz Swarcfiter, Lilian Markenzon, Estruturas de Dados e Seus
Algoritmos, 2a edition
4. Nivio Ziviani , Projeto De Algoritmos, 2º ed. , 2004
5. Papadimitriou, C. H.; Computational Complexity. 1ed, Ed. Addison Wesley, 
1994. 
6. Garey, M. R.; Johnson, D. S.; Computers and intractability: A guide to the 
theory of NP-completeness. Ed. Freeman, 1979. 
7. Toscani, L. V.; Veloso, P. A. S.; Complexidade de Algoritmos, 2ed, Ed. 
Bookman, 2008. 
Prof. Rodrigo Freitas Silva / UFES 217