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 uma