Unidade 4 - Análise de algoritmos

Prévia do material em texto

08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 1/26
ANÁLISE DEANÁLISE DE
ALGORITMOS ALGORITMOS 
UNIDADE 4 – ALGORITMOSUNIDADE 4 – ALGORITMOS
GULOSOS E PROBLEMAS P EGULOSOS E PROBLEMAS P E
NP NP 
Autor: Thiago Nascimento Rodrigues Autor: Thiago Nascimento Rodrigues 
Revisor: Bruno Carreira Coutinho Silva Revisor: Bruno Carreira Coutinho Silva 
INICIAR
Introdução
Caro(a) estudante, 
Os modelos e estratégias que podem ser empregados tanto no projeto como na análise
de algoritmos são os mais variados possíveis. À medida que nos aprofundamos e
dominamos técnicas cada vez mais elaboradas, somos capazes de entender problemas
com níveis de complexidade avançados e, consequentemente, de propor soluções
computacionais mais precisas e eficientes. Por isso, o estudo de algoritmos já conhecidos
e que implementam diferentes abordagens constitui uma etapa relevante para
profissionais que se dedicam à atividade de construir soluções computacionais. 
Nesta unidade, vamos explorar um pouco mais dos algoritmos recursivos e perceber
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 2/26
como eles têm larga aplicabilidade em problemas reais. Expandindo o nosso estudo das
estratégias de ordenação de dados em memória, vamos conhecer um algoritmo que
explora uma abordagem completamente distinta das analisadas até agora. Além disso,
teremos a chance de fazer uma imersão em uma técnica de desenvolvimento de
algoritmos conhecida como gulosa, que é muito empregada em cenários profissionais.
Finalmente, vamos ter uma visão geral sobre as principais categorias que organizam os
problemas dentro da Ciência da Computação. 
4.1 Algoritmos com recorrência
Sequências, também conhecidas como funções de uma variável discreta, aparecem em
muitas aplicações em ciências da computação, em análise numérica e, naturalmente, em
matemática discreta. Muitas dessas aplicações estão enraizadas em problemas práticos
de engenharia, nos quais os sistemas têm um espaço de estados finito ou enumerável.
Outros cenários surgem quando os sistemas mudam de estado apenas em instantes
discretos de tempo. Uma recorrência é uma equação que descreve a evolução ou
comportamento de funções desse tipo (DOBRUSHKIN, 2010). Sob uma perspectiva mais
computacional, recorrências modelam procedimentos que fazem chamadas a si próprios –
os conhecidos algoritmos recursivos. 
 
