CompAlgo Aula 08 [2025] - Exercicios

Prévia do material em texto

Complexidade
de Algoritmos
2025
Prof. Gregorio Perez Peiro
Foto de Google DeepMind - Disponível para Uso Gratuito
https://www.pexels.com/pt-br/foto/abstrato-resumo-abstrair-tecnologia-17485657/
Licença de Uso
Este trabalho está licenciado sob a Licença Atribuição-
NãoComercial-CompartilhaIgual 4.0 Internacional 
Creative Commons.
Para visualizar uma cópia desta licença, visite 
http://creativecommons.org/licenses/by-nc-
sa/4.0/legalcode.pt ou mande uma carta para Creative
Commons, PO Box 1866, Mountain View, CA 94042, USA
2
Atribuição-NãoComercial-CompartilhaIgual
4.0 Internacional 
(CC BY-NC-SA 4.0)
Atribuição Você deve dar o crédito apropriado, prover um
link para a licença e indicar se mudanças foram
feitas. Você deve fazê-lo em qualquer
circunstância razoável, mas de nenhuma
maneira que sugira que o licenciante apoia você
ou o seu uso.
NãoComercial Você não pode utilizar esta obra para fins
comerciais
CompartilhaIgual Se você remixar, transformar, ou criar a partir do
material, tem de distribuir as suas contribuições
sob a mesma licença que o original.
Você tem o direito de
De acordo com os termos seguintes:
Sem restrições adicionais — Você não pode aplicar 
termos jurídicos ou medidas de caráter tecnológico 
que restrinjam legalmente outros de fazerem algo 
que a licença permita.
Compartilhar — copiar e redistribuir o material em qualquer
suporte ou formato
Adaptar — remixar, transformar, e criar a partir do material
Complexidade de Algoritmos - prof. Gregorio Perez PeiroLicença de Uso Creative Commons CC BY - NC - SA 4.0 [2025]
http://creativecommons.org/licenses/by-nc-sa/4.0/legalcode.pt
http://creativecommons.org/licenses/by-nc-sa/4.0/legalcode.pt
http://creativecommons.org/licenses/by-nc-sa/4.0/legalcode.pt
http://creativecommons.org/licenses/by-nc-sa/4.0/legalcode.pt
http://creativecommons.org/licenses/by-nc-sa/4.0/legalcode.pt
Complexidade de Algoritmos - prof. Gregorio Perez Peiro 3
Mais Exercícios ... 
❖ A complexidade pode ser analisada de 
diversos pontos de vista.
❖ Vamos fazer exercícios ... e entender 
alguns deste pontos.
8
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025]
Foto de Victor Freitas (Disponível para uso gratuito)
https://www.pexels.com/pt-br/foto/pessoa-levantando-barra-de-metal-preto-e-cinza-1092877/
Regras Gerais para Análise de Algoritmos
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 4
Regra 1: Condicional
❖ Estruturas Condicionais (𝑠𝑒 … senão)
❖ Para um comando condicional 
composto o tempo total de execução
não é nunca maior do que o tempo 
necessário para realizar o teste mais o 
maior dos tempos de execução entre os 
blocos da estrutura (𝑏1 e 𝑏2). 
➢ Vale também para as estruturas de seleção 
(𝑠𝑤𝑖𝑡𝑐ℎ… 𝑐𝑎𝑠𝑒)
𝑠𝑒 𝑒𝑛𝑡ã𝑜
;
𝑠𝑒𝑛ã𝑜
;
𝑇 = 𝑡𝑒𝑚𝑝𝑜 𝑐𝑜𝑛𝑑𝑖çã𝑜 +
𝑡𝑒𝑚𝑝𝑜 ( 𝑚𝑎𝑖𝑜𝑟 ? 𝑇(𝑏1) ∶ 𝑇(𝑏2) )
𝑂( 𝑇 𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠 )
Regras Gerais para Análise de Algoritmos
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 5
Regra 2: Laços
❖ Estruturas de Repetição (𝑓𝑜𝑟, 𝑤ℎ𝑖𝑙𝑒)
❖ O tempo de execução para um laço é, 
no máximo, o tempo de execução dos 
comandos internos do laço (incluindo 
os testes) vezes o número de iterações.
➢ Observação. Se o bloco interno contiver 
outras estruturas (𝑖𝑓, 𝑓𝑜𝑟, 𝑒𝑡𝑐.) , estas devem 
ser consideradas.
𝑓𝑜𝑟 ( 𝑖 = 1; 𝑖 ;
𝑇 = 𝑛 ∗ 𝑡𝑒𝑚𝑝𝑜( 𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠 )
❖ Para um conjunto de instruções genéricos
𝑂( 𝑛 )
Regras Gerais para Análise de Algoritmos
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 6
Regra 3: Laços Aninhados
❖ Estruturas de Repetição (𝑓𝑜𝑟, 𝑤ℎ𝑖𝑙𝑒)
❖ Analise laços aninhados de dentro pra 
fora. 
❖ O tempo de execução total de um 
comando dentro de um grupo de laços 
aninhados é o tempo de execução do 
comando multiplicado pelo produto do 
tamanho de todos os laços. 
𝑓𝑜𝑟 ( 𝑖 = 1; 𝑖 ;
𝑇 = 𝑛 ∗ 𝑛 ∗ 𝑡𝑒𝑚𝑝𝑜(𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠)
❖ Para um conjunto de instruções genéricos
𝑂( 𝑛2 )
Regras Gerais para Análise de Algoritmos
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 7
Regra 4: Comandos Consecutivos
❖ Comandos consecutivos simplesmente 
são adicionados. 
❖ Na prática significa que o tempo total 
de execução é igual ao comando com 
maior tempo.
❖ No exemplo ao lado:
𝑂(𝑛2)
𝑓𝑜𝑟 ( 𝑘 = 1; 𝑘 ;
𝑓𝑜𝑟 ( 𝑖 = 1; 𝑖 ;
𝑇 = 𝑚 ∗ 𝑡𝑒𝑚𝑝𝑜 𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠 1 +
𝑛 ∗ 𝑛 ∗ 𝑡𝑒𝑚𝑝𝑜(𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠 2)
𝑂(𝑛)
𝑂(𝑛2)
Complexidade de Algoritmos - prof. Gregorio Perez Peiro 8
Agora, sim ... Vamos trabalhar
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025]
Foto de Andrea Piacquadio Disponível para uso gratuito)
https://www.pexels.com/pt-br/foto/mulher-encostada-na-mesa-3767411/
Complexidade de Algoritmos
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 9
❖ Considere o procedimento ao 
lado, implementado em uma 
linguagem qualquer...
❖ Determine a complexidade do 
procedimento.
1. 𝑣𝑜𝑖𝑑 𝑝𝑟𝑜𝑐𝑒𝑑𝑖𝑚𝑒𝑛𝑡𝑜 ( 𝑖𝑛𝑡 𝑛) {
2. 𝑖𝑛𝑡 𝑖, 𝑗, 𝑘, 𝑥 = 0;
3. 𝑓𝑜𝑟 ( 𝑖 = 1; 𝑖de Algoritmos
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 14
❖ Complexidade do procedimento.
❖ Instruções básicas são 
desconsideradas
➢ 𝑂 1
1. 𝑣𝑜𝑖𝑑 𝑝𝑟𝑜𝑐𝑒𝑑𝑖𝑚𝑒𝑛𝑡𝑜 ( 𝑖𝑛𝑡 𝑛) {
2. 𝑖𝑛𝑡 𝑖, 𝑗, 𝑥 = 0, 𝑦 = 0;
3. 𝑓𝑜𝑟 ( 𝑖 = 1; 𝑖 103000
6
106
6 . 106
1012
≈ 1014
? ?
9
109
9 . 109
1018
≈ 1020
? ? ?
Comparação de Funções
𝑛 = 101 𝑛 = 102 𝑛 = 103 𝑛 = 104 𝑛 = 106 𝑛 = 109
𝑛 = 10 𝑛 = 100 𝑛 = 1 000 𝑛 = 10 000 (𝑚𝑖𝑙ℎã𝑜) (𝑏𝑖𝑙ℎã𝑜)
log 𝑛
𝑛
𝑛 log 𝑛
𝑛2
100𝑛2 + 15𝑛
2𝑛
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 23
1
10
10
100
10 150
1 024
2
100
200
10 000
≈ 1,01 . 106
≈ 1,26 . 1030
3
1000
3000
106
≈ 108
≈ 10301
4
10 000
4 . 104
108
≈ 1010
> 103000
6
106
6 . 106
1012
≈ 1014
? ?
9
109
9 . 109
1018
≈ 1020
? ? ?
Tempo (1 operação por seg)
1 𝑎𝑛𝑜  𝑡 = 365𝑥24𝑥60𝑥60
1 𝑎𝑛𝑜  𝑡 ≈ 3𝑥107 𝑠𝑒𝑔
1 𝑠é𝑐𝑢𝑙𝑜  𝑡 ≈ 3𝑥109 𝑠𝑒𝑔
1 𝑚𝑖𝑙ê𝑛𝑖𝑜  𝑡 ≈ 3𝑥1010 𝑠𝑒𝑔
Problema 1 
❖ Considere dois computadores 𝐶1 e 𝐶2
➢ 𝐶1 : executa 107 instruções por segundo (10 𝑚𝑖𝑙ℎõ𝑒𝑠 )
➢ 𝐶2 : executa 109 instruções por segundo (1 𝑏𝑖𝑙ℎã𝑜 )
❖ Considere dois Algoritmos de Ordenação 𝐴 e 𝐵
➢ 𝐴 : exige 2𝑛2 instruções para ordenar 𝑛 números
➢ 𝐵: exige 50 𝑛 log 𝑛 instruções para ordenar 𝑛 números
❖ Quanto tempo 𝐶1 e 𝐶2 gastam para ordenar um 
milhão de números (𝑛 = 106) usando os 
algoritmos 𝐴 e 𝐵 ?
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 24
C
o
m
 a Licen
ça d
a U
n
sp
lash
+ -
h
ttp
s://u
n
sp
lash
.co
m
/p
t-b
r/p
lu
s/licen
%
C
3
%
A
7
a
h
ttp
s://u
n
sp
lash
.co
m
/p
t-b
r/fo
to
grafias/u
m
-sin
al-d
e
-n
eo
n
-q
u
e-d
iz-h
o
u
sto
n
-tem
o
s-u
m
-fo
gu
ete
-so
b
re
-ele-YFtze
0r3ljs
Problema 1
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 25
Computadores Algoritmos
❖ 𝐶1  107 instruções/s
❖ 𝐶2  109 instruções/s
❖ 𝐴  2𝑛2 instruções
❖ 𝐵  50 𝑛 log 𝑛 instruções
❖ Algoritmo 𝐴 (𝑛 = 106)  2 𝑛2 = 2 𝑥 (106)2 = 2 𝑥 1012
❖ Computador 𝐶1 : 𝑡𝑒𝑚𝑝𝑜 =
2𝑛2
107
⇒
2𝑥1012
107
⇒ 𝑡𝑒𝑚𝑝𝑜 = 2𝑥105 (≳ 55 ℎ𝑜𝑟𝑎𝑠)
❖ Computador 𝐶2 : 𝑡𝑒𝑚𝑝𝑜 =
2𝑛2
109
⇒
2𝑥1012
109
⇒ 𝑡𝑒𝑚𝑝𝑜 = 2𝑥103 (~0,5 ℎ𝑜𝑟𝑎𝑠)
Problema 1
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 26
Computadores Algoritmos
❖ 𝐶1  107 instruções/s
❖ 𝐶2  109 instruções/s
❖ 𝐴  2𝑛2 instruções
❖ 𝐵  50 𝑛 log 𝑛 instruções
❖ Algoritmo 𝐵 (𝑛 = 106)  50 𝑛 log 𝑛 = 50 𝑥 106 𝑥 log 106 = 3 𝑥 108
❖ Computador 𝐶1 : 𝑡𝑒𝑚𝑝𝑜 =
50 𝑛 log 𝑛
107
⇒
3𝑥108
107
⇒ 𝑡𝑒𝑚𝑝𝑜 = 30 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠
❖ Computador 𝐶2 : 𝑡𝑒𝑚𝑝𝑜 =
50 𝑛 log 𝑛
109
⇒
3𝑥108
109
⇒ 𝑡𝑒𝑚𝑝𝑜 = 0,3 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠
Problema 1
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 27
𝑛 = 106 (um milhão) 𝑛 = 107 (10 milhões)
Algoritmos
Computador 𝐶1
107 instruções/s
Computador 𝐶2
109 instruções/s
𝐴
2𝑛2
2 𝑥 105
(≳ 55 ℎ𝑜𝑟𝑎𝑠)
2 𝑥 103
(~0,5 ℎ𝑜𝑟𝑎𝑠)
𝐵
50 𝑛 log 𝑛
30 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠 0,3 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠
Algoritmos
Computador 𝐶1
107 instruções/s
Computador 𝐶2
109 instruções/s𝐴
2𝑛2
2 𝑥 107
(≳ 231 𝑑𝑖𝑎𝑠)
2 𝑥 105
(~2,3 𝑑𝑖𝑎𝑠)
𝐵
50 𝑛 log 𝑛
350 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠
(≲ 6 𝑚𝑖𝑛)
3,5 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠
Exercício – Perguntas 
❖ Considere dois programas 𝐴 e 𝐵 com tempos de 
execução 𝑇𝐴 𝑛 = 100𝑛2 e 𝑇𝐵 𝑛 = 5𝑛3, 
respectivamente. Pergunta-se:
1. Qual é o mais eficiente para pequenos 
conjuntos de dados?
2. Qual é o mais eficiente para grandes 
conjuntos de dados?
3. Qual a complexidade dos dois programas?
4. Qual é preferido para um problema 
desconhecido (ou genérico)?
TD
O
 Stu
d
io
 -
C
o
m
 a Licen
ça d
a U
n
sp
lash
+ -
h
ttp
s://u
n
sp
lash
.co
m
/p
t-b
r/p
lu
s/licen
%
C
3
%
A
7
a
h
ttp
s://u
n
sp
lash
.co
m
/p
t-b
r/fo
to
grafias/u
m
-gran
d
e
-n
u
m
ero
-d
e
-p
o
n
to
s-d
e-in
terro
gacao
-em
-u
m
a-p
ared
e-gQ
yjM
_1
1
D
o
g
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 28
Exercício – Perguntas : Análise 
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 29
❖ Programa 𝐴  𝑇𝐴 𝑛 = 100𝑛2
❖ Programa 𝐵  𝑇𝐵 𝑛 = 5𝑛3
❖ Precisamos avaliar os programas para 
quaisquer quantidades de entrada de 
dados.
❖ Novamente, temos duas opções:
❖ Matematicamente
➢ Tabela de Dados
➢ Comparamos vários valores 𝑛 de entrada
❖ Graficamente / Comportamento
➢ Comportamento das Curvas
➢ Verificamos o(s) ponto(s) de intersecção e 
avaliamos o comportamento das curvas 
Análise Matemática
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 30
❖ Programa 𝐴  𝑇𝐴 𝑛 = 100𝑛2
❖ Programa 𝐵  𝑇𝐵 𝑛 = 5𝑛3
❖ As duas curvas possuem 
comportamento exponencial.
➢ Podemos facilmente encontrar o(s) ponto(s) 
de intersecção onde as curvas trocam de 
dominância
Ponto de Mudança de Dominância
Os dois componentes da expressão tem ‘peso’ 
equivalente (são iguais)
𝑓𝐴 = 100𝑛2 𝑓𝐵 = 5𝑛3
100𝑛2 = 5𝑛3 100 = 5𝑛  𝑛 = 20
Podemos usar este valor para construir uma 
tabela de possíveis entradas de dados ...
Análise Matemática
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 31
❖ Programa 𝐴  𝑇𝐴 𝑛 = 100𝑛2
❖ Programa 𝐵  𝑇𝐵 𝑛 = 5𝑛3
Ponto de Mudança de Dominância
Os dois componentes da expressão tem ‘peso’ 
equivalente (são iguais)
𝑓𝐴 = 100𝑛2 𝑓𝐵 = 5𝑛3
100𝑛2 = 5𝑛3 100 = 5𝑛  𝑛 = 20
Podemos usar este valor para construir uma 
tabela de possíveis entradas de dados ...
𝒏
Tempo (unidades, %)
5
10
20
30
50
𝑇𝐴 𝑛 = 100 𝑛2 𝑇𝐵 𝑛 = 5 𝑛3
2 500 80% 625 20%
10 000 66,67% 5 000 33,33%
40 000 50% 40 000 50%
90 000 40% 100 000 60%
300 000 28,57% 600 000 71,43%
Análise Matemática
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 32
❖ Programa 𝐴  𝑇𝐴 𝑛 = 100𝑛2
❖ Programa 𝐵  𝑇𝐵 𝑛 = 5𝑛3
Eficiência
1. Para pequenos valores 𝑛 de entrada de dados
➢ (∀𝑛 20): Programa 𝐴 é mais eficiente𝒏
Tempo (unidades, %)
5
10
20
30
50
𝑇𝐴 𝑛 = 100 𝑛2 𝑇𝐵 𝑛 = 5 𝑛3
2 500 80% 625 20%
10 000 66,67% 5 000 33,33%
40 000 50% 40 000 50%
90 000 40% 100 000 60%
300 000 28,57% 600 000 71,43%
Complexidade
3. a. Programa 𝐴: 𝑂 𝑛2
b. Programa 𝐵: 𝑂 𝑛3
Análise Matemática
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 33
❖ Programa 𝐴  𝑇𝐴 𝑛 = 100𝑛2
❖ Programa 𝐵  𝑇𝐵 𝑛 = 5𝑛3
Eficiência
1. Para pequenos valores 𝑛 de entrada de dados
➢ (∀𝑛 20): Programa 𝐴 é mais eficiente
Complexidade
3. a. Programa 𝐴: 𝑂 𝑛2
b. Programa 𝐵: 𝑂 𝑛3
𝒏
Tempo (unidades, %)
5
10
20
30
50
𝑇𝐴 𝑛 = 100 𝑛2 𝑇𝐵 𝑛 = 5 𝑛3
2 500 80% 625 20%
10 000 66,67% 5 000 33,33%
40 000 50% 40 000 50%
90 000 40% 100 000 60%
300 000 28,57% 600 000 71,43%
4. A Análise Assintótica (conjunto de dados 
grande) indica o Programa 𝐴 como mais 
eficiente. Para um programa desconhecido, 
avaliamos o comportamento assintótico, 
portanto o Programa 𝐴 é preferido.
Análise Gráfica / Comportamento
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 34
❖ Programa 𝐴  𝑇𝐴 𝑛 = 100𝑛2
❖ Programa 𝐵  𝑇𝐵 𝑛 = 5𝑛3
❖ As duas curvas possuem comportamento 
exponencial, então podemos facilmente 
representar ambas no mesmo gráfico.
❖ A diferença entre a Análise Gráfica Exata
e a Análise do Comportamento está na 
consideração das constantes...
𝑓𝐴 = 100𝑛2
𝑓𝐵 = 5𝑛3
𝑛0
Análise Gráfica / Comportamento
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 35
❖ Programa 𝐴  𝑇𝐴 𝑛 = 100𝑛2
❖ Programa 𝐵  𝑇𝐵 𝑛 = 5𝑛3
𝑓𝐴 = 100𝑛2
𝑓𝐵 = 5𝑛3
𝑛0
𝑛0
Análise Gráfica / Comportamento
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 36
❖ Programa 𝐴  𝑇𝐴 𝑛 = 100𝑛2
❖ Programa 𝐵  𝑇𝐵 𝑛 = 5𝑛3
Eficiência
1. Para pequenos valores 𝑛 de entrada de dados
➢ (∀𝑛 20): Programa 𝐴 é mais eficiente
𝑛0
𝑓𝐴 = 100𝑛2
𝑓𝐵 = 5𝑛3
Complexidade
3. a. Programa 𝐴: 𝑂 𝑛2
b. Programa 𝐵: 𝑂 𝑛3
Análise Gráfica / Comportamento
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 37
❖ Programa 𝐴  𝑇𝐴 𝑛 = 100𝑛2
❖ Programa 𝐵  𝑇𝐵 𝑛 = 5𝑛3
𝑓𝐴 = 100𝑛2
𝑓𝐵 = 5𝑛3
𝑛0
4. Quanto menor o valor de n, menor a diferença 
entre os programas. Quando n aumenta, a 
diferença de eficiência se torna significativa 
(muito grande)... Assim, a Análise Assintótica
(conjunto de dados grande) indica o Programa 
𝐴 como mais eficiente. 
Para um programa desconhecido, avaliamos o 
comportamento assintótico, portanto o 
Programa 𝐴 é preferido.
Problema 2 
❖ Um algoritmo tem complexidade 2𝑛2. Em um 
computador 𝐴, em um tempo 𝑡, o algoritmo 
resolve um problema de tamanho 𝑛 = 25. 
❖ Imagine agora que você tem disponível um 
computador 𝐵, 100 vezes mais rápido. 
❖ Qual é o tamanho máximo do problema que o 
mesmo algoritmo resolve no mesmo tempo 𝑡?
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 38
U
so
 G
ratu
ito
 so
b
 a Licen
ça d
a U
n
sp
lash
+ -
h
ttp
s://u
n
sp
lash
.co
m
/p
t-b
r/p
lu
s/licen
%
C
3
%
A
7
a
h
ttp
s://u
n
sp
lash
.co
m
/p
t-b
r/fo
to
grafias/azu
l-laran
ja-ve
rd
e-e-b
rin
q
u
ed
o
-p
lastico
-am
arelo
-ZxR
H
tP
acw
U
Y
Problema 2 
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 39
❖ Um algoritmo tem complexidade 2𝑛2. 
❖ Computador 𝐴
❖ Quantidade de instruções:
2 𝑥 (25)2
❖ Computador 𝐵 (100 vezes mais rápido)
❖ Quantidade de instruções:
100 𝑥 2 𝑥 (25)2
❖ Tamanho do problema resolvido em 𝐵, 
(no mesmo tempo 𝑡):
❖ 2 𝑛2 = 100 𝑥 2 𝑛2
❖ 2 𝑛2 = 100 𝑥 2 𝑥 (25)2
❖ 𝑛2 = 100 𝑥 (25)2
❖ 𝑛 = 10 𝑥 25
❖ 𝑛 = 250
“complexidade” Instruções 
executadas
Exercício – Perguntas 
❖ Considere dois programas 𝐴 e 𝐵 com 
complexidades 𝐴 = 8𝑛2 e 𝐵 = 𝑛3.
❖ Pergunta-se:
1. Qual é o mais eficiente?
2. Qual é o maior valor de 𝑛 para o qual o 
algoritmo 𝐵 é mais eficiente do que o 
algoritmo 𝐴 ?
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 40
Foto de Leeloo The First no Pexels (disponível para Uso Gratuito)
https://www.pexels.com/pt-br/foto/pontos-de-interrogacao-na-superficie-
marrom-5428835/
Análise Matemática
Licença de Uso CreativeCommons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 41
❖ Programa 𝐴  𝑇𝐴 𝑛 = 8𝑛2
❖ Programa 𝐵  𝑇𝐵 𝑛 = 𝑛3
❖ As duas curvas possuem 
comportamento exponencial.
➢ Podemos determinar o(s) ponto(s) de 
intersecção onde as curvas trocam de 
dominância
Ponto de Mudança de Dominância
Os dois componentes da expressão tem 
‘peso’ equivalente (são iguais)
𝑓𝐴 = 8𝑛2 𝑓𝐵 = 𝑛3
8𝑛2 = 𝑛3  8 = 𝑛  𝑛 = 8
Análise Matemática
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 42
❖ Programa 𝐴  𝑇𝐴 𝑛 = 8𝑛2
❖ Programa 𝐵  𝑇𝐵 𝑛 = 𝑛3
Eficiência
1. Para ∀𝑛 8 de entrada de dados, o 
Programa 𝐴 é mais eficiente
𝒏
Tempo (unidades, %)
2
4
8
12
16
𝑇𝐴 𝑛 = 8𝑛2 𝑇𝐵 𝑛 = 𝑛3
32 80% 8 20%
128 66,67% 64 33,33%
512 50% 512 50%
1152 40% 1728 60%
2048 33,33% 4096 66,67%
Tabela meramente ilustrativa
WASH YOUR 
HANDS
Licença de Uso Creative Commons CC BY - NC - SA 4.0 [2025] Complexidade de Algoritmos - prof. Gregorio Perez Peiro 43
	Slide 1: Complexidade de Algoritmos
	Slide 2: Licença de Uso
	Slide 3: Mais Exercícios ... 
	Slide 4: Regras Gerais para Análise de Algoritmos
	Slide 5: Regras Gerais para Análise de Algoritmos
	Slide 6: Regras Gerais para Análise de Algoritmos
	Slide 7: Regras Gerais para Análise de Algoritmos
	Slide 8: Agora, sim ... Vamos trabalhar
	Slide 9: Complexidade de Algoritmos
	Slide 10: Complexidade de Algoritmos
	Slide 11: Complexidade de Algoritmos
	Slide 12: Complexidade de Algoritmos
	Slide 13: Complexidade de Algoritmos
	Slide 14: Complexidade de Algoritmos
	Slide 15: Complexidade de Algoritmos
	Slide 16: Complexidade de Algoritmos
	Slide 17: Complexidade de Algoritmos
	Slide 18: Comparação de Funções
	Slide 19: Comparação de Funções
	Slide 20: Comparação de Funções
	Slide 21: Comparação de Funções
	Slide 22: Comparação de Funções
	Slide 23: Comparação de Funções
	Slide 24: Problema 1 
	Slide 25: Problema 1
	Slide 26: Problema 1
	Slide 27: Problema 1
	Slide 28: Exercício – Perguntas 
	Slide 29: Exercício – Perguntas : Análise 
	Slide 30: Análise Matemática
	Slide 31: Análise Matemática
	Slide 32: Análise Matemática
	Slide 33: Análise Matemática
	Slide 34: Análise Gráfica / Comportamento
	Slide 35: Análise Gráfica / Comportamento
	Slide 36: Análise Gráfica / Comportamento
	Slide 37: Análise Gráfica / Comportamento
	Slide 38: Problema 2 
	Slide 39: Problema 2 
	Slide 40: Exercício – Perguntas 
	Slide 41: Análise Matemática
	Slide 42: Análise Matemática
	Slide 43