Mathematics">
Análise de Algoritmos
Análise de Algoritmos
Análise de Algoritmos
ANÁLISE DE ALGORITMOS
UNIDADE 1 – ALGORITMOS E
ORDENAÇÃO EM MEMÓRIA
PRIMÁRIA
Autor: Thiago Nascimento Rodrigues
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.
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNLzf… 1/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
Bons estudos!
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:
2
1=1
2
1+3=2
2
1+3+5=3
2
1+3+5+7=4
2
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
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNLzf… 2/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
2
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:
2
Caso base: Como 1 = 1 , temos que P (1) é válido.
2 2
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).
» Propriedade distributiva
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.
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNLzf… 4/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
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
p = n ( n - 1)( n – 2) … (1)
nn
#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
33
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
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).
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNLzf… 5/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
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).
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNLzf… 6/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
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.
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNLzf… 7/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
f(n) = n!
#PraCegoVer : Fórmula matemática da função n fatorial.
ou ainda,
n
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.
TAMANHO DA ENTRADA N
FUNÇÃO DE
10 20 30 40 50 60
COMPLEXIDADE
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNLzf… 8/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
5 24,3 13,2
n 0,1 seg. 3,2 seg. 1,7 min. 5,2 min.
seg. min.
8 1,3 x 10
n 0,59 6,5 3,855 2x10 13
3 58 min.
seg. anos séculos séculos
séculos
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
1 2 n
Algoritmo é composto de 5 passos:
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.
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)|
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 10/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 11/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
2
Domínio assintótico de f(n) = 6n sobre g(n) = 100n + 300
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:
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 12/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
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
2
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 é
2
O(max(n, n ))
#PraCegoVer: Notação O para o máximo entre as funções linear e quadrática.
2
que é O(n ) . O tempo de execução de todos os três trechos é, portanto,
2
O(max(n , nlog(n)))
#PraCegoVer: Notação O para o máximo entre as funções quadrática e n
logaritmo de n.
2
que é O(n ).
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
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 13/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
ordenação é dito estável se a ordem relativa dos itens com chaves iguais se mantém inalterada
durante o rearranjo dos elementos.
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 –
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 14/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
após a última finalizar o processo de busca pela posição correta – o vetor resultante contém todas as
chaves em ordem ascendente.
Figura 1 – Operações executadas pela ordenação por inserção direta. Fonte: CORMEN, 2012, p. 18.
Convenções de Pseudo-código
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 15/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
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
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
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 16/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
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 }.
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:
25 57 48 37 12 92 86 33
As seguintes comparações são feitas na primeira passagem:
25 48 37 12 57 86 33 92
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.
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 18/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
ITERAÇÃO CHAVES
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).
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 19/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
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.
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 20/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
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?
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 .
3 3
Sim, pois n + 100n ≥ n para todo n.
f(n) = n 2 – 2n = Ω(n 2 ) ?
2 2 2 2 2
f(n) = n lg n = Ω(n) ?
Sim pois como 2n ≤ (½) n para todo n ≥ 4 então n 2n ≥ n (½)n = (½)n
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 21/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
f(n) = n lg n = Ω(n) ?
Sim, pois como 2n ≤ (½) n para todo n ≥ 4, então n – 2n ≥ n – (½)n = (½)n .
3 3
Sim, pois n + 100n ≥ n para todo n.
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
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.
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 22/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
VAMOS PRATICAR?
Considere o seguinte algoritmo de busca sequencial de uma chave k em um vetor X de n
posições:
4. fim se
5. fim para
Qual o limite assintótico superior do pior caso do algoritmo? Pode-se afirmar que o seu
2
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 pior caso 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
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 23/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
algoritmos que atendam a critérios de desempenho adequados para os cenários onde serão
empregados.
SAIBA MAIS
Referências bibliográficas
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 24/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
BIG Omega Notation. Algol dev ., 2019. Disponível em: < https://algol.dev/en/big-omega-notation/ >.
Acesso em: 07/12/2020.
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.
GAREY, M. R., JOHNSON, D. S. Computers and Intractability – A Guide to the Theory NP-
Completeness. New Jersey: Bell Telephone Laboratories Incorporated, 1979.
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.
TENENBAUM, A. A., LANGSAM, Y., AUGESNTEIN, M. J . Data Structures Using C . New York:
McGraw-Hill, 1999.
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 26/27
27/02/2023, 16:56 Unidade 1 - Análise de algoritmos
https://student.ulife.com.br/ContentPlayer/Index?lc=IyP2HINt7kgtyq4uw8F3sw%3d%3d&l=I7aJAzLzUh2p9R%2fLCcea3w%3d%3d&cd=bezNL… 27/27