Muitos algoritmos úteis levam a recorrências descritas por funções inteiras – funções
que manipulam estritamente números inteiros. Uma classe particular desses algoritmos
são aqueles baseados na estratégia de divisão e conquista. Algoritmos desse tipo
normalmente resolvem o problema dividindo-o em vários subproblemas que são
semelhantes ao original, mas têm tamanhos menores e, em seguida, resolvem os
subproblemas recursivamente. A abordagem de dividir e conquistar é uma abordagem de
cima para baixo, uma vez que a solução para uma instância de nível superior de um
problema é obtida descendo e obtendo as soluções para instâncias menores. O tempo de
execução desses algoritmos pode, muitas vezes, ser descrito por uma recorrência de
funções inteiras. 
VOCÊ SABIA?
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 3/26
Dois exemplos típicos de funções inteiras são as funções piso e teto . O piso de
um número real x (escrito como [ x ]) corresponde ao maior inteiro que é menor ou
igual a x . Por outro lado, o teto de um número real x (escrito como [ x ]) é o menor
inteiro que é maior ou igual que x . Ambas funções são amplamente utilizadas na
modelagem de algoritmos recursivos e na solução de equações de recorrência.
Um tradicional exemplo de algoritmo recursivo é a busca binária . A busca binária
funciona de modo distinto da tradicional busca sequencial em que cada item de um vetor
é examinado por vez e comparado com o item que está sendo procurado. Uma busca
binária é executada sobre um vetor previamente ordenado e, por isso, ele pode se valer
dessa condição para realizar uma operação de pesquisa mais eficiente. Se um vetor
contiver somente um elemento, o problema será simples. Caso contrário, a ideia básica
da busca binária é a de comparar o item sendo procurado com o item posicionado no
meio do vetor. Se forem iguais, a busca termina com sucesso. Se o elemento do meio for
maior que o elemento sendo procurado, o processo de busca será repetido na primeira
metade do vetor (porque esse item deve estar na primeira metade); caso contrário, o
processo será repetido na segunda metade. Importante observar que, toda vez que uma
comparação é feita, o número de elementos a pesquisar é cortado pela metade. Para os
vetores grandes, esse método é superior à busca sequencial na qual cada comparação
reduz o número de elementos a pesquisar em apenas um. Por causa da divisão do vetor a
ser pesquisado em duas partes iguais, esse método de busca ficou conhecido como
busca binária. O pseudocódigo a seguir apresenta o passo a passo de uma busca binária
sobre um vetor ordenado de n posições. 
Algoritmo busca binária 
Entrada : Um vetor A[0 ... n] ordenado e uma chave k a ser pesquisada e os índices min e
max correspondentes aos limites à esquerda e à direita, respectivamente 
Saída : O índice i tal que A[i] = k , se k for encontrado em A ; nulo, caso contrário.
1. se min > max então
2. retorna nulo
3. meio ← [[min + max]/2]
4. se k = A[meio] então
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 4/26
5. retorna meio
6. se k < A[meio] então
7. BuscaBinaria(A, min, meio – 1, k)
8. senão
9. BuscaBinaria(A, meio + 1, max, k)
[ #PraCegoVer: Algoritmo de busca binária, tendo na entrada um vetor de A com intervalo
de zero a n orderando e uma chave k a ser pesquisada e os índices mínimo e máximo
correspondentes aos limites à esquerda e à direita, respectivamente. Na saída, tem-se o
índice i tal que A de i é igual a k, se j for encontrado em A, ou nulo, caso contrário. Assim,
a linha um tem se min maior que max então; na linha dois, retorna nulo; na linha três,
meio com seta para a esquerda intervalo de min mais max dividido por dois; na linha
quatro, se k igual a A meio então; na linha cinco, retorna meio; na linha seis, se k menor
que A meio então; na linha sete, busca binária de A, min, meio, traço, um e k; na linha
oito, então; e na linha nove, busca binária de A, meio mais um, max e k.] 
Importante observar que a busca binária foi definida recursivamente de modo muito
natural. Se o item sendo procurado não for igual ao elemento do meio do vetor, as
instruções serão pesquisar um subvetor usando o mesmo método. Desse modo, o método
de busca é definido em termos de si mesmo com um vetor menor como entrada. A
garantia de que o processo terminará está no fato dos vetores de entrada ficarem cada
vez menores, e a busca em um vetor de um único elemento é definida de modo não
recursivo, já que o elemento do meio desse vetor é seu único elemento. 
VOCÊ SABIA?
Uma busca binária é executada sobre um vetor de elementos no qual os objetos
foram posicionados em determinada ordem. Por exemplo, um dicionário ou um
catálogo de telefones pode ser considerado um vetor, cujos elementos estão em
ordem alfabética ou a folha de pagamento de uma empresa pode estar
classificado pelo CPF dos funcionários. Quando queremos pesquisar um nome em
um catálogo de telefones, uma palavra em um dicionário ou determinado
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 5/26
Em termos da complexidade do algoritmo, vemos que a cada chamadarecursiva, o
tamanho do vetor é dividido pela metade, ou seja, o termo da recorrência que modela
essa chamada é dado por T(n) = 2T(n/2) [ #PraCegoVer : tê de êne igual a dois tê de êne
sobre dois]. Para fins de clareza, considerando vetores de tamanho 2 [ #PraCegoVer :
dois elevado a cá], onde k [ #PraCegoVer : cá] é um inteiro não negativo, temos que a
busca binária vai apresentar complexidade da ordem de Θ(log n ) [ #PraCegoVer : theta
do logaritmo êne].
Teste seus conhecimentos
Atividade não pontuada.
empregado em um arquivo de pessoal, o processo usado para encontrar o
elemento é comumente realizado por meio de uma busca binária.
k 
4.2 Ordenação de tempo linear com algoritmo counting sort 
A avaliação do custo-benefício entre tempo de execução e espaço demandando em
memória no projeto de algoritmos é um problema bem conhecido tanto para teóricos
quanto para profissionais de computação. Considere, por exemplo, o problema de
computar valores de uma função em muitos pontos do seu domínio. Se o tempo de
processamento for crítico, podemos pré-calcular os valores da função e armazená-los em
uma tabela. Isso é exatamente o que profissionais tiveram que fazer antes do advento dos
computadores eletrônicos, o que sobrecarregou as bibliotecas com grandes volumes de
tabelas matemáticas. Embora essas tabelas tenham perdido muito de seu apelo com o
uso generalizado de computadores eletrônicos, a ideia subjacente provou ser bastante útil
no desenvolvimento de vários algoritmos importantes para outros problemas. Em termos
um pouco mais gerais, a ideia é pré-processar a entrada do problema, no todo ou em
parte, e armazenar as informações adicionais obtidas para acelerar e resolver o problema
depois (LEVITIN, 2012). Essa estratégia é conhecida como aprimoramento de entrada
(do inglês, input enhancement ) e é base para o algoritmo de ordenação counting sort,
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 6/26
cujo funcionamento difere de todas as demais abordagens de ordenação em memória
estudadas. 
VOCÊ SABIA?
Os termos-padrão usados como sinônimos para a técnica de aprimoramento de
entrada são pré-processamento e pré-condicionamento. De modo surpreendente,
esses termos também podem ser aplicados a métodos que usam a ideia de pré-
processamento, mas sem o uso de espaço extra em memória. Assim, a fim de
evitar confusão, usamos “aprimoramento de entrada” como um nome especial
para a técnica de compensação de tempo por meio do uso de mais espaço
empregada no algoritmo counting sort.
O algoritmo counting sort assume que cada um dos n elementos de um vetor fornecido
como entrada é um número inteiro no intervalo 0 a k , para algum inteiro k . Quando k =
O(n) [ #PraCegoVer : cá igual a ó de êne], a ordenação é executada em um tempo Θ(n) [
#PraCegoVer : theta de êne]. Essa abordagem de ordenação determina, para cada
elemento de entrada x , o número de elementos menores ou iguais que x . Então, ele usa
essas informações para colocar o elemento x diretamente em sua posição no vetor de
saída. Por exemplo, se 17 elementos forem menores que x , então, x pertence à saída na
posição 18. Naturalmente, para lidar com a situação em que vários elementos têm o
mesmo valor, um ajuste precisa ser feito, já que não queremos colocá-los todos na
mesma posição (CORMEN, 2009). 
O pseudocódigo, a seguir, apresenta o passo a passo do algoritmo. Ele faz uso de um
vetor extra B para armazenar os valores ordenados do vetor A informado. Além disso, um
vetor C auxiliar é usado como armazenador temporário. Depois do laço das linhas 02-03
que inicializa todas as posições do vetor C com valor zero, o laço das linhas 04-05 realiza
uma inspeção em cada posição do vetor A . Para cada valor x armazenado em uma
posição j de A , ou seja, x = A[j] [ #PraCegoVer : xis igual á de jota], C[x] [ #PraCegoVer :
cê de xis] é incrementado de 1. Então, depois da linha 05, C[i] [ #PraCegoVer : cê de í]
contém o número de elementos de A que são iguais a i , para cada inteiro i = 0, 1, …, k [
#PraCegoVer : í igual a zero, um até cá]. 
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 7/26
Algoritmo counting sort 
Entrada : Um vetor A de n inteiros com valores entre 0 e k – 1 ; 
Saída : Um vetor B contendo os elementos de A ordenados. 
1. Defina um novo vetor C[0 ... k]
2. para i ← 0 até k faça
3. C[i] ← 0
4. para j ← 1 até n faça
5. C[A[j]] ← C[A[j]] + 1
6. para i ← 1 até k faça
7. C[i]← C[i] + C[i – 1]
8. para j ← n até 0 faça
9. B[C[A[j]]] ← A[j]
10. C[A[j]] ← C[A[j]] – 1
11. retorna B
Características do counting sort
» Clique nas setas ou arraste para visualizar o conteúdo
Números com o mesmo valor aparecem no vetor de saída na mesma
ordem em que aparecem no vetor de entrada.
COMPARAÇÕES ENTRE CHAVES
O algoritmo não realiza qualquer comparação entre as chaves que estão
sendo ordenadas.LIMITE ASSINTÓTICO INFERIOR
Como o algoritmo não é baseado em um modelo de comparações, o
limite inferior de Ω (n log n) [ #PraCegoVer : ômega de êne logaritmo
êne] não se aplica a ele.
APLICABILIDADE
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 8/26
As linhas 06-06 do algoritmo determinam, para cada i = 0, 1, …, k [ #PraCegoVer : i igual
a zero, um até cá], quantos elementos de A são menores ou iguais a i . Para isso, ele
executa uma incremental sobre o vetor C . Finalmente, o laço das linhas 08-10 aloca cada
elemento A[j] [ #PraCegoVer : á de jota] em sua correta posição ordenada no vetor B . Se
todos os n elementos de A forem distintos, então, ao executar a linha 08, para cada A[j] [
#PraCegoVer : á de jota], o valor C[A[j]] [ #PraCegoVer : cê de á de jota] corresponde à
posição correta final de A[j] [ #PraCegoVer : á de jota] no vetor de saída B , uma vez que
existem C[A[j]] [ #PraCegoVer : cê de á de jota], elementos menores ou iguais a A[j] [
#PraCegoVer : á de jota]. Como os elementos podem não ser todos distintos, o valor de
C[A[j]] [ #PraCegoVer :cê de á de jota] é decrementado cada vez que um elemento com
valor iguala A[j] [ #PraCegoVer :á de jota] é alocado no vetor B. Decrementar C[A[j]] [
#PraCegoVer : cê de á de jota] ocasiona que o próximo elemento com valor igual a A[j] [
#PraCegoVer : á de jota], se existir, seja armazenado na posição imediatamente anterior
a A[j] [ #PraCegoVer : á de jota] no vetor de saída. 
A Figura 1 ilustra o funcionamento do algoritmo quando aplicado sobre um vetor de oito
posições e com valores inteiros menores ou iguais a cinco. A Figura 1(a) retrata o vetor A
e o vetor auxiliar C após a linha 05 do algoritmo. A Figura1(b) apresenta o estado do vetor
C após a linha 07. Nas Figuras 1(c) a 1(e), o vetor de saída B , assim como o vetor
auxiliar C , são apresentados após a primeira, segunda e terceira iterações,
respectivamente, do laço indicado nas linhas 08-10. O vetor B ordenado, contendo os
valores de A , é retratado na Figura 1(f).
Muito utilizado como procedimento auxiliar em outros algoritmos de
ordenação como o Radix Sort.
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 9/26
Figura 1 – Operações do counting sort sobre um vetor de 8 posições com valores inteiros menores ou iguais a 5. 
Fonte: CORMEN et al., 2009, p. 195. (Adaptado). 
Em termos de complexidade assintótica, temos as seguintes ordens para cada trecho do
algoritmo:
Laço das linhas 02-03: demanda um tempo Θ(k) [ #PraCegoVer : theta de cá];
Laço das linhas 04-05: demanda um tempo Θ(n) [ #PraCegoVer : theta de êne]; 
Laço das linhas 06-04: demanda um tempo Θ(k) [ #PraCegoVer : theta de cá]; 
Laço das linhas 08-10: demanda um tempo Θ(n) [ #PraCegoVer : thetade êne]. 
Portanto, o tempo total do algoritmo é da ordem de Θ(n + k) [ #PraCegoVer : theta de êne
mais cá]. Na prática, é comum empregar o counting sort quando o valor do maior número
é da ordem de O(n) [ #PraCegoVer : k igual a é de êne]. Nesse caso, o tempo de
execução é Θ(n) [ #PraCegoVer : theta de êne].
4.3 Algoritmos gulosos
De acordo com Kleinberg e Tardos (2006), é difícil, se não impossível, definir
precisamente o significado de algoritmo guloso. Ainda segundo os autores, um algoritmo é
dito guloso se ele constrói uma solução em poucos passos e toma uma decisão “míope”
em cada etapa, a fim de otimizar algum critério. Em outras palavras, um algoritmo guloso
faz uma escolha localmente ideal na “esperança” de que essa escolha o conduzirá a uma
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 10/26
solução globalmente ideal. Muitas vezes é possível projetar vários algoritmos gulosos
diferentes para um mesmo problema, cada um otimizando, em uma vizinhança restrita e
de modo incremental, alguma medida diferente em direção a uma solução.
Aspectos-chave das estratégias gulosas
» Clique nas abas para saber mais sobre o assunto
Cientistas da computação consideram o desenvolvimento de estratégias gulosas como
sendo uma técnica geral de projeto de algoritmos, apesar de ser aplicável apenas a
problemas de otimização. Via de regra, algoritmos gulosos são intuitivamente atraentes e
simples. Dado um problema de otimização, geralmente é fácil descobrir como proceder de
uma maneira gulosa, possivelmente depois de considerar algumas pequenas instâncias
do problema. O que é geralmente mais difícil é provar, quando possível, que um algoritmo
guloso produz uma solução ótima. Uma das maneiras comuns de demonstrar essa
corretude é por meio de indução matemática – mostramos que uma solução parcialmente
construída obtida pelo algoritmo guloso em cada iteração pode ser estendida para uma
solução ótima para o problema geral. Um segundo modo é mostrar que, em cada etapa, o
algoritmo se sai pelo menos tão bem quanto qualquer outro algoritmo faria no avanço em
direção à solução do problema (LEVITIN, 2012). 
 
Viabilidade Localmente ótima Irrevogável
VOCÊ SABIA?
Existem problemas para os quais uma sequência de escolhas localmente ideais
produz uma solução ideal para cada instância do problema em questão. No
entanto existem outros para os quais essa realidade não se mostra verdadeira;
para tais problemas, um algoritmo guloso ainda pode ser valioso se estamos
interessados em uma solução aproximada ou se podemos ficar satisfeitos com ela.
Cormen (2013) defende que o melhor modo de se entender a ideia por trás do projeto de
algoritmos gulosos é por meio da análise de exemplos que implementam estratégias
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 11/26
gulosas. Seguindo essa abordagem, um tradicional problema explorado nesse contexto é
o conhecido como escalonamento de intervalos ou escalonamento de recurso
(ROUGHGARDEN, 2019). Vamos considerar um conjunto de pedidos {1, 2... n} [
#PraCegoVer : conjunto composto pelos número um, dois até êne], onde a enésima
solicitação corresponde a um intervalo de tempo começando em s(i) [ #PraCegoVer :
ésse de í] e terminando em f(i) [ #PraCegoVer : éfe de í]. Um subconjunto de solicitações
é dito compatível se não houver qualquer sobreposição no tempo. O objetivo é aceitar o
maior subconjunto compatível possível. Conjuntos compatíveis de tamanho máximo são
chamados de conjuntos ótimos . 
Algoritmos gulosos – vantagens e desvantagens
» Clique nas setas ou arraste para visualizar o conteúdo
A ideia básica de um algoritmo guloso para o problema de escalonamento de intervalos é
usar uma regra simples para selecionar uma primeira solicitação i [ #PraCegoVer : í
índice um]. Uma vez que a solicitação i [ #PraCegoVer : í índice um] é aceita, todas as
demais solicitações que não são compatíveis com ela são rejeitadas. Em seguida,
selecionamos a próxima solicitação i [ #PraCegoVer : í índice dois] para ser aceita e,
novamente, rejeitamos todas as solicitações que não são compatíveis com i [
#PraCegoVer :í índice dois]. Continuamos assim, até que acabem todos pedidos. O
1 
1 
2 
2 
Para muitos problemas, é surpreendentemente fácil criar um ou vários
algoritmos gulosos que podem funcionar de forma satisfatória.
DESEMPENHO
Muitos algoritmos gulosos apresentam tempo de execução de
complexidade linear. CORRETUDE
Muitas vezes é difícil descobrir se um algoritmo guloso proposto
realmente retorna a saída correta para cada entrada possível. E mesmo
quando um algoritmo guloso está correto, provar sua corretude pode ser
difícil.
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 12/26
desafio em projetar um bom algoritmo guloso é decidir qual regra simples usar para a
seleção – e há muitas regras naturais para este problema que não geram boas soluções. 
Para exemplificar o desafio de se definir uma boa regra de escolha de pedidos, vamos
considerar três estratégias distintas. A regra mais óbvia pode ser sempre selecionar o
pedido disponível que começa primeiro – ou seja, aquele com tempo de início mínimo s(i)
[ #PraCegoVer : ésse de í], o que, por sua vez, faz com que o recurso comece a ser
usado o mais rápido possível. Esse método, entretanto, não produz uma solução ótima.
Se o primeiro pedido for de um intervalo muito longo, então, ao aceitar o pedido, podemos
ter que rejeitar muitos pedidos de intervalos de tempo mais curtos. Uma vez que o
objetivo é atender o máximo de solicitações possível, acabaremos com uma solução
abaixo do ideal. Em um caso muito ruim – por exemplo, quando o tempo de término f(i) [
#PraCegoVer : éfe de í] é o máximo entre todas as solicitações – a solicitação aceita
mantém o recurso ocupado por todo o tempo. Nesse caso, o método guloso aceitaria um
único pedido, enquanto a solução ideal poderia aceitar muitos. Essa situação é ilustrada
na Figura 2. 
Figura 2 – Instâncias do problema de escalonamento de intervalo em que algoritmos gulosos não conseguem
encontrar a solução ideal. 
Fonte: KLEINBERG; TARDOS, 2006, p. 117. (Adaptado). 
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 13/26
Outra estratégia intuitiva seria a de começar aceitando a solicitação que requer o menor
intervalo de tempo – ou seja, a solicitação para a qual f(i) - s(i) [ #PraCegoVer : diferença
entre éfe de í e ésse de í] é o menor possível. Embora essa regra seja um pouco melhor
que a anterior, ela ainda pode produzir um escalonamento não ótimo. Por exemplo, na
Figura 2(b), a aceitação do intervalo mais curto ao meio impediria os outros dois, que
formam uma solução ótima, de serem aceitos. Fica claro que nessa segunda gulosa o
problema é que a segunda solicitação compete com a primeira e com a terceira, ou seja,
aceitar esse pedido acarretaria a rejeição dos outros dois pedidos. 
Desenvolvimento de algoritmos gulosos
» Clique nas abas para saber mais sobre o assunto
Tomando como base a segunda estratégia descrita, poderíamos criar um algoritmo guloso
com a seguinte abordagem de escolha de pedidos: para cada pedido, contamos o número
de outras solicitações que não são compatíveis e aceitamos a solicitação que tenha o
menor número de solicitações não compatíveis. Em outras palavras, selecionamos o
intervalo com o menor número de “conflitos”. Essa escolha gulosa levaria à solução ótima
no exemplo da Figura 2(b). No entanto, para uma instância do problema como
representado na Figura 2(c), a única solução ideal (aceitar as quatro solicitações na linha
superior) possível não seria obtida. Com essa terceiraestratégia gulosa, a solicitação do
meio na segunda linha é aceita o que garante uma solução de tamanho não superior a
três. 
Uma regra gulosa que leva à solução ótima é baseada em uma quarta ideia: devemos
aceitar primeiro o pedido que termina primeiro, ou seja, o pedido i para o qual f(i) [
#PraCegoVer : éfe de í] é o menor possível. Essa também é uma ideia bastante natural:
garantimos que o recurso fique disponível o mais rápido possível, enquanto ainda atende
a uma solicitação. Desse modo, é possível maximizar o tempo restante para atender a
outras solicitações. Para definir um algoritmo de modo mais formal, R será usado para
denotar o conjunto de solicitações que ainda não foram aceitas nem rejeitadas, e A vai
denotar o conjunto de solicitações aceitas. O pseudocódigo do algoritmo é apresentando
a seguir. 
 
Passo 1 Passo 2 Passo 3
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 14/26
Algoritmo escalonamento guloso 
Entrada : Um conjunto R de todas as requisições e um conjunto A vazio; 
Saída : Conjunto A com todas as requisições aceitas.
1. enquanto R ≠ ∅ faça
2. Escolha uma requisição i ∈ R com menor tempo para finalização
3. A ← A ∪ {i} 
4. Remova todas requisições de R que não sejam compatíveis com i
5. fim enquanto
6. retornar A 
Um exemplo de execução do algoritmo é ilustrado na Figura 3. Em cada etapa, o intervalo
selecionado está indicado com linhas mais escuras, e os intervalos excluídos na etapa
correspondente são indicados com linhas tracejadas.
Figura 3 – Exemplo de execução do algoritmo de escalonamento guloso. 
Fonte: KLEINBERG; TARDOS, 2006, p. 119. (Adaptado). 
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 15/26
Em termos de implementação, o algoritmo guloso apresentado pode ser construído de
forma a funcionar com um complexidade da ordem O(n log n) [ #PraCegoVer : ó de êne
logaritmo de êne]. Primeiramente, é preciso ordenar as n solicitações de acordo com o
tempo para finalização e rotulá-las nessa ordem; ou seja, vamos assumir que f(i) < f(j) [
#PraCegoVer : éfe de í menor que éfe de jota] quando i < j [ #PraCegoVer : í menor que
jota]. Essa ordenação leva um tempo O(n log n) [ #PraCegoVer : ó de êne logaritmo de
êne] quando empregados algoritmos como quick sort (melhor caso) ou merge sort . Um
tempo O(n) [ #PraCegoVer : ó de êne] adicional será necessário para a construção de um
vetor S(1... n) [ #PraCegoVer : ésse maiúsculo de um até êne] com a propriedade de que
S(i) [ #PraCegoVer : ésse maiúsculo de í] contém o valor s(i) [ #PraCegoVer : ésse de í].
Feito isso, as requisições devem ser selecionadas processando-se os intervalos em
ordem crescente de f(i) [ #PraCegoVer : éfe de í]. O primeiro intervalo sempre deve ser
selecionado. Então, deve-se iterar por meio dos intervalos em ordem até atingir o primeiro
intervalo j para o qual s(j) ≥ f(1) [ #PraCegoVer : ésse de jota maior ou igual a éfe de um]
– este corresponderá ao próximo intervalo a ser selecionado. De modo mais geral, se o
intervalo mais recente que selecionamos terminar no tempo f , continuamos iterando pelos
intervalos subsequentes até chegarmos ao primeiro j para o qual s(j) ≥ f [ #PraCegoVer :
ésse de jota maior ou igual a éfe]. Desse modo, o algoritmo guloso analisado acima pode
ser implementado gastando um tempo constante por intervalo e fazendo com que esta
parte do algoritmo demande um tempo O(n) [ #PraCegoVer : ó de êne]. 
Teste seus conhecimentos
Atividade não pontuada.
4.4 Problemas P e NP
Diferentes algoritmos possuem uma ampla variedade de funções de complexidade de
tempo, e a caracterização de quais dessas funções são “suficientemente eficientes” e
quais são “muito ineficientes” sempre vai depender do problema a ser resolvido. No
contexto da computação, o conceito de problema está relacionado a uma questão geral
que precisa ser respondida e que frequentemente possui vários parâmetros ou variáveis
livres, cujos valores não são especificados. Logo, um problema pode ser descrito por uma
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 16/26
descrição geral de todos os seus parâmetros ou uma afirmação a respeito de qual
propriedade a resposta/solução deve satisfazer. De posse dessa definição, uma instância
de um problema é obtida por meio da especificação de valores particulares para todos os
parâmetros do problema. Um modo de se descrever como a solução para um dado
problema pode ser obtida consiste em apresentar um algoritmo para ele, ou seja, listar o
conjunto de passos que levam à geração da solução. Um algoritmo é dito capaz de
resolver um problema X se tal algoritmo pode ser aplicado a uma instância I de X e tem-se
a garantia que ele sempre produzirá uma solução para a instância I (GAREY; JOHNSON,
1979). 
Para vários problemas encontrados na literatura científica, já foram propostos algoritmos
capazes de encontrar soluções em tempo polinomial, ou seja, dada uma entrada de
tamanho n , o pior caso da complexidade de tempo é O(n ) [ #PraCegoVer : ó de êne
elevado a cá] para alguma constante k . Algoritmos que apresentam esse comportamento
assintótico são ditos tratáveis . Embora diversas técnicas já tenham sido desenvolvidas
para guiar a construção de algoritmos com essa ordem de eficiência, não é possível
afirmar que exista uma metodologia geral para a obtenção de procedimentos
computacionais eficientes para qualquer dado problema. Ao contrário, cada novo
problema que surge apresenta, em geral, desafios desconhecidos e que exigem a
proposição de novas estratégias para lidar com a dificuldade inerente a cada um (SEN;
KUMAR, 2019). Na prática, existem problemas para os quais os únicos algoritmos
capazes de solucioná-los demandam um tempo computacional inviável – à medida que o
tamanho da entrada cresce, o tempo requerido para se resolver o problema cresce a uma
taxa não polinomial (crescimento exponencial, fatorial etc.). Problemas dessa natureza
são ditos intratáveis . 
Apesar dessas duas classes de problemas (tratáveis e intratáveis) apresentarem uma
diferença determinante em relação à eficiência na obtenção de suas soluções, ainda
assim, problemas dessas duas categorias podem ser resolvidos por meio de algum
algoritmo computacional. Essa condição os classifica como problemas computáveis .
Outros sinônimos comuns para “computável” são “resolvível”, “decidível” e “recursivo”. Em
contrapartida, são problemas que não podem ser resolvidos por meio de um programa
executado por meio de um computador. Esses são ditos problemas incomputáveis . O
Quadro 1 apresenta uma visão esquemática de como os problemas na computação
podem ser classificados de acordo com a eficiência e viabilidade de implementação
k 
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 17/26
computacional dos algoritmos capazes de resolvê-los. Nesse quadro, a marcação
“sim/não” na classe dos problemas incomputáveis indica que, para certos problemas
considerados intratáveis, não existe ainda uma prova formal de que são, de fato,
intratáveis.
Quadro 1 – As três maiores categorias de problemas computacionais
PROBLEMAS
TRATÁVEIS
PROBLEMAS
INTRATÁVEIS
PROBLEMAS
INCOMPUTÁVEIS
Descrição
Podem ser
resolvidos
eficientemente
Existem
algoritmos
para
resolvê-
los, mas
demandam
tempo
inviável
Não podem
ser resolvidos
por nenhum
programa
computacional
Computáveis
na teoria
Sim Sim Não
Computáveis
na prática
Sim Sim/não Não
Exemplo
Rota mais
curta em um
mapa
Decriptação
Encontrar todos os
erros 
de um programa
computacional
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=118/26
VOCÊ SABIA?
A máquina de Turing, proposta em 1936, é provavelmente o modelo para
formalização de algoritmos mais utilizado. De acordo com Diverio e Menezes
(2011), o trabalho de Turing foi “o primeiro a identificar programas escritos para
uma máquina computacional, com noções intuitivas de efetivamente computável”.
A máquina de Turing é um mecanismo usado para realização de cálculos e é
composto de: uma fita de tamanho infinito para armazenar dados, uma unidade de
controle capaz de realizar cálculos e um programa com comandos a serem
executados pela unidade de controle.
Um exemplo de problema dessa classe é conhecido como o problema da totalidade. Ele
consiste em decidir se uma máquina de Turing arbitrária é interrompida para qualquer
entrada passada para ela. Se existir um algoritmo capaz de tomar essa decisão, então, é
dito que ele calcula uma “função total”. Esse problema é equivalente ao problema de
determinar se um programa pode ou não entrar em um laço infinito para qualquer entrada
informada. Do mesmo modo, o fato do problema de a totalidade ser indecidível significa
que não é possível escrever um programa que seja capaz de encontrar qualquer laço
infinito em qualquer programa. 
Ainda que para uma entrada de tamanho n = 10 [ #PraCegoVer : êne igual a dez], um
algoritmo demande um tempo 10 [ #PraCegoVer : dez elevado a cem] (a quantidade
Fonte: Elaborado pelo autor, 2021.
Vários são os problemas (ou funções) que são decidíveis (ou computáveis), o que
significa que existe algum algoritmo que calcula uma resposta (ou saída) para qualquer
instância do problema (ou para qualquer entrada da função) em um número finito de
etapas simples. Por outro lado, também existem problemas e funções que são
indecidíveis ou incomputáveis, significando que não existe um algoritmo que possa
calcular uma resposta ou saída para todas as entradas em um número finito de passos.
Neste contexto, indecidível significa simplesmente incomputável dentro do escopo de um
problema de decisão cuja resposta (ou saída) é “sim” ou “não”.
100 
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 19/26
10 [ #PraCegoVer : dez elevado a cem] é conhecida como um googol – origem do
nome “Google”), um problema que requer um tempo Θ(n ) [ #PraCegoVer : theta de
êne elevado a cem] é considerado como tratável. No entanto, na prática, poucos são os
algoritmos dessa ordem de complexidade. Em geral, os problemas da classe P exigem
muito menos tempo. Além disso, uma vez que um primeiro algoritmo de tempo polinomial
é encontrado para um problema, normalmente novos algoritmos ainda mais eficientes são
propostos subsequentemente (Cormen, 2013). 
Conforme já apresentado, cientistas da computação em geral consideram problemas
solucionáveis por algoritmos de tempo polinomial como “tratáveis” o que, de modo
informal, traz o significado de “fácil de lidar”. Um algoritmo é dito de tempo polinomial se o
seu tempo de execução no pior caso é limitado por um polinômio cujo grau é da ordem
das instâncias do problema. Mais formalmente, um algoritmo é polinomial se existe um
número i para todas as instâncias, tal que a complexidade de tempo do algoritmo é O(n )
[ #PraCegoVer : ó de êne elevado a í] onde n corresponde ao tamanho da instância.
Nesse sentido, se existir um algoritmo de tempo polinomial para um dado problema, esse
problema é dito como pertencente à classe P . 
VOCÊ SABIA?
Importante nunca confundir problemas da classe NP com problemas não
polinomiais. Um problema é dito NP se é verificável em tempo polinomial,
entretanto, ainda não foi encontrado um algoritmo que o resolva em tempo
polinomial. Por outro lado, problemas não polinomiais não se trata de problemas
para os quais não conhecemos um algoritmo polinomial, hoje, mas de problemas
que nunca terão um algoritmo polinomial. Problemas desse tipo são considerados
intratáveis (FORTNOW, 2009).
Há problemas, entretanto, que são verificáveis em tempo polinomial, mas para os quais
ainda não foram encontrados algoritmos polinomiais que os resolvam. Problemas desse
tipo são considerados como pertencentes à classe NP . Para resolver uma instância de
um problema desse tipo, o melhor que se pode fazer é testar todos os candidatos à
solução da instância. Outra característica desses problemas é a verificabilidade de suas
100 
100 
i 
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 20/26
soluções. Supondo que uma solução seja proposta para um dado problema, deseja-se
verificar se a solução é correta ou não. Nesse sentido, outra característica de problemas
da classe NP é que, para todos eles, é possível realizar a verificação de uma solução
proposta em tempo polinomial. Uma solução apresentada para um problema NP é
chamada de certificado . Além disso, para que um problema seja considerado como NP,
o tempo para se verificar um certificado deve ser polinomial e da mesma ordem que o
tamanho da entrada do problema e do próprio certificado. 
Problemas NP
» Clique nas setas ou arraste para visualizar o conteúdo
índice í, jota] entre cada cidade e um número k qualquer, decidir se é
possível construir um circuito fechado em que um viajante visite todas as
cidades exatamente uma única vez e cujo comprimento total
corresponda a, no máximo, o valor de k .
PROBLEMA DE PROGRAMAÇÃO LINEAR
Dada uma lista de m desigualdades lineares com coeficientes racionais
sobre n variáveis u , …, u [ #PraCegoVer : sequência de u índice 1
até u índice êne] (uma desigualdade linear é descrita da forma a u +
a u + … + a u ≤ b [ #PraCegoVer : de á índice um vezes u índice
um mais á índice dois vezes u índice dois e isso somando até á índice
êne vezes u índice êne e essa soma menor ou igual a bê] para algum
conjunto de coeficientes a ,…, a , b [ #PraCegoVer : sequência de á
índice um até á índice bê, seguido de bê]), decidir se existe uma
atribuição de números racionais para as variáveis u , …, u [
#PraCegoVer : sequência de u índice um até u índice êne] que satisfaça
todas as desigualdades.
1 n 
1 1 
2 2 n n 
1 n 
1 n 
SOMA DE SUBCONJUNTO
Dados números naturais p , …, p e c [ #PraCegoVer : sequência de
pê índice um até pê índice êne e cê], decidir se existe um subconjunto K
de {1, …, n} [ #PraCegoVer : conjunto de um até êne] tal que a soma Σ (
p : k ∈ K ) seja igual a c [ #PraCegoVer : somatório de pê índice cá tal
que cá pertença ao subconjunto cá maiúsculo seja igual a cê].
1 n 
k 
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 21/26
Naturalmente, se um problema pode ser resolvido em tempo polinomial, então, um
certificado para esse problema também pode ser verificado em tempo polinomial. Em
outras palavras, todo problema pertencente à classe P pertence automaticamente à
classe NP. O inverso, no entanto, constitui uma questão em aberto já por muitos anos.
Cabe ressaltar a importância de não se confundir problemas da classe NP com problemas
não polinomiais. De fato, até os dias atuais não foi encontrado, ainda, um único problema
NP provado que não esteja em P, ou seja, não foi identificado um problema que pode ser
verificado em tempo polinomial, mas para o qual não exista um algoritmo polinomial que o
resolva. Logo, a pergunta que padece de uma resposta formal é: todo problema cuja
solução pode ser verificada em tempo polinomial pode também ser resolvido por um
algoritmo polinomial? (KLEINBERG; TARDOS, 2006). 
Existe, ainda, outra classe de problemas que são considerados os mais difíceis dentre os
da classe NP. Eles são conhecidos como problemas NP-completos . Informalmente, um
problema é NP-completo se ele atende a duas condições: (1) está em NP e (2) se existir
um algoritmo de tempo polinomial para o problema, então, vai existir uma maneirade
converter todos os problemas da classe NP nesse problema, de modo a resolvê-los em
tempo polinomial. Logo, se existir um algoritmo de tempo polinomial para qualquer
problema NP-completo, ou seja, se houver algum problema NP-completo em P, pode-se
afirmar que P = NP [ #PraCegoVer : pê é igual a êne pê]. 
O Quadro 2 apresenta, de modo sintético, uma descrição das classes de computabilidade
nas quais os problemas podem ser agrupados. 
Quadro 2 – Classes de computabilidade 
CLASSE DESCRIÇÃO
P
Problema resolvível em tempo
polinomial com ordem correspondente
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 22/26
ao tamanho da entrada.
NP
Problema para o qual não se conhece
um algoritmo polinomial, isto é, dado
um certificado, é possível verificar em
tempo polinomial que o certificado é
uma solução para ele.
NP-difícil
Problema tal que, se existir um
algoritmo polinomial que o resolva,
então será possível converter todos os
problemas NP nele próprio de modo a
tornar possível que todo problema NP
seja resolvido em tempo polinomial.
NP-completo
Problema que é tanto NP-difícil como
NP.
Fonte: Elaborado pelo autor, 2021. 
Como os problemas NP-completos são os mais difíceis da classe NP, se houver algum
problema em NP que não é possível de ser resolvido em tempo polinomial, então,
nenhum dos problemas NP-completos são. Nesse contexto, outra classe de problemas é
conhecida como NP-difícil . Um problema é dito NP-difícil se ele satisfizer a segunda
condição de NP-completude, mas pode ou não estar em NP. A Figura 4 ilustra como as
diferentes classes estão relacionadas como conjuntos de problemas. 
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 23/26
Figura 4 – Diagrama das classes de computabilidade supondo P contido em NP e diferente de NP. Fonte: Elaborado
pelo autor, 2021. 
Para concluir, destacamos que, como afirmam Diverio e Menezes (2011, p. 246), “o
objetivo do estudo da computabilidade é determinar a solucionabilidade de problemas, ou
seja, investigar a existência ou não de algoritmos que solucionem determinada classe de
problemas”. Por conseguinte, são investigados os limites da computabilidade e de sua
implementação, levando o estudo da solucionabilidade a não focar na pesquisa de
soluções inexistentes. 
Síntese
Nesta unidade, tivemos a oportunidade de explorar um pouco mais o conceito de
algoritmos recursivos. Vimos que as funções de recorrências constituem um poderoso
recurso matemático para modelagem de algoritmos desta classe. Além disso,
conseguimos explorar uma nova estratégia dentro do problema de ordenação de dados.
Por meio do detalhamento do algoritmo counting sort, vimos que é possível alcançar um
melhor desempenho computacional quando fazemos uso de mais espaço em memória. 
Com relação às estratégias disponíveis para fundamentar o projeto de algoritmos,
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 24/26
aprendemos como explorar uma abordagem conhecida como gulosa. A versatilidade
dessa estratégia dá margem para o desenvolvimento de um amplo espectro de algoritmos
que podem ser testados nos mais diversos cenários reais. Finalmente, o conceito de
computabilidade foi explorado e foi possível perceber que certos problemas não podem
ser resolvidos por meio de um algoritmo com número finito de passos. Esse mesmo
conceito foi adicionalmente abordado dentro das diferentes classes de problemas
existentes. Em decorrência dessa análise, uma das grandes questões que permanecem
em aberto dentro da Ciência da Computação, a saber P = NP? [ #PraCegoVer : pê igual a
êne pê?], também foi pontuada. 
SAIBA MAIS
Título : Algoritmos 
Autores : Sanjoy Dasgupta, Christos Papadimitriou e Umesh Vazirani 
 Editora : Bookman 
 Ano : 2010 
Comentário : Aproveite, primeiramente, o capítulo 5, em que a estratégia
de projeto de algoritmos gulosos é bem trabalhada. Mas não deixe de
explorar o capítulo 8, em que os conceitos relacionados a problemas P e
NP são igualmente bem analisados. 
 Onde encontrar : Biblioteca Virtual da 
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 25/26
Título : Estruturas de dados: algoritmos, análise de complexidade e
implementações em Java e C/C++ 
 Autor : Ana F. Gomes Ascencio 
Editora : Pearson Prentice Hall 
Ano : 2010 
Comentário : Para se aprofundar nos conceitos relacionados a
recorrências, explore o capítulo 1, em que vários outros recursos
matemáticos são analisados dentro do contexto dessas funções. E, para
uma visão mais detalhada da busca binária considerada nesta unidade,
analise as seções finais do capítulo 2. 
Onde encontrar : Biblioteca Virtual da Laureate
Título : Métodos para análise de algoritmos 
 Autor(a) : Vladimir A. Dobrushkin 
Editora : LTC 
 Ano : 2012 
Comentário : Explore o capítulo 5, em que o conceito de recorrências é
apresentado sob uma perspectiva muito matemática. Nesse mesmo
capítulo, algumas aplicações são detalhadas e possibilitam ter uma visão
mais prática de como essas funções podem ser empregadas. 
Onde encontrar : Biblioteca Virtual da Laureate
Referências bibliográficas 
08/09/2022 22:02 Unidade 4 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_4/ebook/index.html?redirect=1 26/26
CORMEN, T. H. et al. Introduction to algorithms . 3.ed. Cambridge: MIT Press, 2009. 
CORMEN, T. H. Algorithms unlocked . 1. ed. Cambridge: MIT Press, 2013. 
DASGUPTA, S.; PAPADIMITROU, C.; VAZIRANI, U. Algoritmos . Porto Alegre: Bookman,
2010. 
DOBRUSHKIN V. A. Methods in algorithmic analysis , 1. ed. Boca Raton: CRC Press,
2010. 
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação : máquinas universais e
computabilidade. 3. ed. Porto Alegre: Bookman, 2011. 
FORTNOW, L. The Status of the P Versus NP Problem. Communications of the ACM , v.
52, n. 9,p. 78-86, 2009. Disponível em: < https://cacm.acm.org/magazines/2009/9/38904-
the-status-of-the-p-versus-np-problem/fulltext >. Acesso em: 12 jan. 2021. 
GAREY, M. R.; JOHNSON, D. S. Computers and intractability : a guide to the theory of
NP-completeness. 1. ed. Nova Jersey: Bell Telephone Laboratories, 1979. 
KLEINBERG, J.; TARDOS, E. Algorithm design . 1. ed. Boston: Pearson Education,
2006. 
LEVITIN, A. Introduction to the design and analysis of algorithms . 3. ed. Boston:
Addison-Wesley,2012. 
ROUGHGARDEN, T. Algorithms illuminated – Part 3: greedy algorithms and dynamic
programming. 1. ed. San Francisco: Soundlikeyourself Publishing, 2019. 
SEN, S.; KUMAR, A. Design and analysis of algorithms : a contemporary perspective. 1
ed. Cambridge: Cambridge University Press, 2019.
https://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext