Unidade 1 - Análise de algoritmos

Prévia do material em texto

08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 1/28
ANÁLISE DE ALGORITMOSANÁLISE DE ALGORITMOS
UNIDADE 1 – ALGORITMOS EUNIDADE 1 – ALGORITMOS E
ORDENAÇÃO EM MEMÓRIAORDENAÇÃO EM MEMÓRIA
PRIMÁRIA PRIMÁRIA 
Autor: Thiago Nascimento Rodrigues Autor: Thiago Nascimento Rodrigues 
Revisor: Bruno Carreira Coutinho Silva Revisor: Bruno Carreira Coutinho Silva 
INICIAR
Introdução
Caro(a) estudante, 
A noção de algoritmo está presente em qualquer tarefa que precise ser realizada e que demande
uma sequência de passos bem definida. Sob uma perspectiva computacional, esse mesmo conceito
se faz presente quando é preciso especificar para um computador algum conjunto de operações que
ele deve executar. Uma das tarefas mais comuns detalhadas via algoritmos computacionais é a
ordenação de dados em memória. Várias são as estratégias conhecidas para se realizar esse tipo de
operação de maneira eficiente. 
Nesta unidade, teremos uma visão mais precisa do conceito de algoritmos computacionais e de como
é possível fazer uma medição do desempenho desses procedimentos. Nesse cenário, serão
explorados dois algoritmos projetados para ordenar dados na memória principal de um computador.
As diferentes estratégias implementadas por esses algoritmos serão detalhadas e a eficiência de
cada um deles será avaliada através de uma métrica amplamente utilizada na Ciência da
Computação. 
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 2/28
1.1 Fundamentação Matemática dos Algoritmos
Algoritmos estão presentes no dia a dia das pessoas em geral. As instruções para uso de
medicamentos, o passo a passo de montagem de um equipamento ou uma receita culinária são
alguns exemplos de algoritmos. Um algoritmo pode ser visto como uma sequência de ações
executáveis para a obtenção de uma solução para um determinado tipo de problema. Segundo
Dijkstra (1971), um algoritmo corresponde a uma descrição de um padrão de comportamento,
expresso em termos de um conjunto finito de ações. Por exemplo, ao executar a operação a + b é
possível identificar um mesmo padrão de comportamento, ainda que a operação seja realizada para
distintos valores de a e b. 
A descrição formal de qualquer algoritmo, assim como a caracterização mais precisa de seu
desempenho, é comumente fundamentada em conceitos e notações matemáticas. Uma técnica
amplamente utilizada na análise do comportamento de algoritmos é conhecida como indução
matemática . De maneira sucinta, ela é usada para verificar que determinada afirmação (operação) é
válida para qualquer valor natural (número inteiro maior que zero) informado. Para isso, dois passos
devem ser dados: 
Passo 1 (Caso base): Mostrar que a afirmação é verdadeira para um valor inicial.
Passo 2 (Passo de indução) : Mostrar que se a afirmação for verdadeira para os n primeiros
números ( n primeiras iterações), então a afirmação é verdadeira para os n + 1 números ( n + 1
iterações).
Como exemplo, considere a seguinte série de equações que já foram descobertas várias vezes de
forma independente ao longo dos anos: 
1 = 1 
1 + 3 = 2 
1 + 3 + 5 = 3 
1 + 3 + 5 + 7 = 4 
1 + 3 + 5 + 7 + 9 = 5 
#PraCegoVer : Sequência de 5 equações, uma em cada linha. Cada linha i
contém a soma dos i- ésimos primeiros números ímpares positivos. Assim, na
primeira linha, temos 1 igual a 1 ao quadrado. Na segunda linha, 1 mais 3 igual
a 2 ao quadrado. Na terceira linha, 1 mais 3 mais 5 igual a 3 ao quadrado. Na
Bons estudos! 
2 
2 
2 
2 
2
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 3/28
quarta linha, 1 mais 3 mais 5 mais 7 igual a 4 ao quadrado. E na última linha, 1
mais 3 mais 5 mais 7 mais 9 igual a 5 ao quadrado. 
Ela pode ser formulada pela seguinte propriedade geral: 
1 + 3 + 5 + … + (2 n – 1) = n . 
#PraCegoVer : Equação geral da soma de n números ímpares positivos,
representada por 1 mais 3 mais 5 e essa soma se repete até o limite de 2n
menos 1 resultando em n elevado ao quadrado. 
Inicialmente, a equação acima será chamada de P(n) . Logo, busca-se mostrar que P(n) é válida para
todo número positivo n . Seguindo os dois passos estabelecidos pela técnica de indução matemática
temos: 
Caso base: Como 1 = 1 , temos que P (1) é válido.
Passo de indução: Se todo P (1), …, P ( n ) é válido, então, em particular, P ( n ) é válido. Neste
caso, se adicionarmos o termo 2 n + 1 em ambos os lados da propriedade geral formulada
acima, temos que:
1 + 3 + 5 + … + (2 n – 1) + (2 n + 1) = n + 2 n + 1 = ( n + 1) 
#PraCegoVer : Equação geral da soma de n + 1 números ímpares. Ela é
representada por 1 mais 3 mais 5 e essa soma se repete até o limite de 2n
menos 1 mais 2n mais 1, sendo igual a n ao quadrado mais 2n mais 1, que é
igual a n mais 1 elevado ao quadrado. 
demonstrando assim que P ( n + 1) também é válido. 
VOCÊ SABIA?
Até o ano 1957, a palavra algoritmo não estava presente nos dicionários mais conceituados
internacionalmente. Apenas a forma “ algorism ”, de significado mais antigo – o processo de
fazer aritmética usando algarismos arábicos – era encontrada. Com o passar dos anos,
historiadores matemáticos recuperaram a origem da palavra: ela deriva do nome do um
famoso matemático persa Abdu Abdullah Mohamed ben Musa Al-Khwarizmi (viveu entre os
anos 780 a 850). Gradualmente, a forma e o significado da palavra foram sendo modificados
até alcançar a escrita atual: algoritmo (KNUTH, 1997). 
O operador somatório é outro elemento matemático muito empregado na descrição de algoritmos
computacionais. Basicamente ele é utilizado para apresentar de forma compacta a adição de
sequências de números. Neste caso, a soma de uma sequência a , a , …, a de números pode
ser expressa como 
2 
2 
2 2 
1 2 n 
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 4/28
#PraCegoVer : Notações de dois somatórios equivalentes. O primeiro é um
somatório de a índice j com j variando de 1 a n; o segundo é o somatório de a
índice j com j maior ou igual a 1 e menor ou igual a n. 
Duas operações algébricas simples envolvendo somatórios são muito importantes e a familiaridade
com eles torna possível a solução de muitos problemas. Elas são descritas a seguir. 
» Propriedade distributiva
#PraCegoVer : Aplicação da propriedade distributiva sobre dois somatórios. O
somatório de a índice i seguido do somatório de b índice j é igual ao somatório
sobre o índice i seguido do somatório sobre o índice j do produto de a índice i
por b índice j. 
Para um melhor entendimento dessa propriedade, podemos considerar um caso particular dela: 
#PraCegoVer : Exemplo de aplicação da propriedade distributiva dos
somatórios sobre duas somas. O somatório de a índice i com i variando de 1
até 2 seguido do somatório de b índice j com j variando de 1 até 3 é igual o
produto de a índice 1 somando a índice 2 por b índice 1 somando b índice 2
somando b índice 3. Toda essa expressão é igual ao somatório sobre o índice i
variando de 1 a 2 seguido do somatório do produto de a índice i por b índice j
com j variando de 1 até 3. 
» Troca da ordem dos somatórios
Duas operações algébricas simples envolvendo somatórios são muito importantes e a familiaridade
com eles torna possível a solução de muitos problemas. Elas são descritas a seguir. 
#PraCegoVer : Expressão matemática da troca de somatórios: o somatório
sobre o índice i seguido do somatório sobre o índice j, ambos em relação ao
termo a índice ij, é igual ao somatório sobre o índice j seguido do somatório
sobre o índice, ambos em relação ao termo a índice ij. 
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=15/28
A troca da ordem dos somatórios é extremamente útil quando uma forma simples para um dos
somatórios é conhecida, mas não para o outro envolvido. A permutação de n objetos em um arranjo
de n objetos distintos constitui outra operação matemática cujas propriedades são de grande
importância na análise de algoritmos. O processo de contagem de quantas permutações de n objetos
são possíveis de serem construídas decorre da percepção de que existem n maneiras de escolher o
objeto mais à esquerda e, uma vez feita esta escolha, existem n - 1 maneiras de selecionar um objeto
diferente para colocar próximo. Logo, há n ( n - 1) escolhas para as duas primeiras posições. Da
mesma forma, verificamos que há n - 2 opções para o terceiro objeto distinto dos dois primeiros, e um
total de n ( n - 1)( n - 2) maneiras possíveis de escolher os três primeiros objetos. No geral, se pnk
denota o número de maneiras de escolher k objetos de n para que sejam organizados em uma linha,
vemos que 
pnk = n ( n - 1)( n – 2) … ( n - k + 1).
#PraCegoVer : Fórmula da permutação de n objetos dispostos de k em k: p
índice nk é igual ao produto de n por n menos 1 seguido de n menos 2 e esse
produto se repetindo até o limite de n menos k mais 1. 
O número total de permutações é, portanto 
p = n ( n - 1)( n – 2) … (1)
#PraCegoVer : Fórmula da permutação de n objetos dispostos de n em n: p
índice nn é igual ao produto de n por n menos 1 seguido de n menos 2 e esse
produto de se repetindo até o limite de 1. 
Como exemplo,considere o conjunto { a, b, c } detrês elementos. Temos que p = 6 e as
permutações geradas são: 
a b c, a c b, b a c, b c a, c a b, c b a.
Um importante operador empregado na quantificação do número de permutações possíveis dos
elementos de um conjunto é conhecido como fatorial e ele é denotado por 
n ! = 1⋅2⋅…⋅ n
#PraCegoVer : Fórmula de cálculo de um número n fatorial: n fatorial é igual ao
produto de 1 por 2 por 3 e assim sucessivamente até n. 
Por convenção, o fatorial de 0 é dado por 0! = 1. 
Números Harmônicos
» Clique nas abas para saber mais sobre o assunto
nn 
33 
 Série Harmônica Formulação Matemática
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 6/28
De posse das ferramentas matemáticas descritas, algoritmos podem ser projetados para solucionar
inúmeras classes de problemas. Em geral, espera-se que o projeto de algoritmo seja dotado de
múltiplas qualidades. Depois da precisão de funcionamento, a característica mais relevante de um
algoritmo é a sua eficiência. Um algoritmo pode ser avaliado sob dois tipos de medidas de eficiência:
eficiência de tempo – indicando a rapidez com que o algoritmo é executado, e eficiência de espaço –
indicando quanta memória extra ele usa (LEVITIN, 2012). 
Nos primórdios da computação eletrônica, ambos os recursos – tempo e espaço – eram muito
escassos. No entanto, com meio século de constantes inovações tecnológicas, a velocidade e o
tamanho da memória do computador foram aprimorados em muitas ordens de magnitude.
Atualmente, a quantidade de espaço extra exigida por um algoritmo não costuma ser tão crítica,
considerando a ressalva da diferença de desempenho existente entre a memória principal (mais
rápida), a memória secundária (mais lenta) e o cache (muito mais rápida). Em contrapartida, a
eficiência relativa ao tempo de execução não evoluiu na mesma proporção. Além disso, diversas
pesquisas apontaram que, para a maioria dos problemas, é possível obter progressos muito mais
significativos em termos de velocidade de execução do que de espaço utilizado. Portanto, a análise
tradicional de desempenho de algoritmos passou a se concentrar principalmente na eficiência do
tempo, embora a estrutura analítica que fundamenta essa análise também seja aplicável à análise da
eficiência em termos de espaço (SEDGEWICK; WAYNE, 2011). 
A avaliação da eficiência de tempo de um algoritmo é comumente feita com base no número de
operações básicas efetuadas em detrimento do número de unidades de tempo necessárias para a
sua execução. Inicialmente, é preciso considerar que a maioria dos programas – se não todos – tem
o seu tempo de execução atrelado ao tamanho do problema a ser resolvido – o que caracteriza a
dificuldade computacional associada à tarefa designada a ele. Em geral, o tamanho do problema
corresponde ao tamanho da entrada fornecida ao programa ou a um valor informado como
argumento. Intuitivamente, é possível afirmar que o tempo de processamento de um algoritmo deve
crescer proporcionalmente ao tamanho do problema. A questão-chave, portanto, é determinar quanto
o tempo de processamento cresce à medida que a dimensão do problema aumenta. Em outras
palavras, o objetivo em uma análise de eficiência de um algoritmo é descrever uma relação ou função
f(n) do seu tempo de execução com o tamanho n do problema a ser resolvido. Essa função é
conhecida como função de custo ou função de complexidade (FEOFILOFF, 2013). 
VOCÊ QUER LER?
Para valores suficientemente pequenos de n (entrada do algoritmo), qualquer algoritmo custa
pouco para ser executado, mesmo os algoritmos ineficientes. Em outras palavras, a escolha
do algoritmo não é um problema crítico para problemas de tamanho pequeno. Logo, a análise
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 7/28
de algoritmos é realizada para valores grandes de n . Para isso, considera-se o
comportamento de suas funções de custo para valores grandes de n , isto é, estuda-se o
comportamento assintótico das funções de custo. O comportamento assintótico de ƒ(n)
representa o limite do comportamento do custo quando n cresce (ZIVIANI, 1999). 
As principais classes de problemas computacionais apresentam uma das seguintes funções de
complexidade (ZIVIANI, 1999): 
Constante f(n) = 1 . Algoritmos desta classe não têm o seu desempenho afetado pelo tamanho
da entrada. Neste caso, as instruções do algoritmo são executadas um número fixo de vezes.
Logarítmica f(n) = log(n) . Este tempo de execução descreve algoritmos cujo funcionamento é
baseado na conversão do problema original em problemas menores.
Linear f(n) = n . Algoritmos desta classe, em geral, realizam alguma operação sobre cada
elemento da entrada. Para cada acréscimo no tamanho da entrada, o tempo de execução
aumenta correspondentemente.
f(n) = nlog(n) . A eficiência de algoritmos que implementam a estratégia de dividir e conquistar
são tipicamente descritos por essa função de complexidade. Nesta estratégia, o problema é
fracionado em instâncias menores (etapa de dividir), cada instância é resolvida de forma
independente e, na sequência, as soluções são combinadas para gerar a solução do problema
original (etapa de conquistar).
Quadrática f(n) = n . Algoritmos com essa complexidade processam os dados da entrada, em
geral, aos pares. É comum apresentarem um aninhamento de laços de execução, ou seja, um
laço sendo executado dentro de outro laço.
Cúbica f(n) = n . Algoritmos desse tipo são geralmente utilizados apenas em problemas de
pequeno porte. Isso porque programas que apresentam essa ordem de crescimento, em geral
são compostos de três laços aninhados usados para alguma operação envolvendo todas as
triplas de n elementos.
Exponencial f(n) = c , c > 1 . Algoritmos com essa função de complexidade não têm
aplicabilidade em problemas práticos. Isso porque eles implementam uma estratégia de força
bruta (avaliar todas as soluções possíveis) para resolver um problema.
Gráfico 1 – Hierarquia assintótica de funções
2 
3 
n 
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 8/28
Fonte: MILLER e RANUM, 2020. 
#PraCegoVer : O gráfico, todo em preto, apresentaa representação de seis
funções: exponencial, cúbica, quadrática, n log n , n , log n . Horizontalmente
aparecem os números: 0, 2, 4, 6, 8 e 10. Verticalmente aparecem os números 0,
10, 20, 30, 40 e 50. A função exponencial se origina na vertical um pouco acima
do valor 0 e segue em um arco crescente, sem passar horizontalmente o valor 2
e atingindo verticalmente o valor 50. A função cúbica se origina no valor 0 do
gráfico e segue também em crescente, chegando perto do valor 4 horizontal e
atingindo o valor 50 vertical. A função quadrática sai do valor 0 do gráfico e
forma um arco crescente chegando na metade entre os valores 6 e 8
horizontais e ao valor 50 horizontal. A função n log n sai da linha horizontal do
gráfico entre os valores 0 e 2, em um leve arco, quase reto, e segue
verticalmente atingindo o valor 10 horizontal e um pouco acima do valor 20
vertical. A função n sai do valor 0 do gráfico e segue em linha reta atingindo o
valor 10 horizontal e valor e valor 10 vertical. A função log n sai do valor 0 do
gráfico, segue em linha reta até o valor 10 horizontal e atinge um valor pouco
acima de 0 na linha vertical. 
Outros algoritmos podem apresentar funções de complexidades ainda mais caras
computacionalmente. Esse é o caso de algoritmos com complexidade fatorial
f(n) = n!
#PraCegoVer : Fórmula matemática da função n fatorial.
ou ainda,
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 9/28
f(n) = n 
#PraCegoVer : Fórmula matemática da função n elevado a n.
A comparação de todas essas funções é geralmente feita com base em seu comportamento
assintótico . Isso quer dizer que a comparação só leva em conta a tendência de crescimento das
funções e não os seus valores absolutos. Logo, fatores multiplicativos e valores pequenos passados
como argumentos são desprezados. O Gráfico 1 apresenta um gráfico comparativo da hierarquia
assintótica das principais funções. 
O Quadro 1 ilustra as diferentes taxas de crescimento observadas entre várias funções de
complexidade. As funções expressam o tempo de execução para múltiplos tamanhos de entrada. É
possível observar uma explosiva taxa de crescimento para as funções de complexidade exponencial.
Em contrapartida, um algoritmo linear é capaz de executar um milhão de operações em apenas um
segundo. 
Quadro 1 – Comparação de funções polinomiais e exponenciais de complexidade de tempo
TAMANHO DA ENTRADA N
FUNÇÃO DE
COMPLEXIDADE
10 20 30 40 50 60
n
n
0,00001
seg.
0,00002
seg.
0,00003
seg.
0,00004
seg.
0,00005
seg.
0,00006
seg.
n 2
0,0001
seg.
0,0004
seg.
0,0009
seg.
0,0016
seg.
0,0025
seg.
0,0036
seg.
n 3
0,001
seg.
0,008
seg.
0,027
seg.
0,064
seg.
0,125
seg.
0,216
seg.
n 5 0,1 seg. 3,2 seg.
24,3
seg.
1,7 min. 5,2 min.
13,2
min.
0 001 17 9 12 7 35 7 366
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 10/28
Fonte: GAREY e JOHNSON, 1979, p. 7.
VAMOS PRATICAR? 
Para exemplificar alguns conceitos apresentados, vamos considerar o algoritmo para
encontrar o maior elemento dentre os n elementos de A = { e , e , …, e } informados. O
Algoritmo é composto de 5 passos:
1. Definir um contador cont contendo o valor n e um outro max com valor e .
2. Se cont tiver valor 0, o algoritmo deve terminar. 
3. Se e ≤ max , ir para o passo 5.
4. Atualizar o valor de max para e .
5. Decrementar cont em 1 e voltar para o passo 2.Vamos tomar f como a função de
complexidade tal que f(n) é o número de comparações entre os elementos de A. Como A
tem n elementos, serão feitas n – 1 comparações até que o maior elemento seja localizado.
Portanto, f(n) = n – 1 , para n > 0.
2 n
0,001
seg.
1,0 seg.
17,9
min.
12,7
dias
35,7
anos
366
séculos
3 n
0,59
seg.
58 min.
6,5
anos
3,855
séculos
2x10 
séculos
8 1,3 x 10
séculos
13
1 2 n 
n 
cont 
cont 
1.2 Complexidade de algoritmo de ordenação por inserção direta
A análise de um algoritmo geralmente conta com algumas operações elementares e, em muitos
casos, apenas uma operação elementar. A medida de custo ou medida de complexidade expressa o
crescimento assintótico da operação considerada. Além disso, essa análise é geralmente feita tendo
como base um modelo independente de máquina, isto é, a expressão de consumo de tempo é feita
abstraindo particularidades como linguagem de programação, detalhes de implementação e o
computador utilizado. De acordo Skienka (2008) esse modelo de computação, conhecido como RAM
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 11/28
(do inglês Random Access Machine , ou Máquina de Acesso Aleatório, em português), assume os
seguintes custos associados às operações executadas por um computador:
Cada operação simples (operações aritméticas, comparações e invocações de métodos) custa
exatamente um passo de tempo.
Laços ( loops ) e subrotinas não são consideradas operações simples. Ao contrário, eles são a
composição de múltiplas operações de um passo de tempo. De fato, não seria coerente afirmar
que uma operação de ordenação demanda apenas um passo de tempo, uma vez que a
ordenação de 1.000.000 elementos certamente exige um tempo computacional muito maior do
que a ordenação de apenas 10 elementos. Assim, o tempo necessário para executar um laço ou
para executar um subprograma depende do número de iterações do laço ou da natureza
específica do subprograma.
Cada acesso à memória requer exatamente um passo de tempo. Além disso, assume-se que há
tanta memória disponível quanto necessária. O modelo RAM não faz distinção se um item está
em cache ou em disco.
Por meio do modelo RAM, o tempo de execução pode ser medido por meio da contagem do número
de passos que um algoritmo executa a fim de resolver uma dada instância de um problema. A partir
dessa contagem, o comportamento assintótico do algoritmo pode ser compreendido e,
consequentemente, sua função de complexidade pode ser expressa. 
No entanto, para fins de comparação de funções, o conceito de dominação assintótica deve ser
empregado. Uma função f(n) domina assintoticamente outra função g(n) se existem duas constantes
positivas c e m tais que, para n ≥ m , tem-se 
|g(n)| ≤ c · |f(n)|
#PraCegoVer : Expressão matemática indicando que o módulo da função g de n
é menor ou igual ao produto da constante c com o módulo da função f de n. 
O significado dessa definição pode ser graficamente expresso conforme apresentado no Gráfico 2.
Pode-se observar que a partir de um ponto m , todo valor de f(n) é maior que g(n) em módulo,
considerando uma constante positiva c multiplicando f(n) . 
Gráfico 2 – Dominação assintótica da função f sobre a função g
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 12/28
Fonte: CORMEN, 2012, p. 45.
#PraCegoVer : A imagem demonstra um gráfico com eixo horizontal n e um
eixo vertical não especificado. Há duas linhas representando a função f de n
sobre a função g de n . A função f de n é uma linha saindo do primeiro terço do
eixo vertical e ascendendo de forma mais ou menos constante, porém não em
linha reta, ao longo dos eixos. A g de n é representada por uma linha saindo do
eixo vertical, um pouco acima da função n . Primeiro ela realiza um arco de
queda, depois um arco de subida, no qual intersecciona a função f , novamente
um arco de queda quando intersecciona novamente a função f e depois
ascende de forma mais u menos constante, porém abaixo da linha da função f .
Na terceira intersecção entre as funções, há uma linha pontilhada até o eixo
horizontal n , sinalizada pela letra m .
Para expressar que um função f(n) domina assintoticamente outra função g(n) , uma notação
conhecida comoO (do inglês big-oh , ou grande O, em português) é utilizada. Neste caso, a
dominação assintótica seria escrita como g(n) = O(f(n)) (pronuncia-se “oh de f de n”), o qual deve ser
entendido como g(n) tendo a ordem de no máximo f(n) . Em outras palavras, f(n) é um limite
assintótico superior para g(n) . Assim, quando é dito que o tempo de execução T(n) de um programa
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 13/28
VOCÊ SABIA?
A notação O foi introduzida em 1894 por Paul Bachmann em seu livro Analytische
Zahlentheorie, cuja tradução livre seria Teoria dos Números Analíticos . De acordo com Knuth
(1997), essa notação possibilita a substituição do sinal de aproximação “≈” pelo de igualdade
“=”, além de quantificar o grau de precisão.
Como indicado por Tenenbaum, Langsam e Augesntein (1989), as seguintes operações podem ser
realizadas com a notação O:
#PraCegoVer : Sequênciade sete operações que podem ser executadas com a
notação O . A primeira indica que f de n é igual a O de f de n. A segunda,
oproduto de uma constante c por O de f de n é igual a O de f de n. Na terceira,a
soma de de O de f de n com O de f de n é igual a O de f de n. Na quarta, O deO
de f de n é igual a O de f de n. Naquinta, a soma de O de f de n com O de g de n
é igual a O do máximo entre f den e g de n. Na sexta, o produto de O de f de n e
O de g de n é igual a O doproduto de f de n com g de n. Na sétima, o produto de
f de n com O de g de n éigual a O do produto de f de n com g de n. 
é O(n2) , isso significa que existem constantes c e m tais que, para valores de n maiores ou iguais a
m , T(n) ≤ cn2 . Em geral, a notação O(f(n)) pode ser usada em qualquer intervalo onde f(n) é uma
função de um número inteiro n , indicando assim que ela representa uma quantidade que não é
explicitamente conhecida, mas cuja magnitude não é muito grande (KNUTH, 1997).
Teste seus conhecimentos
Atividade não pontuada.
Domínio assintótico de f(n) = 6n sobre g(n) = 100n + 300
» Clique nas abas para saber mais sobre o assunto
2 
 
