Unidade 2 - Análise de algoritmos

Prévia do material em texto

08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 1/28
ANÁLISE DEANÁLISE DE
ALGORITMOS ALGORITMOS 
UNIDADE 2 –UNIDADE 2 –
COMPLEXIDADE DECOMPLEXIDADE DE
ALGORITMOS EALGORITMOS E
RECORRÊNCIAS RECORRÊNCIAS 
Autor: Thiago Nascimento Rodrigues Autor: Thiago Nascimento Rodrigues 
Revisor: Bruno Carreira Coutinho Silva Revisor: Bruno Carreira Coutinho Silva 
INICIAR
Introdução
Caro(a) estudante, 
Várias técnicas podem ser empregadas em uma análise de complexidade de algoritmo.
Um objetivo comum entre elas é a descrição de uma métrica, mais precisa possível, que
possibilite uma caracterização formal do desempenho de diferentes estratégias
empregadas na solução de um domínio de problema. A definição do comportamento
assintótico de um algoritmo é a mais explorada para esse fim na ciência da computação. 
Nesta unidade, vamos conhecer uma notação usada para retratar a eficiência de um
algoritmo tendo como base o número de operações executadas por ele e o quanto esse
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 2/28
2.1 Ordem assintótica: notação Theta
Os modelos de análise de eficiência se concentram em avaliar a ordem de crescimento
da contagem do número de operações elementares executadas por um algoritmo.
Conforme indicado por Skienka (2008), para fins de comparação e classificação dessas
ordens de crescimento, cientistas da computação propuseram três notações: O (grande
O ou apenas O), Ω (grande ômega ou apenas ômega) e Θ (grande theta ou apenas
theta). Conforme apresentado na unidade 1, duas funções f e g de limite assintótico
estão relacionadas pelas notações O e Ω #PraCegoVer : ó e ômega , se elas atendem
as seguintes definições: 
Se f(n) = O(gn) #PraCegoVer : éfe de êne é igual a ó de gê êne , então, c · g(n)
#PraCegoVer : cê vezes gê de êne é um limite superior para f(n) #PraCegoVer :
éfe de êne . Isso significa que existem constantes positivas c e n 0 #PraCegoVer :
cê e êne índice zero tal que f(n) ≤ cg(n) #PraCegoVer : éfe de êne é menor ou
igual ao produto de cê gê de êne para qualquer n ≥ n 0 #PraCegoVer : êne maior
ou igual a êne índice zero .
Se f(n) = Ω(gn) #PraCegoVer : éfe de êne é igual a ômega de gê êne , então, c ·
g(n) #PraCegoVer : cê vezes gê de êne é um limite inferior para f(n)
#PraCegoVer : éfe de êne . Isso significa que existem constantes positivas c e n 0
#PraCegoVer : cê e êne índice zero tal que f(n) ≥ cg(n) #PraCegoVer : éfe de
êne é maior ou igual ao produto de cê e gê de êne para qualquer n ≥ n 0
#PraCegoVer : êne maior ou igual a êne índice zero .
Considerando as duas primeiras notações, se for possível mostrar que o tempo de
execução de uma função f(n) #PraCegoVer : éfe de êne é tanto O (g(n)) #PraCegoVer :
ó de gê de êne como Ω( g(n)) #PraCegoVer : ômega de gê de êne , então, é natural
número é influenciado pelo tamanho do problema a ser resolvido. Exploraremos também
uma nova técnica de análise de complexidade fundamentada no conceito de
recursividade. Além disso, teremos a oportunidade de entender como essa técnica pode
ser aplicada para a obtenção da ordem assintótica de algoritmos. 
Bons estudos! 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 3/28
concluir que #PraCegoVer g(n) : gê de êne seja um delimitador justo para f(n)
#PraCegoVer : éfe de êne . Nesse caso, f(n) #PraCegoVer : éfe de êne cresce na
mesma proporção que g(n) #PraCegoVer : gê de êne e dentro dos limites superiores e
inferiores definidos por fatores constantes. A título de exemplo, essa é a conclusão
extraída do fato de f(n) = pn² + qn + r #PraCegoVer : éfe de êne é igual a pê vezes êne
ao quadrado mais quê vezes êne mais érre ser tanto O (n²) como Ω( n² ) #PraCegoVer
: ó de êne ao quadrado como ômega de êne ao quadrado. 
VOCÊ SABIA?
O limite assintótico superior provido pela notação O pode ou não ser um limite
assintótico justo. O limite 2 n² = O (n²) #PraCegoVer : dois êne ao quadrado é
igual a ó de êne ao quadrado é assintoticamente justo, mas o limite 2 n = (n2)
#PraCegoVer : dois êne é igual a êne ao quadrado não é. Para essa situação,
pode-se usar a notação o (do inglês, little-oh , ou pequeno o , em português) para
denotar um limite superior que não é assintoticamente justo. Formalmente, o(g(n))
#PraCegoVer : é de gê de êne é definido como um conjunto : 
• o(g(n)) = { f(n) : para qualquer constante positiva c > 0, #PraCegoVer : ó de gê
de êne é igual a éfe de êne para qualquer constante positiva de cê maior que
zero existe uma constante n 0 > 0 #PraCegoVer : êne índice zero maior que
zero tal que 0 ≤ f(n) ≤ cg(n) para todo n ≥ n 0}. #PraCegoVer : éfe de êne é
maior ou igual a zero e menor ou igual ao produto de uma cê com gê de êne
para todo êne maior ou igual a êne índice zero . 
Por exemplo, 2 n = o( n ²), mas 2 n ² ≠ o( n ²) #PraCegoVer : dois êne é igual a
pequeno ó de êne ao quadrado , mas dois êne ao quadrado é diferente de pequeno
ó de êne ao quadrado. 
 