Dominação Algébrico Dominação Gráfica
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 14/28
Os algoritmos de ordenação constituem bons exemplos de como é possível resolver problemas
através de recursos e técnicas computacionais. A atividade de colocar itens em ordem está presente
na maioria das aplicações onde os objetos armazenados têm que ser pesquisados e recuperados,
como dicionários, índices de livros, tabelas e arquivos. Como existem várias abordagens para se
rearranjar um conjunto de elementos em ordem ascendente ou descendente, a avaliação do
desempenho de cada um desses algoritmos oferece um cenário amplo para aplicação das técnicas
de análise de comportamento assintótico.
VOCÊ SABIA?
A regra da soma O(f(n)) + O(g(n)) pode ser usada para calcular o tempo de execução de uma
sequência de trechos de programas. Suponha três trechos de programas cujos tempos de
execução são 
O(n), O(n ) e O(nlog(n))
#PraCegoVer: Notação O para as funções linear, quadrática e n logaritmo de n.
O tempo de execução dos dois primeiros trechos é 
O(max(n, n ))
#PraCegoVer: Notação O para o máximo entre as funções linear e quadrática.
que é O(n ) . O tempo de execução de todos os três trechos é, portanto, 
O(max(n , nlog(n)))
#PraCegoVer: Notação O para o máximo entre as funções quadrática e n
logaritmo de n.
que é O(n ). 
2 
2 
2 
2 
2 
Os algoritmos sempre operam sobre os registros de um arquivo. Apenas uma parte do registro,
chamada chave , é utilizada para controlar a ordenação. Apesar de outros elementos também
poderem compor um registro, eles não influenciam no processo de ordenação, salvo pelo fato de que
a chave a qual estão associados nunca é alterada. A escolha do tipo de dados a ser empregado na
definição da chave é arbitrária. Porém, devem ser utilizados tipos de dados sobre os quais exista
alguma regra de ordenação bem definida. Este é o caso dos tipos numéricos e alfabéticos. Outro
conceito importante associado ao processo de ordenação é o de estabilidade. Um método de
ordenação é dito estável se a ordem relativa dos itens com chaves iguais se mantém inalterada
durante o rearranjo dos elementos.
Tipos de Algoritmos de Ordenação
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 15/28
» Clique nas setas ou arraste para visualizar o conteúdo
Um algoritmo comumente usado para ordenar cartas em jogos de baralho funciona considerando as
cartas uma por vez e inserindo cada carta em seu devido lugar entre aquelas já analisadas.
Conforme descrito por Cormen (2012), este processo tem início com uma das mãos vazia (esquerda,
por exemplo) e as cartas viradas para baixo na mesa. Em seguida, removemos uma carta de cada
vez da mesa e a inserimos na posição correta na mão esquerda. Para encontrar a posição correta
para uma carta, comparamos com cada uma das cartas já na mão, da direita para a esquerda. Em
todos os momentos, as cartas seguradas na mão esquerda são classificadas. Nesse processo, a
ordenação já estabelecida na mão é mantida. Esse algoritmo é conhecido como ordenação por
inserção direta . 
A Figura 1 apresenta um exemplo dos passos executados pela ordenação por inserção direta sobre
um conjunto a = { 5, 2, 4, 6, 1, 3 }. A estrutura de dados usada para armazenar o conjunto a é um
vetor. Em cada passo, o retângulo escuro armazena a chave a ter sua correta posição encontrada. A
busca por essa posição acontece da direita para a esquerda. Enquanto a chave a ser ordenada
(retângulo preto) é menor do que as chaves à sua esquerda (retângulos cinza), o valor é deslocado
neste sentido. Naturalmente, os deslocamentos não ultrapassam os limites do vetor. Essas
comparações ficam bem evidentes no passo (d), quando a chave de valor 1 é comparada com os
quatro elementos à sua esquerda até alcançar a extremidade do vetor. Ao término do processo –
após a última finalizar o processo de busca pela posição correta – o vetor resultante contém todas as
chaves em ordem ascendente.
Tipo de Acesso: Na ordenação interna qualquer registro pode ser imediatamente
acessado.
ORDENAÇÃO EXTERNA
Quando o arquivo a ser ordenado não cabe na memória principal e, por isso, tem
que ser armazenado em fita ou disco. 
 Tipo de Acesso: Na ordenação externa os registros são acessados
sequencialmente ou em blocos.
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 16/28
Figura 1 – Operações executadas pela ordenação por inserção direta. Fonte: CORMEN, 2012, p. 18. 
#PraCegoVer : Sequência de seis imagens descrevendo o passo a passo de
ordenação de um vetor com os elementos 5, 2, 4, 6, 1 e 3 pelo método de
ordenação por inserção direta. Na primeira, o 2 trocado com o 5, na segunda o
4 é trocado com o 5, na terceira o 6 permanece na sua posição, na quarta o 1 é
deslocado para primeira posição, na quinta o 3 é trocado com o 4 e na sexta o
vetor se encontra ordenado. 
O pseudo-código a seguir detalha o algoritmo de ordenação por inserção direta. 
Algoritmo de Ordenação Direta: 
Entrada: Vetor A de n posições 
 Saída: Vetor A com as chaves em ordem crescente 
1. para j = 2 até n faça 
 2. chave = A[ j ] 
3. i = j – 1 
4. enquanto i > 0 e A[ i ] > chave faça 
 5. A[ i + 1 ] = A[ i ] 
6. i = i – 1 
7. fim enquanto 
 8. A[ i + 1 ] = chave 
9. fim para
Fazendo uma correspondência entre o algoritmo apresentado e a analogia com a ordenação de
cartas de baralho, o índice j representa a carta que está sendo comparada com as demais, a fim de
localizar a sua correta posição. Levando em conta a Figura 4, o índice j correspondeao retângulo
preto da carta corrente. Observe que o valor armazenado neste índice a cada iteração do laço mais
externo é atribuído a uma variável chave . O laço mais interno (linhas 4 a 7) é responsável por fazer
as comparações da chave com os demais valores à esquerda. Na prática, cada chave vai ser
comparada com um subvetor à esquerda, delimitado pelos índices 1 e j – 1 . O lado direito da chave,
o subvetor de índice variando de j + 1 a n , corresponde às cartas que ainda se encontram na mesa e
precisam ser ordenadas.
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 17/28
Convenções de Pseudo-código
» Clique nas abas para saber mais sobre o assunto
Considerando o modelo RAM para descrição do comportamento assintótico da ordenação por
inserção direta, observamos que a operação elementar do algoritmo é a comparação entre chaves. O
cenário menos custoso computacionalmente – menor número de comparações entre chaves – para o
algoritmo acontece quando o vetor informado já se encontra ordenado. Em contrapartida, o caso em
que será demandado o maior número de comparações se dá quando o vetor se encontra ordenado
inversamente. Ambas situações são conhecidas como melhor e pior caso do algoritmo,
respectivamente. 
Qualquer que seja o vetor de entrada a ser ordenado via inserção direta, o laço mais interno (linhas 4
a 7) será executado n – 1 vezes. No entanto, o número de comparações realizadas por esse laço vai
depender de quão ordenado o vetor original se encontra. No melhor caso, o laço mais interno
executará apenas uma comparação, tendo em vista que nesta única operação a chave identifica que
já se encontra na posição correta – o teste A [ i ] > chave falha na primeira tentativa de comparação.
Logo, no melhor caso, o algoritmo vai realizar
C(n) = ( n - 1) * 1 = n – 1
#PraCegoVer: C de n é igual ao produto de n menos 1 por 1, que por sua vez é
igual a n menos 1.
Expressão matemática indicando que o número de comparações executadas pelo algoritmo é n - 1]
comparações. Considerando que n – 1 ≤ n para todo n > 0, concluímos que o melhor caso do
algoritmo é dominado assintoticamente pela função
f(n) = n
#PraCegoVer: Função f de n é igual a n: Expressão matemática da função f de
n.
Isso equivale a dizer que complexidade do algoritmo no melhor caso é O(n) . 
Por outro lado, quando o algoritmo recebe como entrada um vetor inversamente ordenado, o laço
mais interno ainda será executado n - 1 vezes. Porém, o número de comparações realizadas por ele
será consideravelmente maior. De fato, a primeira chave a ser posicionada efetuará 1 comparação, a
segunda chave fará 2 comparações, a terceira chave, 3 comparações e assim sucessivamente, até
que a última chave finalize as suas n - 1 comparações. Mais precisamente, o número de
comparações total C(n) será dado por
 
Blocos de código Laços Vetores Retornos
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 18/28
f(n) = n
#PraCegoVer: Expressão matemática para o número de comparações no pior
caso. C de n é igual à soma de 1 mais 2 mais 3 e a soma se repete até o limite
de n menos 1. Essa soma é dada por n ao quadrado menos n sobre 2.
Isso quer dizer que o algoritmo de ordenação por inserção direta é dominado assintoticamente por
uma função quadrática em seu pior caso. Aplicando as operações da notação O sobre essa função,
obtemos que
#PraCegoVer: Cálculo da complexidade do pior caso da ordenação por
inserção direta. Portanto, o pior caso da ordenação por inserção direta
apresenta complexidade O(n ).
Teste seus conhecimentos
Atividade não pontuada.
VAMOS PRATICAR? 
Para reforçar o funcionamento do algoritmo de ordenação por inserção direta, vamos
apresentar a evolução da ordenação de um vetor com os seguintes elementos { O, R, D, E,
N, A }:
Ao término do processo, o vetor ordenado é { A, D, E, N, O, R }.
2 
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 19/28
1.3 Análise de algoritmos de ordenação bubble sort
Os sons que escutamos em nosso dia a dia são formados por uma junção complexa de ondas,
formadas pelas oscilações complexas de cada fonte que emite esses sons. Para complicar ainda
mais a questão, os sons que normalmente ouvimos são compostos por uma somatória de diferentes
sons, como já vimos na mixagem para cinema. Sendo assim, é necessário queUm dos métodos de
ordenação mais conhecidos pela simplicidade de ser entendido e programado é conhecido como
bubble sort (ordenação por bolha). Apesar de ser facilmente implementado, ele é tido como o
método menos eficiente dentre os conhecidos. A ideia básica da ordenação via bolha é percorrer um
vetor X sequencialmente várias vezes. Cada passagem consiste em comparar cada elemento com o
seu sucessor [ #PraCegoVer : Comparação entre o valor armazenado na posição i do vetor X com o
valor da posição i + 1] e trocar os dois elementos que não estiverem na ordem correta. Tenembaum,
Langsam e Augenstein (1999) descreveram um exemplo de execução da ordenação pelo método da
bolha sobre um vetor X composto dos seguintes elementos: tenhamos diversos instrumentos
diferentes para visualização dessas ondas. Em linhas gerais, os parâmetros que podemos visualizar
são: duração , frequência e intensidade . Cada um desses parâmetros pode ser visualizado de
uma forma diferente e apresenta questões específicas que são de nosso interesse, conforme mostra
o quadro a seguir:
(X[ i ] com X[ i + 1])
#PraCegoVer : Comparação entre o valor armazenado na posição i do vetor X
com o valor da posição i + 1
e trocar os dois elementos que não estiverem na ordem correta. Tenembaum, Langsam e Augenstein
(1999) descreveram um exemplo de execução da ordenação pelo método da bolha sobre um vetor X
composto dos seguintes elementos:
25 57 48 37 12 92 86 33 
As seguintes comparações são feitas na primeira passagem:
X[ 1 ] com X[ 2 ] (25 com 57) nenhuma troca
X[ 2 ] com X[ 3 ] (57 com 48) troca
X[ 3 ] com X[ 4 ] (57 com 37) troca
X[ 4 ] com X[ 5 ] (57 com 12) troca
X[ 5 ] com X[ 6 ] (57 com 92) nenhuma troca
X[ 6 ] com X[ 7 ] (92 com 86) troca
X[ 7 ] com X[ 8 ] (92 com 33) troca
Terminada a primeira passagem pelo vetor, as chaves estarão na seguinte ordem:
25 48 37 12 57 86 33 92 
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 20/28
Importante observar que após a primeira iteração do algoritmo, o maior elemento (neste caso, 92) fica
alocado em sua posição correta. O método é conhecido por ordenação por bolha já que cada número
“borbulha” lentamente para a posição correta. Depois da segunda iteração, a ordem das chaves é a
seguinte:
25 37 12 48 57 33 86 92 
Após esta iteração, o elemento 86 ficou posicionado na segunda posição mais alta. Como cada
iteração rearranja um novo elemento em sua posição correta, um vetor de n chaves vai demandar n -
1 iterações até que a ordenação finalize. Neste exemplo, o conjunto completo de iterações é
apresentado no Quadro 2. As chaves em negrito foram empurradas para o fim do vetor a cada
passada: bolhas. Nas duas últimas iterações, o vetor não sofre mais modificações já que se encontra
ordenado.
Quadro 2 – Iterações executados pelo algoritmo bubble sort
ITERAÇÃO CHAVES
0 25 57 48 37 12 92 86 33
1 25 48 37 12 57 86 33 92
2 25 37 12 48 57 33 86 92
3 25 12 37 48 33 57 86 92
4 12 25 37 33 48 57 86 92
5 12 25 33 37 48 57 86 92
6 12 25 33 37 48 57 86 92
7 12 25 33 37 48 5786 92
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 21/28
Fonte: TENEMBAUM, LANGSAM e AUGENSTEIN, 1999, p. 425.
O pseudo-código a seguir detalha o algoritmo de ordenação pelo método da bolha. O laço externo é
responsável por controlar o limite mais à direita a ser percorrido pela bolha em cada iteração. Já o
laço interno (linhas 2 a 8) implementa a movimentação da bolha. As chaves são comparadas duas a
duas (linha 3) e sempre que a chave à esquerda for maior do que a chave à direita ambas têm suas
posições trocadas entre si (linhas 4 a 6).
Algoritmo Bubble Sort: 
Entrada: Vetor A de n posições 
 Saída: Vetor A com as chaves em ordem crescente 
1. para i = n até 1 faça 
 2. para j = 1 até i - 1 faça 
 3. se A[ j ] > A [ j + 1] então 
 4. temp = A[ j + 1 ] 
5. A[ j + 1 ] = A[ j ] 
6. A[ j ] = temp 
7. fim se 
 8. fim para 
 9. fim para
se A índice j é menor que A índice j mais 1. Quando essa condição for verdadeira, três comandos são
executados. Uma variável temp recebe o valor de A índice j mais 1, A índice j mais 1 recebe o valor
de A índice j e, finalmente A índice j recebe o valor armazenado na variável temp. 
 
Considerando a eficiência desse método de ordenação, a operação elementar também é a
comparação. Neste caso, para um vetor de n posições, serão executadas n – 1 comparações na
primeira iteração, n - 2 comparações na segunda iteração e assim sucessivamente, até que a última
iteração execute apenas uma comparação (entre as chaves posicionadas nas duas primeiras
posições do vetor). Logo, o número de comparações C(n) após o término da execução do algoritmo é
dado pela soma
#PraCegoVer : Cálculo do número de comparações C de n realizadas pelo
método da bolha. C de n é igual ao somatório de i variando de 1 até n menos 1
sobre a variável i . Esse somatório corresponde à razão de n ao quadrado
menos n sobre 2.
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 22/28
Isso quer dizer que a ordenação pelo método da bolha é dominada assintoticamente por uma função
quadrática. Importante ainda perceber que, independentemente de como as chaves estão dispostas
no vetor informado como entrada para o algoritmo, o número de comparações executadas será o
mesmo. Em outras palavras, tanto o melhor como o pior caso do método da bolha terão a mesma
complexidade, que é dada por
#PraCegoVer : Cálculo da complexidade do pior e melhor caso da ordenação
pelo método da bolha. O de meio de n ao quadrado somado a O de menos meio
de n é igual a O do máximo entre meio de n ao quadrado e menos meio de n
que é igual a O de n ao quadrado.
VAMOS PRATICAR? 
Embora o método de ordenação pela bolha seja reconhecidamente ineficiente, alguns
aprimoramentos podem ser feitos no algoritmo. Considerando o pseudo-código
apresentado do método, tente introduzir a seguinte modificação que pode causar uma
melhoria no desempenho do algoritmo: 
No exemplo apresentado neste tópico, o vetor foi ordenado após cinco iterações, tornando
as duas últimas iterações desnecessárias. Para eliminar as passagens desnecessárias,
altere o pseudo-código do algoritmo de forma que ele detecte o fato do vetor já se
encontrar ordenado durante o processo de rearranjo das chaves. 
Com a introdução dessa modificação, qual a nova complexidade do melhor caso, ou seja,
quando o vetor informado já se encontrar ordenado?
1.4 Ordem assintótica: notação ômega
Assim como a notação O provê um limite assintótico superior para uma função, uma segunda
notação – a notação Ω (ômega) – descreve o limite assintótico oposto, isto é, o limite inferior para
uma função. Logo, para uma dada função g(n) , a notação f(n) = Ω(g(n)) (pronuncia-se “ômega de g
de n”) significa que g(n) é um limite assintótico inferior para f(n) . Isso quer dizer que existem
constantes positivas c e m tais que
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 23/28
0 ≤ cg(n) ≤ f(n)
#PraCegoVer : Expressão matemática indicando uma sequência de
desigualdades: 0 é menor ou igual ao produto de c por g de n, que por sua vez
é menor ou igual ao f de n.
para todo n ≥ m .
Limites Assintóticos Inferiores
» Clique nas setas ou arraste para visualizar o conteúdo
#PraCegoVer : Quatro expressões matemáticas exemplificando o conceito de
limites assintóticos inferiores. A primeira relaciona o cubo de n, a segunda a
diferença entre o quadrado de n e 2 n , a terceira está relacionada a n logaritmo
de n e a quarta a 100n.
Um exemplo de definição de um limite assintótico inferior foi apresentado por Kleinberg e Tardos
(2006) aplicado à função f(n) = 4 n - 3. Enquanto a definição de um limite superior envolve
incrementar os valores dos termos de f(n) até que seja observado uma constante associada ao termo
dominante, a definição do limite inferior é feita no sentido oposto, ou seja, é preciso reduzir o
tamanho de f(n) até que uma constante seja observada associada ao termo-limite. Logo, pode-se
afirmar que
f(n) = Ω(n)
#PraCegoVer : Notação ômega para indicar que o limite assintótico inferior de f
de n é n.
uma vez que, para todo n ≥ 1, tem-se que
Sim, pois n + 100n ≥ n para todo n.3 3 
f(n) = n – 2n = Ω(n ) ?
Sim, pois como 2n ≤ (½) n para todo n ≥ 4, então n – 2n ≥ n – (½)n = (½)n .
2 2 
2 2 2 2 2 
f(n) = n lg n = Ω(n) ?
Sim, pois n + 100n ≥ n para todo n.3 3 
f(n) = 100 = Ω(n ) ?
Não, pois para todo n > 100c, tem-se 100 < 1/c e, portanto, 100n < (1/c)n .
n 2 
2 
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 24/28
f(n) = 4 n - 3 ≥ n
#PraCegoVer : Expressão matemática indicando que a função f de n é menor ou
igual a n.
O Gráfico 3 apresenta o gráfico das duas funções. 
Gráfico 3 – Gráfico das funções g(n) = n e f(n) = 4n-3
Fonte: ALGOL DEV, 2019. 
#PraCegoVer :Imagem apresentando os gráficos das funções n e 4n menos 3.
Horizontalmente os valores são: 0.5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5, 5.5.
Verticalmente os números são 10, 8, 6, 4, 2. Há duas linhas. A que representa
função n é azul e sai do valor 0, ou seja do ponto de interseção ente a linha
horizontal e vertical e segue, verticalmente, chegando até o último ponto da
linha horizontal e sem passar o valor 6 da linha vertical. Já a linha que
representa a função 4n-3 é vermelha e parte da linha horizontal entre os valores
0.5 e 1. Ela segue verticalmente pelo gráfico chegando próximo ao valor 4 da
linha horizontal e chegando ao último valor da linha vertical. As linhas das
duas funções se interseccionam no valor 1 da linha horizontal. Desta
interseção sai uma linha vermelha pontilhada onde está indicado o valor n ≥ 1. 
VAMOS PRATICAR? 
Considere o seguinte algoritmo de busca sequencial de uma chave k em um vetor X de n
posições:
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 25/28
1. para pos = 1 até n faça
2. se X [ pos ] é igual a k então
3. retorna Busca com Sucesso
4. fim se
5. fim para
6. retorna Busca sem Sucesso
Qual o limite assintótico superior do pior caso do algoritmo? Pode-se afirmar que o seu
limite assintótico inferior é Ω(n )? Justifique. 
Síntese
Neste capítulo, conseguimos ter uma visão dos principais fundamentos matemáticos que dão suporte
ao projeto e à análise de algoritmos computacionais. Os conceitos relacionados ao comportamento
assintótico dos algoritmos, juntamente com o formalismo das notações O e Ω possibilitaram que dois
algoritmos de ordenação interna pudessem ser descritos e avaliados quanto à sua eficiência. Por
meio do cálculo das complexidades de melhor e piorcaso de ambos algoritmos, observou-se que o
desempenho de cada um deles pode variar de acordo com a maneira com que os dados de entrada
estão arranjados. Além disso, o detalhamento das estratégias de ordenação implementadas pelos
dois métodos deu suporte ao desenvolvimento de uma visão mais crítica quanto ao projeto de
algoritmos que atendam a critérios de desempenho adequados para os cenários onde serão
empregados.
SAIBA MAIS
Título : Estruturas de Dados e Algoritmos em Java 
Autores : Roberto Tamassia e Michael T. Goodrich 
2 
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 26/28
Ano : 2011 
Comentário : Leia o capítulo 4, que apresenta mais detalhes a respeito das
ferramentas de análise de algoritmos e fundamentos matemáticos complementares
usados na descrição do comportamento de algoritmos. 
Onde encontrar : Biblioteca Virtual da 
Título : Estruturas de Dados e Algoritmos em Java 
Autores : Roberto Tamassia e Michael T. Goodrich 
Ano : 2011 
Comentário : Leia o capítulo 4, que apresenta mais detalhes a respeito das
ferramentas de análise de algoritmos e fundamentos matemáticos complementares
usados na descrição do comportamento de algoritmos. 
Onde encontrar : Biblioteca Virtual da 
Título : Estruturas de Dados e Algoritmos em Java 
Autores : Roberto Tamassia e Michael T. Goodrich 
Ano : 2011 
Comentário : Leia o capítulo 4, que apresenta mais detalhes a respeito das
ferramentas de análise de algoritmos e fundamentos matemáticos complementares
usados na descrição do comportamento de algoritmos. 
Onde encontrar : Biblioteca Virtual da 
Referências bibliográficas 
BIG Omega Notation. Algol dev ., 2019. Disponível em: < https://algol.dev/en/big-omega-notation/ >.
Acesso em: 07/12/2020. 
https://algol.dev/en/big-omega-notation/
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 27/28
 
CORMEN, T. H. Algoritmos . Rio de Janeiro: Elsevier, 2012. 
 
DIJKSTRA, E. W. A Short Introduction to the Art of Programming , 1971. Disponível em: <
https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF >. Acesso: 06 dez. 2020. 
 
FEOFILOFF, P. Minicurso de Análise de Algoritmos. Instituto Militar de Engenharia – IME, Rio de
Janeiro, 2013. Disponível em: < https://www.ime.usp.br/~pf/livrinho-AA/ >. Acesso: 07/12/2020. 
 
GAREY, M. R., JOHNSON, D. S. Computers and Intractability – A Guide to the Theory NP-
Completeness. New Jersey: Bell Telephone Laboratories Incorporated, 1979. 
 
ASYMPTOTIC notation. Khan Academy , 2019. Disponível em: <
https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-
notation/a/asymptotic-notation >. Acesso: 07 dez. 2020. 
 
KLEINBERG, J., TARDOS, E. Algorithm Design . Boston: Pearson Education, 2006. 
 
KNUTH, D. E. The Art of Computer Programming – Fundamental Algorithms. Boston: Addison-
Wesley, 1997. 
 
LEVITIN, A. A Introduction to the Design and Analysis of Algorithms . New Jersey: Addison-
Wesley, 2012. 
 
MILLER, B., RANUM, D. Problem Solving with Algorithms and Data Structures Using Python.
Pythonds , 2012. Disponível em: <
https://runestone.academy/runestone/books/published/pythonds/AlgorithmAnalysis/BigONotation.html
>. Acesso: 07 dez. 2020. 
 
SEDGEWICK, R., WAYNE, K. Algorithms . Boston: Addison-Wesley, 2011. 
 
SKIENKA, S. S. The Algorithm Design Manual . New York: Springer, 2008. 
 
TENENBAUM, A. A., LANGSAM, Y., AUGESNTEIN, M. J . Data Structures Using C . New York:
McGraw-Hill, 1999. 
 
ZIVIANI, N. Projeto de Algoritmos com Implementações em Pascal e C . São Paulo: Pioneira
Informática, 1999. 
https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF
https://www.ime.usp.br/~pf/livrinho-AA/
https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation
https://runestone.academy/runestone/books/published/pythonds/AlgorithmAnalysis/BigONotation.html
08/09/2022 22:03 Unidade 1 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_1/ebook/index.html?redirect=1 28/28