Para cenários como o exemplo acima, a notação Theta (Θ) é utilizada para expressar
que uma função f(n) #PraCegoVer : éfe de êne é tanto O(g(n)) #PraCegoVer : ó de gê
de êne quanto Ω ( g(n)) #PraCegoVer : ômega de gê de êne. De modo sucinto, f(n) =
Θ(g(n)) #PraCegoVer : theta de gê de êne e g(n) #PraCegoVer : gê de êne é dita ser
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 4/28
um limite assintótico firme ou justo para f(n) #PraCegoVer : éfe de êne. Considerando a
função f(n) = pn² + qn + r #PraCegoVer : éfe de êne é igual a pê vezes êne ao
quadrado mais quê vezes êne mais érre , pode-se afirmar que f(n) = Θ (n2)
#PraCegoVer : éfe de êne é igual a theta de êne ao quadrado. Mais formalmente: 
se f(n) = Θ(g(n)) #PraCegoVer: éfe de êne é igual a theta de gê de êne , então,
existem constantes positivas 
c , c e n #PraCegoVer: cê índice um, cê índice dois e êne índice zero tais
que c · g(n) ≤ f(n) ≤ c · g(n) #PraCegoVer: o produto de cê índice um por gê
de êne é menor ou igual a éfe de êne , que por sua vez é menor ou igual ao
produto de cê índice dois por gê de êne para todo n ≥ n 0 #PraCegoVer: êne
maior ou igual a êne índice zero , ou seja, g(n) #PraCegoVer: gê de êne é um
limite superior e inferior para f(n) #PraCegoVer: éfe de êne .
Gráfico 1 – Exemplos de gráficos das notações Θ, O e Ω #PraCegoVer: theta, ó e
ômega
Fonte: CORMEN et al., 2009, p. 45. (Adaptado). 
O Gráfico 1 apresenta uma descrição gráfica das notações assintóticas O, Ω e Θ
#PraCegoVer : ó, ômega e theta . Em cada gráfico, o valor de n #PraCegoVer : êne
índice zero apresentado corresponde ao menor valor possível, ou seja, qualquer valor
maior também manteria a relação entre as funções. No gráfico (a), a notação Θ
#PraCegoVer : theta limita a função f(n) #PraCegoVer : éfe de êne dentro de dois
fatores constantes. Por isso, é indicado que f(n) = Θ (g(n)) #PraCegoVer : éfe de êne é
igual a theta de gê de êne se existirem constantes positivas c , c e n #PraCegoVer
1 2 0 
1 2 
0 
1 2 0 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 5/28
: cê índice um, cê índice dois e êne índice zero tais que, a partir do lado direito de n 
#PraCegoVer : êne índice zero , o valor de f(n) #PraCegoVer : éfe de êne sempre
estará entre c g(n) e c g(n) #PraCegoVer : cê índice um de gê de êne e cê índice
dois de gê de êne (incluindo os próprios limites). A notação O do gráfico (b) estabelece
um limite superior para a função f(n) #PraCegoVer : éfe de êne dentro de um fator
constante. Então, pode-se afirmar que f(n) = O (g(n)) #PraCegoVer : éfe de êne é iguala ó de gê de êne se existirem constantes positivas n0 #PraCegoVer : êne índice zero e
c tais que, para toda região à direita de n #PraCegoVer : êne índice zero , o valor de
f(n) #PraCegoVer : éfe de êne sempre será inferior a cg(n) #PraCegoVer : cê gê de êne
. E o gráfico (c) apresenta um limite inferior para f(n) #PraCegoVer : éfe de êne de
acordo com um fator constante. É possível afirmar que f(n) = Ω (g(n)) #PraCegoVer : éfe
de êne é igual a ômega de gê de êne se existirem constantes positivas n 
#PraCegoVer : êne índice zero e c tais que, para toda região à direita de n 
#PraCegoVer : êne índice zero , o valor de f(n) #PraCegoVer : éfe de êne sempre será
maior que cg(n) #PraCegoVer : cê gê de êne . 
VOCÊ SABIA?
A análise assintótica, em especial a notação Θ #PraCegoVer : theta , é uma
ferramenta fundamental para a escolha de um algoritmo para um dado problema.
No entanto, cabe considerar que essa análise “esconde” fatores assintoticamente
irrelevantes, mas que em alguns casos merecem ser considerados. Por exemplo,
um algoritmo com tempo de execução da ordem de 10¹ºº é Θ(n) #PraCegoVer :
dez elevado a cem é theta de êne , ou seja, é assintoticamente melhor que
outro com tempo 10 nlog(n) #PraCegoVer : dez êne log de êne . Contudo, 10¹ºº
#PraCegoVer : dez elevado a cem é o número estimado por alguns astrônomos
como limite superior para a quantidade de átomos existentes no universo
observável (HELMENSTINE, 2019). 
Muitas propriedades relacionais que podem ser observadas nos números reais podem
ser igualmente aplicadas nas comparações assintóticas. Considerando as funções f(n)
#PraCegoVer : éfe de êne e g(n) #PraCegoVer : gê de êne assintoticamente positivas,
as seguintes propriedades de transitividade, reflexividade e simetria são válidas.
0
1 2 
0 
0
0
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 6/28
Juntamente com essas, outra relações complementares também são válidas com a
notação Θ #PraCegoVer : theta conforme listado a seguir: 
f(n) = Θ(g(n)) e g(n) = Θ(h(n)) → f(n) = Θ(h(n)) ( Transitividade ) #PraCegoVer :
éfe de êne é igual a theta de gê de êne e gê de êne é igual a theta de agá de
êne resultando em éfe de êne igual a theta de agá de êne
f(n) = Θ(f(n)) (Reflexividade) #PraCegoVer: éfe de êne é igual a theta de éfe de
êne
f(n) = Θ(g(n)) ↔ g(n) = Θ(f(n)) (Simetria) #PraCegoVer: éfe de êne é igual theta
de gê de êne que é que corresponde a gê de êne igual a theta de éfe de êne
Θ(f(n)) + Θ(g(n)) = Θ(max(f(n), g(n))) #PraCegoVer: theta de éfe de êne mais
tenta de gê de êne igual a theta máximo de éfe de êne, gê de êne
Θ(c · f(n)) = Θ(f(n)) #PraCegoVer: theta de cê vezes éfe de êne é igual a theta de
éfe de êne
Θ(f(n)) · Θ(g(n)) = Θ(f(n) · g(n)) #PraCegoVer: theta de éfe de êne vezes theta de
gê de êne é igual a theta de éfe de êne vezes gê de êne
Para exemplificar o uso da notação Theta, considere a afirmação de que 4 n + 1 = Θ(n)
#PraCegoVer: quatro êne mais um é igual a theta de êne. Por definição, para validar
essa igualdade é necessário demonstrar que existem duas constantes positivas c e c 
#PraCegoVer: cê índice um e cê índice dois e um valor inicial positivo n 
#PraCegoVer : êne índice zero de modo que para todos os valores n ≥ n0 #PraCegoVer
: êne maior ou igual a êne de zero , é verdadeira a desigualdade c n ≤ 4 n + 1 ≤ c n
#PraCegoVer : o produto de cê índice um por êne é menor ou igual a quatro êne
mais um, que por sua vez é menor ou igual ao produto de cê índice dois por êne .
Para isso, o primeiro passo é escolher valores para as constantes c e c #PraCegoVer
: cê índice um e cê índice dois . Nesse caso, vamos considerar c = 4 e c = 5
#PraCegoVer : o produto de cê índice um por êne é igual a quatro e o produto de cê
índice dois por êne é igual a cinco . Observe os resultados dessas desigualdades para
alguns valores iniciais de n , conforme apresentado a seguir: 
n = 1: 4n = 4 < 5 = 4n + 1 = 5n = 5 #PraCegoVer: n é igual a um, sendo que
quatro n é igual a quatro menor que cinco igual a quatro n mais um igual a
cinco n igual a cinco.
1 2
0
1 2 
1 2 
1 2 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 7/28
n = 2: 4n = 8 < 9 = 4n + 1 < 5n = 10 #PraCegoVer: n é igual a dois, sendo que
quatro n é igual a doze menor que treze igual a quatro n mais um menor que
cinco n igual a quinze.
n = 3: 4n = 12 < 13 = 4n + 1 < 5n = 15 #PraCegoVer: n é igual a três, sendo que
quatro n é igual a doze menor que treze igual a quaro n mais um menor cinco
n igual a quinze.
n = 4: 4n = 16 < 17 = 4n + 1 < 5n = 20 #PraCegoVer: n é igual a quatro, sendo
que quatro n é igual a dezesseis menor que 17 igual a quatro n mais um menor
que cinco n igual a vinte.
n = 5: 4n = 20 < 21 = 4n + 1 < 5n = 25 #PraCegoVer: n é igual a cinco, sendo que
quatro n é igual a vinte menor que vinte e um igual a quatro n mais um menor
que cinco n igual a vinte e cinco.
VAMOS PRATICAR? 
Para consolidar o entendimento da notação theta (Θ), vamos avaliar se a
relação f(n) = 2 = Θ(2 ) #PraCegoVer: éfe de êne é igual a dois
elevado a êne mais um , que por sua vez é igual a theta de dois elevado a
êne é verdadeira. Boa parte das relações envolvendo a notação Theta podem
ser verificadas fazendo uso de sua definição. Nesse caso, vamos conferir se
f(n) = O(2 ) e f(n) = Ω(2 ) #PraCegoVer: éfe de êne é igual a ó de dois
elevado a êne e éfe de êne é igual a ômega de dois elevado a êne . 
f(n) = 2 = Θ(2 ) #PraCegoVer : éfe de êne é igual a dois elevado a
êne mais um, que por sua vez é igual a theta de dois elevado a êne é
verdadeira. Boa parte das relações envolvendo a notação Theta podem
ser verificadas fazendo uso de sua definição. Nesse caso, vamos conferir
se f(n) = O(2 ) e f(n) = Ω(2 ) #PraCegoVer : éfe de êne é igual a ó de
dois elevado a êne e éfe de êne é igual a ômega de dois elevado a
êne .
n + 1 n 
n n 
n+1 n 
n n 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 8/28
f(n) = O(2 ) #PraCegoVer : éfe de êne é igual a ó de dois elevado a
êne ? Essa igualdade é verdadeira se existir uma constante c tal que,
para todo n suficientemente grande, f(n) ≤ cg(n) #PraCegoVer : éfe de
êne é menor ou igual a cê gê de êne . Observando que 2 = 2 · 2 
#PraCegoVer : dois elevado a êne mais um é igual ao produto de dois
vezes dois elevado a êne , temos que 2 · 2 ≤ c · 2 #PraCegoVer : o
produto de dois vezes dois elevado a êne é menor ou igual ao
produto de uma constante positiva cê com dois elevado a êne para
qualquer c ≥ 2 #PraCegoVer : cê maior ou igual a dois.
f(n) = Ω(2 ) #PraCegoVer : éfe de êne é igual a ômega de dois
elevado a êne ? Essa igualdade é verdadeira se existir uma constante c >
0 #PraCegoVer : cê é maior que zero tal que, para n suficientemente
grande temos f(n) ≥ cg(n) #PraCegoVer : éfe de êne é maior ou igual ao
produto de uma constante positiva cê com gê de êne . Essa
desigualdade pode ser satisfeita para qualquer 0 < c ≤ 2 #PraCegoVer :
cê é maior que zero e menor ou igual a dois . Logo, considerando as
duas notações O e Ω #PraCegoVer : ó e ômega juntas, temos que 2 =
Θ(2 ) #PraCegoVer : dois elevado a êne mais um é igual a theta de
dois elevado a êne .
Gráfico 2 – Gráfico das funções 5n, 4n + 1 e 4n 
 #PraCegoVer : cinco êne, quatro êne mais um e quatro êne
n 
n +1 n
n n 
n 
n+1 
n 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 9/28
Fonte: Elaborado pelo autor, 2020. 
Importante observar que para todos os valores de n ≥ 1 #PraCegoVer : êne é maior ou
igual a um expressos na tabela, a função 4n + 1 #PraCegoVer : quatro êne mais um é
sempre maior que 4n #PraCegoVer : quatro êne e menor ou igual a 5n #PraCegoVer:
cinco êne . Quando o gráfico de ambas as funções é plotado, é possível ver mais
claramente como a função 4n + 1 #PraCegoVer : quatro êne mais um é limitada
superiormente pela função 5 n #PraCegoVer : cinco êne e, inferiormente, pela função
4n #PraCegoVer : quatro êne , conforme apresentado no Gráfico 2. Isso significa que a
função 4n + 1 #PraCegoVer : quatro êne mais um nunca crescerá abaixo de 4 n
#PraCegoVer : quatro êne e não crescerá mais do que 5n #PraCegoVer : cinco êne .
Por esta razão dizemos que Θ (n) #PraCegoVer : theta de êne representa um limite
assintótico razoável para a função 4n + 1 #PraCegoVer : quatro êne mais um , já que
ela é limitada superiormente e inferiormente por duas outras funções da mesma classe
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 10/28
assintótica, isso é, a classe linear . Desse modo, é possível afirmar que existem duas
constantes positivas c = 4 e c = 5 e uma n = 1 #PraCegoVer : cê índice um é igual
a quatro e cê índice dois é igual a cinco e uma êne índice zero é igual a um , de
modo que c n ≤ 4n + 1 ≤ c n #PraCegoVer : o produto de cê índice um por êne é
menor ou igual a quatro êne mais um, que por sua vez é menor ou igual ao produto
de cê índice dois por êne para todos os valores de n maiores ou iguais a n 
#PraCegoVer : êne índice zero . Em outras palavras, 4n + 1 = Θ(n) #PraCegoVer :
quatro êne mais um é igual a theta de êne . 
Teste seus conhecimentos
Atividade não pontuada.
2.2 Análise de recorrências
O conceito de recorrência ou recursividade é fundamentado na definição de um objeto ou
de um processo a partir de si próprio, ou seja, a definição recursiva de alguma coisa é
feita em termos da própria coisa. Na matemática, vários objetos são definidos por meio
da apresentação do processo que os produz. Um exemplo tradicional de recursão
envolvendo figuras geométricas são os fractais. A Figura 1 apresenta um exemplo de
fractal nomeado de tetra-círculo que é formado por circunferências “quatro pontos
equidistantes que a divide em quatro arcos congruentes, os quais são centros das novas
circunferências” (MELO; LEIVAS, 2015). 
Figura 1 – Representação dos três primeiros níveis de recorrência para a construção do fractal tetra-círculo. 
Fonte: MELO; LEIVAS, 2015, p. 3. (Adaptada). 
1 2 0 
1 2 
0
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 11/28
Outro exemplo amplamente utilizado de definição de objeto ou processo que é construído
a partir de si próprio é a função fatorial, que desempenha um papel importante na
matemática e na estatística (TENEMBAUN; LANGSAM; AUGENSTEIN, 1998). Dado um
número inteiro positivo n , o fatorial de n (representado como n! ) é definido como o
produto de todos os inteiros entre n e 1. Por exemplo, o fatorial de 5 corresponde a 5 ∙ 4
∙3 ∙ 2 ∙1 = 120 (o fatorial de 0 é definido como 1) #PraCegoVer : o fatorial de cinco é
igual a cinco vezes quatro vezes três vezes dois vezes um que é igual a cento e
vinte . Logo, a função fatorial pode ser escrita como o seguinte sistema de equações,
onde os três pontos representam uma abreviatura para o produto de todos os números
compreendidos entre n – 3 e 2 #PraCegoVer : êne menos três e dois : 
Analisando mais detalhadamente essa função, é possível observar que o fatorial de um
número n pode ser escrito como n! = n * (n – 1)! #PraCegoVer : êne fatorial é igual a
êne vezes o fatorial de êne menos um . Em outras palavras, o fatorial de um número n
corresponde ao produto de todos os inteiros a partir de n até 1. Logo, são verdadeiras as
seguintes igualdades: 
E assim por diante. Fazendo uso de uma notação matemática, a função fatorial de um
número pode ser definida em termos de um caso mais simples de si mesma, o que é
chamado de definição recursiva . O seguinte sistema de equações descreve a definição
recursiva da função fatorial. 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 12/28
VOCÊ SABIA?
Um clássico exemplo de aplicação do conceito de recursão pode ser
encontrado no nome de um tradicional sistema operacional de software
livre conhecido como GNU. O próprio site do projeto explica que o
nome GNU é um acrônimo recursivo para GNU’s Not Unix! , cuja
tradução em português seria GNU não é Unix! (GNU, 2020).
O exemplo a seguir descreve como a definição recursiva da função fatorial pode ser
usada para avaliar 5! #PraCegoVer : cinco fatorial . A definição indica que 5!
#PraCegoVer : cinco fatorial corresponde a 5 · 4! #PraCegoVer : cinco vezes quatro
fatorial . Logo, antes de se proceder com a avaliação de 5! #PraCegoVer : cinco
fatorial , é preciso calcular o valor de 4! #PraCegoVer : quatro fatorial . Aplicando a
definição da função fatorial mais uma vez, obtém-se que 4! = 4 · 3! #PraCegoVer :
quatro fatorial é igual a quatro vezes três fatorial êne . Então, é preciso avaliar 3!
#PraCegoVer : três fatorial antes de avançar com o cálculo de 4! #PraCegoVer :
quatro fatorial . O processo deve ser repetido até que a função alcance o caso base 0!
#PraCegoVer : zero fatorial . Nesse ponto, um valor definitivo é obtido, ou seja, 1 (0! =
1) #PraCegoVer : um de zero fatorial igual a um e, na sequência, todas as demais
avaliações anteriores que ficaram pendentes (1!, 2!, 3!, 4! e 5!) #PraCegoVer : um
fatorial, dois fatorial, três fatorial e cinco fatorial são calculadas. O valor final
corresponde ao resultado da avaliação de 5! #PraCegoVer : cinco fatorial. 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 13/28
No âmbito computacional, muitos algoritmos apresentam uma definição recursiva em sua
estrutura: para resolver um dado problema, eles chamam a si mesmos recursivamente
uma ou mais vezes a fim de lidar com subproblemas de menor complexidade. Esses
algoritmos seguem uma estratégia tipicamente conhecida como de divisão-e-conquista
: eles quebram o problema a ser resolvido em vários subproblemas similares ao original,
mas de tamanho menor, resolvem os subproblemas recursivamente e, por fim, combinam
as soluções de modo a criar a solução para o problema original. Portanto o paradigma de
divisão-e-conquista envolve a execução de três passos em cada nível de recursão
(DASGUPTA; PAPADMITROU; VAZIRANI, 2010): 
Dividir o problema em subproblemas que correspondam a instâncias menores
do mesmo problema;
Conquistar os subproblemas por resolvê-los recursivamente. Se o tamanho
dos subproblemas for suficientemente pequeno, basta apresentar a solução
de maneira direta;
Combinar as soluções dos subproblemas em uma solução para o problema
original.
Para uma recursão funcionar, dois elementos precisam existir, conforme descrito nas
abas a seguir. 
Elementos de uma recursão
» Clique nas abas para saber mais sobre o assunto
 Caso base Chamada recursiva
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 14/28
O Diagrama 1 apresenta uma visão esquemática da estratégia de divisão-e-conquista.
Nesse caso, o tamanho do problema original é reduzido pela mesma constante em cada
iteração do algoritmo. Embora qualquer valor de constante possa ser utilizado, o valor
tipicamente empregado é igual a um. Além da função fatorial, outro exemplo concreto de
aplicação dessa estratégia é na solução de um problema de exponenciação do tipo a 
#PraCegoVer : á elevado a êne , onde a ≠ 0 #PraCegoVer : á é diferente de zero e n é
um número inteiro não negativo. A relação entre a solução de uma instância de tamanho
n e uma instância de tamanho n – 1 #PraCegoVer : êne menos um pode ser obtida pela
fórmula a = a *a #PraCegoVer : á elevado a êne é igual ao produto de á elevado
a êne menos um com á . Então, a função f(n) = a #PraCegoVer : éfe de êne é igual a
á elevado a êne pode ser computada por meio de sua definição recursiva: 
Diagrama 1 – Técnica de dividir e conquistar
Fonte: LEVITIN, 2012, p. 132. (Adaptado). 
n
n n-1 
n 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 15/28
A seguir, o pseudocódigo apresenta como o cálculo de uma função exponencial pode ser
implementado por meio de um algoritmo recursivo. O subproblema, ou chamada
recursiva, está relacionado ao cálculo de a (linha 4) #PraCegoVer : á elevado a êne
menos um (linha quatro) . O caso base corresponde à solução direta da menor
instância do problema (linha 2). 
Algoritmo exponencial
» Clique nas abas para saber mais sobre o assunto
Conforme já descrito, uma recorrência corresponde a uma equação (ou inequação) que
descreve uma função em termos de seu próprio valor aplicado a entradas de menor
tamanho. Recorrências são particularmente utilizadas como ferramentas básicas para a
análise de algoritmos recursivos. Em função disso, elas precisam ser resolvidas a fim de
possibilitarem que o comportamento assintótico de algoritmos dessa classe seja
avaliado. Três principais métodos para a solução de recorrências são (CORMEN et al.,
2009): 
Método da substituição;
Árvores de recursão;
Teorema mestre.
Iterações de uma recursão do tipo T(n) = n + T(n/3) 
 #PraCegoVer : tê de êne é igual a êne mais tê de êne por três
» Clique nas abas para saber mais sobre o assunto
n – 1 
 Entrada Saída
 Iteração 1 – T(n) Iteração 2 – T(n/3) Iteração 3 – T(n/3/3)
Iteração n – T(n/3/3 … /3 )
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 16/28
O método de substituição é um modo objetivo de provar o limite assintótico de uma
recorrência por indução. No método de substituição, em lugar de se tentar encontrar uma
fórmula fechada como solução exata para a recorrência, o objetivo é o de apenas tentar
encontrar uma fórmula fechada que delimite a recorrência. Essa abordagem é, em geral,
mais simples, uma vez que faz uso de constantes durante a resolução da recorrência, o
que, por sua vez, oferece uma margem mais ampla para manipulação (CORMEN et al.,
2009). De modo sucinto, o método da substituição compreende dois passos: 
Sugerir uma fórmula para a solução;
Usar indução matemática para encontrar as constantes e demonstrar que a solução
funciona.
No primeiro passo do método, a solução proposta deve ser substituída pela função ao
aplicar a hipótese indutiva a valores menores; daí o nome método de substituição .
Embora o método seja considerado eficaz, ele depende da sugestão de uma fórmula
para a recorrência. De posse da proposta de solução, o uso do método de substituição
permite que sejam estabelecidos limites superiores ou inferiores em uma recorrência.
Como primeiro exemplo, o método será utilizado para se determinar um limite superior
para a recorrência: 
Classificação das recursões
» Clique nas abas para saber mais sobre o assunto
Cada termo depende exclusivamente dos anteriores. Exemplo: F(n + 2)
= 2F(n + 1) + F(n) #PraCegoVer : éfe de êne mais dois é igual a dois
éfe de êne mais um somado a éfe de êne.
NÃO HOMOGÊNEAS
Além de depender dos termos anteriores, cada elemento também está
em função de um termo independente. Exemplo: F(n) = F(n – 1) + 1
#PraCegoVer : éfe de êne é igual a éfe de êne menos um somado a
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 17/28
Uma proposta inicial de solução a ser testada é T(n) = O(n log n) #PraCegoVer : tê de
êne é igual a ó de êne com logaritmo na base dois com êne . O método da
substituição exige que a desigualdade T(n) ≤ cnlog (n) #PraCegoVer : tê de êne menor
ou igual a cê êne logaritmo na base dois de êne seja provada para uma escolha
apropriada de valor da constante c > 0 #PraCegoVer : cê maior que zero . A aplicação
do método poderia começar assumindo que esse limite é válido para todos os valores
positivos m < n #PraCegoVer : ême menor que êne , em particular para m = n/2
#PraCegoVer : ême é igual a êne sobre dois , o que geraria a seguinte desigualdade
T(n/2) ≤ c(n/2)log (n/2) #PraCegoVer : tê de êne sobre dois é igual a cê vezes êne
sobre dois e isso vezes o logaritmo de êne sobre dois na base dois . O próximo
passo é substituir essa última desigualdade na recorrência a ser resolvida conforme
desenvolvido a seguir. Importante observar que a simplificação do passo (4) para o passo
(5) é verdadeira, assumindo-se c ≥ 1 #PraCegoVer : cê maior ou igual a um . 
Apesar da primeira parte da indução matemática ter sido mostrada, ainda é preciso
provar o caso base da indução, ou seja, é preciso demonstrar que T(1) = 1 #PraCegoVer
: tê de um é igual a um . Fazendo a substituição na solução proposta, verifica-se que o
caso base não é válido: T(1) = c * 1 * log (1) = 0 ≠ 1 #PraCegoVer : tê de um é igual
ao produto de cê com um e com o logaritmo de um na base dois, e isso é igual a
zero, que por sua vez é diferente de um (pois, log (1) = 0) #PraCegoVer : logaritmo
de um na base dois é igual a zero . Contudo, como o objetivo é definir o
comportamento assintótico da recorrência, esse tipo de análise exige apenas que T(n) ≤
cnlog (n) #PraCegoVer : tê de êne é menor ou igual ao produto de cê com êne e
com o logaritmo de êne na base dois para algum c escolhido adequadamente. Logo,
2 
2 
2 
2 
2 
2 
um.
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 18/28
tomando c = 2 #PraCegoVer : cê é igual a dois e aplicando na solução proposta se
obtém T(2) ≤ c * 2 * log (2) #PraCegoVer : tê de dois é menor ou igual ao produto de
cê com dois e com o logaritmo de dois na base dois , o que prova o caso base da
indução e válida a solução proposta para a recorrência. 
Somatórios úteis em recorrências
» Clique nas abas para saber mais sobre o assunto
Para algumas funções de recorrência de menor complexidade, o método de substituição
pode ser eficaz ao ser aplicado para a definição de uma solução exata. Ainda assim, o
método permanece dependente da proposição de uma solução adequada, cuja validação
também precisa ser feita via indução matemática. Um exemplo de recorrências deste tipo
é a função F(n) = F(n – 1) + 3n + 2 #PraCegoVer : éfe de êne é igual a éfe de êne
menos um somado a três êne mais dois com caso base F(1) = 1 #PraCegoVer : éfe de
um é igual a um . Uma solução a ser testada para essa recorrência é dada por F(n) = 3n
/2 + 7n/2 – 4 #PraCegoVer : éfe de êne é igual a três vezes êne elevado a dois
sobre dois e isso somado a sete êne sobre dois e subtraído de quatro . A avaliação
do caso base é direta, ou seja, F(1) = 3/2 + 7/2 – 4 = 1 #PraCegoVer : éfe de um é igual
a três sobre dois mais sete sobre dois menos quatro é igual a um . Para o passo de
indução, a substituição precisa ser feita na recorrência original como segue: 
2 
2 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 19/28
Em alguns casos, uma manipulação algébrica de substituição de variáveis pode tornar
uma recorrência desconhecida em outra cuja solução seja menos complexa. Um
exemplo de aplicação desta estratégia pode ser observado com a função F(n) = 2F(n/2) +
7n + 2 #PraCegoVer : éfe de êne é igual a dois éfe de êne sobre dois e isso somado
a sete êne mais dois . Importante notar que para essa recorrência os valores de êne
que fazem sentido são elementos do conjunto {2 , 2 , 2 , …} #PraCegoVer : dois
elevado a um, dois elevado a dois,dois elevado a três etc. Um modo útil para
começar a resolver a recorrência é calculando o valor de F(n) #PraCegoVer : éfe de êne
para valores pequenos de n , do seguinte modo: 
Para encontrar uma fórmula fechada, uma técnica possível de ser aplicada é desenvolver
ou “desenrolar” a recorrência e escrever 2 #PraCegoVer : dois elevado a cá no lugar
de n (substituição de variável): 
1 2 3 
k 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 20/28
Classificação das recursões
» Clique nas abas para saber mais sobre o assunto
Como k = log (n) #PraCegoVer : cá é igual a logaritmo de êne na base dois , a
fórmula fechada pode ser reescrita como F(n) = 7n log (n) + 3n – 2 #PraCegoVer : éfe
de êne é igual a sete êne vezes o logaritmo de êne na base dois mais três êne
menos dois . Para fins de verificação, o mecanismo de indução matemática pode ser
utilizado. De fato, tomando n = 1 #PraCegoVer : êne é igual a um como case base
temos: 
Para o passo de indução, temos que: 
Portanto, a função é uma solução fechada para a recorrência. 
 Substituição para trás Substituição para frente
2 
2 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 21/28
VAMOS PRATICAR? 
Para praticar a análise de recorrências e a obtenção de expressões fechadas
para elas, vamos tomar a seguinte função: F(n) = F(n/2) + 3 #PraCegoVer: éfe
de êne é igual a éfe de êne sobre dois somado a três . Tente obter uma
fórmula fechada para essa recorrência considerando os seguintes passos:
Defina valores iniciais de F(n) #PraCegoVer: éfe de êne levando em conta que
os valores de n pertencem ao conjunto {2 , 2 , 2 , 2 , …} #PraCegoVer:
dois elevado a um, dois elevado a dois, dois elevado a três, dois elevado
a quatro etc. ;
Faça a substituição da variável n por 2 #PraCegoVer: êne por dois elevado
a cá ;
Aplique a técnica de expansão da recorrência (desenrole a recorrência);
Retorne a recorrência para a variável n fazendo uma nova substituição, k = log
(n) #PraCegoVer: cá igual a logaritmo de êne na base dois , ao término da
expansão.
1 2 3 4 
k 
2 
2.3 Árvores de recursão
Embora o método da substituição seja uma técnica muito objetiva de provar se uma
solução proposta para uma recorrência está correta ou não, esse método apresenta uma
grande limitação: a sua dependência por uma boa sugestão ou um bom “chute” de
solução. Uma classe comum de recorrências é aquela que envolve a geração de
subproblemas como reduções a um fator do problema original – essas costumam ser
recorrências complexas de se propor uma solução. Por exemplo, não é trivial de se
“chutar” que a solução de uma recorrência T(n) #PraCegoVer : tê de êne que envolva
um termo T(n/4) #PraCegoVer : tê de êne sobre quatro somado a Θ( n 2)
#PraCegoVer : theta de êne ao quadrado é limitada superiormente por n . Esse é o
caso de várias outras recorrências. 
2 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 22/28
Diagrama 2 – Ordenação recursiva de um vetor de inteiros
Fonte: LEVITIN, 2012, p. 173. (Adaptado).
Uma estratégia para se encontrar boas possíveis soluções para recorrências é a
construção de árvores de recorrências. A construção de uma árvore começa por se
colocar o termo não recursivo como nó raiz da árvore. Na sequência, o termo recursivo é
representado por meio de nós-filhos no próximo nível da árvore. Um modo prático de
visualizar o uso dessa técnica é por meio de um exemplo computacional conhecido. Esse
é o caso do problema de se ordenar um vetor de números. Uma estratégia muito
eficiente utilizada para esse caso é a dividir-e-conquistar. O vetor é dividido em duas
metades sucessivamente, até que a comparação aconteça apenas entre dois números.
Na etapa de conquista, todos os subvetores ordenados são combinados de forma a gerar
o vetor original ordenado. O Diagrama 3 ilustra como esse processo recursivo de
ordenação é feito sobre um vetor de inteiros. Como a cada iteração o vetor é dividido em
duas metades, o termo recursivo pode ser dado por 2T(n/2) #PraCegoVer : dois tê de
êne sobre dois . Logo, a recorrência será expressa pela função T(n) = 2T(n/2) + O(n)
#PraCegoVer : tê de êne é igual a dois tê de êne sobre dois somado a ó de êne . 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 23/28
Diagrama 3 – Árvore de recursão para T(n) = 2T(n/2) + n 
#PraCegoVer : tê de êne igual a dois tê de êne sobre dois mais êne
Fonte: CORMEN, 2009, p. 89. (Adaptado).
Para esse problema de ordenação, o termo não recursivo n é representado na raiz da
árvore. Como a recorrência T(n/2) #PraCegoVer : tê de êne sobre dois aparece
multiplicada por 2 na função, então dois nós-filhos T(n/2) #PraCegoVer : tê de êne
sobre dois são representados no primeiro nível da árvore. O Diagrama 3 (b) apresenta a
montagem inicial da árvore. Na sequência, o Diagrama 3 (c) mostra como cada termo
T(n/2) #PraCegoVer : tê de êne sobre dois é expandido, representando mais uma
iteração recursiva da função. Nesse caso, mais um nível é criado na árvore. E assim,
esse processo de expansão ou chamadas recursivas da função pode ser representado
quantas vezes for necessário para se entender o comportamento da recorrência. 
Com essa representação do problema de ordenação do vetor, é possível ver que cada
expansão da recorrência acrescenta n termos ao resultado final. Consequentemente,
para resolver a recorrência, é preciso achar a altura da árvore. O Diagrama 3 (d) oferece
uma visão gráfica desse processo e mostra que a altura é dada por log n #PraCegoVer
: logaritmo de êne na base dois . Logo, a soma de todos os termos da árvore resulta
em nlog (n) #PraCegoVer : êne logaritmo de êne na base dois que é uma solução
fechada para a recorrência, ou seja, T(n) = O(nlog n) #PraCegoVer : tê é igual a ó de
2 
2 
2 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 24/28
Síntese
êne logaritmo de êne na base dois . 
Embora uma solução fechada para recorrências possa ser obtida a partir de árvores de
recursão, a solução constitui, na realidade, apenas uma possibilidade ou um “bom chute”
de resolução da recorrência. Isso quer dizer que a solução gerada a partir dessa técnica
precisa ser validada. Um modo de realizar essa verificação é por meio do método de
substituição apresentado previamente. Logo, no caso do problema de ordenação
recursiva de um vetor de inteiros, o caso base a ser verificado é T(1) = 0 #PraCegoVer :
tê de um é igual a zero , o que é confirmado de forma direta – T(1) = 1 • log 1 = 1 • 0 =
0 #PraCegoVer : tê de um é igual ao produto de um com o logaritmo de um na base
dois, que por sua vez é igual ao produto de um com zero que é igual a zero . Já a
hipótese de indução é: 
Fazendo a substituição na função de recorrência, temos: 
Portanto, a solução encontrada pela árvore de recorrência é válida e satisfaz a função.
Teste seus conhecimentos
Atividade não pontuada.
2 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 25/28
Nesta unidade, aprofundamos o estudo da complexidade de algoritmos por conhecer
mais uma notação para a descrição do comportamento assintótico de funções. A notação
Theta é amplamente utilizada nesse contexto e, por isso, tivemos a oportunidade de
conhecer melhor suas propriedades. Outro tipo de ferramenta matemática presente no
projeto e análise de algoritmos são as funções de recorrência. Por estarem
intrinsecamente associadas às recursões dentro da ciênciada computação, a obtenção
de expressões fechadas para essas funções também foi explorada nesta unidade. Em
particular, o método da substituição foi apresentado como estratégia para a validação de
soluções propostas para recorrências. Além disso, a técnica de expansão de termos foi
abordada dando mais subsídio para a manipulação dessas relações.
SAIBA MAIS
Título : Algoritmos 
Autores : Sanjoy Dasgupta, Christos Papadimitriou e Umesh
VaziraniEditora: Bookman 
Ano : 2010 
Comentário : Concentre-se no Capítulo 2 onde a estratégia de divisão-e-
conquista é bem detalhada. Ainda neste capítulo, as relações de
recorrência são apresentadas com vários exemplos práticos, dando uma
visão ainda mais ampla de como essas funções são empregadas. 
Onde encontrar : Biblioteca Virtual da 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 26/28
Título : Algoritmos 
Autores : Sanjoy Dasgupta, Christos Papadimitriou e Umesh
VaziraniEditora: Bookman 
Ano : 2010 
Comentário : Concentre-se no Capítulo 2 onde a estratégia de divisão-e-
conquista é bem detalhada. Ainda neste capítulo, as relações de
recorrência são apresentadas com vários exemplos práticos, dando uma
visão ainda mais ampla de como essas funções são empregadas. 
Onde encontrar : Biblioteca Virtual da 
Título : Algoritmos 
Autores : Sanjoy Dasgupta, Christos Papadimitriou e Umesh
VaziraniEditora: Bookman 
Ano : 2010 
Comentário : Concentre-se no Capítulo 2 onde a estratégia de divisão-e-
conquista é bem detalhada. Ainda neste capítulo, as relações de
recorrência são apresentadas com vários exemplos práticos, dando uma
visão ainda mais ampla de como essas funções são empregadas. 
Onde encontrar : Biblioteca Virtual da 
Referências bibliográficas 
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 27/28
ASCÊNCIO, A. F. G.; ARAÚJO, G. S. Estruturas de dados : algoritmos, análise de
complexidade e implementações em Java e C/C++. São Paulo: Pearson Prentice Hall,
2010. 
 
CORMEN, T. H. et al. Introduction to Algorithms . 3. ed. Massachusetts Institute of
Technology, 2009. 
 
DASGUPTA, S.; PAPADIMITROU, C.; VAZIRANI, U. Algoritmos . Porto Alegre:
Bookman, 2010. 
 
DOBRUSHKIN, V. Métodos para análise de algoritmos . Rio de Janeiro: LTC, 2012. 
 
GNU. O sistema operacional GNU . Disponível em < https://www.gnu.org/ >. Acesso
em: 17 dez. 2020. 
 
HELMENSTINE, A. M. How Many Athoms Exist in the Universe . ThoughtCo, 2019.
Disponível em < https://www.thoughtco.com/number-of-atoms-in-the-universe-603795 >.
Acesso em: 02 nov. 2021. 
 
LEVITIN, A. Introduction to the design and analysis of algorithms . 3. ed. Boston:
Addison-Wesley, 2012. 
 
MELO, C. B. S., LEIVAS, J. C. P. Explorando o fractal Tetra-Círculo: possibilidade
para a introdução de Progressões Geométricas . CIAEM – Conferência
Interamericana de Educação Matemática, 2015. Disponível em < http://xiv.ciaem-
redumate.org/index.php/xiv_ciaem/xiv_ciaem/paper/viewFile/147/103 >. Acesso em: 02
nov. 2021. 
 
SKIENKA, S. S. The Algorithm Design Manual . Nova York: Springer, 2008. 
 
TENEMBAUN, A. A.; LANGSAM, Y.; AUGENSTEIN, M. J. Data Structures Using C .
Nova York: McGraw-Hill, 1998. 
https://www.gnu.org/
https://www.thoughtco.com/number-of-atoms-in-the-universe-603795
http://xiv.ciaem-redumate.org/index.php/xiv_ciaem/xiv_ciaem/paper/viewFile/147/103
08/09/2022 22:02 Unidade 2 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_2/ebook/index.html?redirect=1 28/28