Unidade 3 - Análise de algoritmos

Prévia do material em texto

08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 1/26
ANÁLISE DEANÁLISE DE
ALGORITMOS ALGORITMOS 
UNIDADE 3 –UNIDADE 3 –
RECORRÊNCIAS ERECORRÊNCIAS E
COMPLEXIDADE DECOMPLEXIDADE DE
ALGORITMOS DEALGORITMOS DE
ORDENAÇÃO ORDENAÇÃO 
Autor: Thiago Nascimento Rodrigues Autor: Thiago Nascimento Rodrigues 
Revisor: Bruno Carreira Coutinho Silva Revisor: Bruno Carreira Coutinho Silva 
INICIAR
Introdução
Caro(a) estudante, 
 
Diversos problemas computacionais são modelados por relações ou funções cuja
definição é dada por meio de regras baseadas na própria relação ou função. Essa é a
essência do conceito de recorrência, o qual é amplamente empregado em problemas
conhecidos como recursivos. Entender como manipular essa classe de problemas e
conhecer técnicas para descrever o comportamento assintótico dos algoritmos
relacionados é de grande importância para o desenvolvimento de soluções eficientes e
precisas. 
Nesta unidade, vamos conhecer um importante resultado que dá suporte à obtenção de
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 2/26
3.1 Recorrências: método do teorema mestre
Dividir e conquistar é provavelmente a técnica geral de projeto de algoritmos mais
conhecida. De fato, alguns dos algoritmos mais eficientes para certos tipos de problemas
são implementações específicas dessa estratégia geral. Algoritmos de divisão e
conquista são construídos em conformidade com três passos gerais: 
Um problema é dividido em vários subproblemas do mesmo tipo e idealmente do
mesmo tamanho aproximado.
Os subproblemas são resolvidos, normalmente de forma recursiva, embora às
vezes um algoritmo diferente seja empregado, especialmente quando os
subproblemas se tornam pequenos o suficiente.
Se necessário, as soluções para os subproblemas são combinadas para se obter
uma solução do problema original.
O caso mais típico da técnica de divisão e conquista é apresentado esquematicamente
no Diagrama 1, no qual um problema é dividido em dois subproblemas menores. Como
exemplo prático, o problema de calcular a soma dos números 
pode ser considerado. Se n > 1 [ #PraCegoVer : n maior que 1], o problema pode ser
dividido em dois: calcular a soma dos primeiros ⌊n/2⌋ [ #PraCegoVer : piso de n sobre 2]
números e calcular a soma dos números ⌈n/2⌉ [ #PraCegoVer : teto de n sobre 2]
restantes. Naturalmente, se n = 1 [ #PraCegoVer : n igual a 1], basta simplesmente
retornar a [ #PraCegoVer : a índice 0] como resposta. Assim que cada uma das duas
soluções fechadas para determinados tipos de recorrências de maneira direta. Além
disso, os conceitos de recursão serão analisados sob a perspectiva de algoritmos que
lidam com o problema de ordenação de dados em memória primária. Uma técnica
conhecida como dividir e conquistar será ainda explorada no contexto de dois algoritmos
projetados para essa classe de problema. 
 
Bons estudos! 
0 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 3/26
somas for calculada aplicando o mesmo método recursivamente, os seus valores podem
ser somados para obter o resultado em questão (LEVITIN, 2012): 
Diagrama 1 – Caso típico de divisão e conquista
Fonte: LEVITIN, 2012, p. 170. (Adaptado). 
Conforme apresentado, no caso mais típico de divisão e conquista, a instância de um
problema de tamanho n é dividida em duas instâncias de tamanho n/2 [ #PraCegoVer : n
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 4/26
sobre 2]. De forma geral, uma instância de tamanho n pode ser dividida em b instâncias
de tamanho n/b [ #PraCegoVer : n sobre b], com a delas precisando ser resolvidas – a e
b são constantes em que a ≥ 1 e b > 1 [ #PraCegoVer : a maior ou igual a 1 e b maior
que 1]. Para simplificação da análise, é possível supor que o tamanho n é uma potência
de b. Neste caso, a seguinte recorrência para o tempo de execução T(n) [ #PraCegoVer :
T de n] é obtida: 
em que f(n) é uma função que contabiliza o tempo gasto na divisão de uma instância de
tamanho n em instâncias de tamanho n/b e combinando suas soluções. Considerando
essa recorrência no formato padrão de recorrências, temos que T(n) é, no máximo, uma
constante para todo n suficientemente pequeno. Para valores grandes de n , o caso geral
seria dado por 
Em que: 
a corresponde ao número de chamadas recursivas;
b indica o fator de redução do tamanho da entrada;
d é o expoente do tempo de execução relativo aos passos de combinação.
O caso básico de uma recorrência no formato padrão afirma que quando o tamanho da
entrada é suficiente, nenhuma chamada recursiva é necessária; logo, o problema pode
ser resolvido em tempo O (1). Por outro lado, o caso geral assume que o algoritmo faz a
chamadas recursivas, cada uma aplicada a um subproblema menor do que a entrada
original e cuja redução se dá por um b. Além disso, o caso geral realiza O(n ) [
#PraCegoVer : O de n elevado a d] operações funciona fora das chamadas recursivas
(ROUGHGARDEN, 2017). 
Uma técnica muito empregada para se encontrar uma solução fechada para recorrências
no formato padrão é conhecido como teorema mestre. De acordo com Cormen et al.
(2009), o teorema mestre oferece um passo a passo para resolver recorrências da forma
T(n) = aT(n/b) + f(n) [ #PraCegoVer : T de n é igual ao produto de a por T de n sobre b
somado a f de n], em que a ≥ 1 e b > 1 [ #PraCegoVer : a maior ou igual a 1 e b maior
d 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 5/26
que 1] são constantes e f(n) é uma função assintoticamente positiva. Uma vez satisfeitas
essas condições, a solução de recorrências desse tipo pode ser dada pela avaliação dos
seguintes casos: 
(Caso 1) Se
para alguma constante ε > 0 [ #PraCegoVer : épsilon maior que 0], então
(Caso 2) Se
então
(Caso 3) Se
e se af(n/b) ≤ cf(n) [ #PraCegoVer : a vezes f de n sobre b é menor ou igual a c
vezes f de n] para alguma constante c > 1 e n for suficientemente grande, então T(n)
= Θ(f(n)) [ #PraCegoVer : T de n é igual a theta de f de n].
Clique nos cards para saber mais sobre o Teorema Mestre. 
Teorema Mestre
Se f(n) ∈ Θ(n ) [ #PraCegoVer : f de n pertence a theta de n elevado a d] onde d ≥ 0 na
recorrência T(n) = aT(n/b) + f(n) [ #PraCegoVer : T de n igual ao produto de a com T de n
sobre b e isso somado a f de n] então 
» Clique nas abas para saber mais sobre o assunto
d 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 6/26
Importante observar que o resultado da recorrência depende da comparação entre 
Para que o teorema possa ser aplicado, é preciso que a diferença entre essas duas
funções seja polinomial, isto é, tem que ser pelo menos n [ #PraCegoVer : n elevado a
épsilon] . Em função disso, o teorema não se aplica a todas as recorrências. De maneira
intuitiva, a maior das funções determina a solução para a recorrência. No caso 1, se a
função 
é maior, então a solução é 
No caso 3, se a função f(n) [ #PraCegoVer : f de n] é maior, então a solução é T(n) =
Θ((f)n) [ #PraCegoVer : T de n é igual a theta de f de n]. No caso 2, se as duas funções
têm o mesmo tamanho, é preciso multiplicar um fator logarítmico e a solução é 
VOCÊ SABIA?
Os três casos abrangidos pelo teorema mestre não cobrem todas as
possibilidades para f(n) . Há uma lacuna entre os casos 1 e 2 quando f(n) é
menor que
mas não polinomialmente menor. Da mesma forma, existe uma lacuna entre os
casos 2 e 3 quando f(n) é maior queε 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 7/26
mas não polinomialmente maior. Se a função f(n) cair em uma dessas lacunas, ou
se a condição de regularidade no caso 3 falhar, não será possível usar o método
mestre para resolver a recorrência (SKIENKA, 2008). 
Para utilizar o teorema mestre, basta determinar em qual caso (se aplicável) a
recorrência a ser resolvida se encaixa. Por exemplo, a seguinte função: T(n) = 9T(n/3) +
n [ #PraCegoVer : T de n é igual a 9 vezes T de n sobre 3 e isso somado a n]. Para essa
recorrência, os termos considerados pelo teorema têm os seguintes valores: 
a = 9; [ #PraCegoVer : a igual a 9]
b = 3; [ #PraCegoVer : b igual a 3]
f(n) = n . [ #PraCegoVer : f de n igual a n]
Logo, 
Como 
onde ε = 1 [ #PraCegoVer : épsilon é igual a 1], o teorema pode ser aplicado para o caso
1, o que leva à solução da recorrência como T(n) = Θ(n ) [ #PraCegoVer : T de n é
igual a theta de n ao quadrado]. 
Um segundo exemplo de aplicação do teorema pode ser analisado com a função T(n) =
T(2n/3) + 1 [ #PraCegoVer : T de n é igual a T de 2n sobre 3 e isso somado a 1]. Neste
caso, os termos envolvidos são: 
a = 1; [ #PraCegoVer : a igual a 1]
b = 2 /3; [ #PraCegoVer : b igual a dois terços]
f(n) = 1. [ #PraCegoVer : f de n igual a 1]
Logo, 
2 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 8/26
Como 
o caso 2 do teorema pode ser aplicado e o resultado é dado por T(n) = Θ(log(n)) [
#PraCegoVer : T de n é igual a theta de log de n]. Como terceiro exemplo, o problema de
encontrar a solução para a recorrência T(n) = 3T(n/4) + nlog(n) [ #PraCegoVer : T de n é
igual a 3 vezes T de n sobre 4 e esse produto é somado a n vezes log de n]. Neste caso,
tem-se: 
a = 3, [ #PraCegoVer : a igual a 3]
b = 4, [ #PraCegoVer : b igual a 4]
f(n) = nlog(n) . [ #PraCegoVer : f de n igual ao produto de n com log de n]
Logo, 
Como 
onde ε ≈ 0,2 [ #PraCegoVer : épsilon é aproximadamente 0,2], o caso 3 do teorema pode
ser aplicado se a condição de regularidade de f(n) for provada ser satisfeita. Para um
número n suficientemente grande, tem-se que: 
Consequentemente, o caso 3 pode ser empregado e a solução da recorrência é dada por
T(n) = Θ(nlog(n)) [ #PraCegoVer : T de n é igual a theta de n log de n]. 
Teste seus conhecimentos
Atividade não pontuada.
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 9/26
VOCÊ SABIA?
Merge sort é um algoritmo relativamente antigo e que era conhecido por John von
Neumann já em 1945. Apesar de ter mais de 70 anos, esse algoritmo ainda é um
dos métodos escolhidos para executar operações de ordenação. Na prática,
Merge sort é o algoritmo de ordenação padrão em uma série de bibliotecas de
programação (ROUGHGARDEN, 2017).
3.2 Complexidade do algoritmo de decisão e conquista
Merge sort 
Muitos dos algoritmos conhecidos são recursivos em estrutura, isto é, para resolver um
determinado problema eles chamam recursivamente a si próprios uma ou mais vezes e
lidam com subproblemas relacionados. Esses algoritmos normalmente seguem uma
abordagem de dividir e conquistar: eles dividem o problema em vários subproblemas que
são semelhantes ao problema original, mas menores em tamanho, resolvem os
subproblemas recursivamente e, em seguida, as soluções são combinadas para construir
uma solução para o problema original. 
O algoritmo de ordenação Merge sort segue de perto o paradigma dividir e conquistar.
Intuitivamente, ele funciona da seguinte maneira: 
Dividir: uma sequência de n elementos é dividida em duas subsequências de n /2
elementos cada a fim de que ambas sejam ordenadas;
Conquistar: as duas subsequências são ordenadas recursivamente usando o
Merge sort;
Combinar : as duas subsequências ordenadas são mescladas para produzir a
resposta ordenada.
A recursão é interrompida ou atinge o seu limite quando a sequência a ser ordenada
alcança o comprimento 1, caso este em que não há trabalho a ser feito, uma vez que
toda sequência de comprimento 1 já está ordenada. 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 10/26
Uma maneira de visualizar a execução do algoritmo Merge sort é por meio de uma árvore
binária T, chamada de árvore Merge sort. Cada nó de T representa uma invocação
recursiva (ou chamada) do algoritmo sobre uma sequência S a ser ordenada. Os filhos
de um nó v de T estão associados às chamadas recursivas que processam as
subsequências S e S de S. Os nós externos de T estão associados a elementos
individuais de S, correspondendo a instâncias do algoritmo que não fazem chamadas
recursivas (GOODRICH, TAMASSIA e GOLWASSWER, 2014). O Diagrama 2 apresenta
um exemplo de árvore binária de execução do algoritmo Merge sort. 
Diagrama 2 – Árvore binária de execução do Merge sort
Fonte: GOODRICH, TAMASSIA e GOLWASSWER, 2014, p. 533. 
O pseudocódigo do algoritmo Merge sort é descrito a seguir. Nesse algoritmo, a
ordenação de um dado vetor A de n posições é feita com sua divisão em duas metades,
ordenando cada uma delas recursivamente e, então, mesclando os dois vetores menores
ordenados em um só. Quando o tamanho dos subvetores é menor ou igual a 1, ou seja,
tem no máximo um elemento, ele já se encontra ordenado. A operação principal do
algoritmo (linha 6) é a mesclagem de dois subvetores ordenados na etapa de
“combinação” da estratégia de divisão e conquista. O procedimento Mesclar realiza
junção dos subvetores dois a dois para formar um único vetor ordenado. 
1 2 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 11/26
Algoritmo MergeSort 
Entrada: Um vetor A[0 .. n - 1] de elementos ordenáveis 
 Saída: Vetor A[0 .. n – 1] ordenado de maneira crescente 
1. se n > 1 então
2. Copiar A[0 .. ⌊n/2⌋ - 1] para B[0 .. ⌊n/2⌋ - 1]
3. Copiar A[⌊n/2⌋ .. n - 1] para C[0 .. ⌊n/2⌋ - 1]
4. MergeSort(B[0 .. ⌊n/2⌋ - 1])
5. MergeSort(C[0 .. ⌊n/2⌋ - 1])
6. Mesclar(B, C, A)
VOCÊ SABIA?
O número de comparações de chaves feitas pelo Merge sort, no pior caso, chega
muito perto do mínimo teórico (log n! ≈ nlog n – 1,44n) [ #PraCegoVer : logari
 tmo de n fatorial na base 2 é aproximadamente igual a n log n na base 2 menos
1,44 n] que qualquer algoritmo de ordenação geral baseado em comparação
pode ter. Para n grande, a quantidade de comparações feitas por esse algoritmo,
no caso médio, acaba tendo cerca de 0,25n menos operações (LEVITIN, 2012). 
No algoritmo para mesclagem de vetores utilizado pelo Merge sort, o vetor A resultado é
percorrido usando o índice k , e os subvetores com os índices i e j . Todos os três vetores
são percorridos da esquerda para a direita. O laço na linha 3 implementa a varredura
para construção do vetor de saída. Na primeira iteração, o procedimento identifica o
elemento mínimo em L ou R e realiza sua cópia para a primeira posição do vetor de
saída A. O elemento mínimo global está localizado ou em L (nesse caso é L[0], uma vez
que L está ordenado) ou em R (nesse caso é R[0], uma vez que R está ordenado).
Avançando o índice apropriado (i ou j), o algoritmo evita, definitivamente, de avaliar o
elemento recém-copiado em uma iteração posterior. Então, o processo é repetido para
identificar o menor elemento remanescente em L ou R (o segundo menor global). Em
geral, o menor elemento ainda não copiado para A é L[ i ] ou R[ j ]; o procedimento
2 2 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 12/26
verifica explicitamente qualé a menor e prossegue adequadamente. Uma vez que cada
iteração realiza a cópia do menor elemento ainda em avaliação em L ou R, o vetor de
saída é completamente preenchido de maneira ordenada.
Merge sort – vantagem vs. desvantagem
» Clique nas abas para saber mais sobre o assunto
Algoritmo Mesclar 
Entrada: Vetores B e C, ambos ordenados e de tamanho ⌊n/2⌋ 
 Saída: Vetor A[0 .. n - 1] ordenado composto dos elementos de L e R 
1. i ←0
2. j ←0 
3. para k ←0 até n - 1 faça 
4. se L[ i ] < R[ j ] então
5. A[ k ] ← L[ i ]
6. i ← i + 1
7. senão
8. A[ k ] ← R[ j ]
9. j ← j + 1
 
Vantagem Desvantagem
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 13/26
Figura 1 – Operações executadas pelo procedimento de mesclagem do Merge sort. Fonte: CORMEN et al., 2009,
p. 32. 
A Figura 1 ilustra o funcionamento do procedimento de mesclagem de vetores acionados
pelo algoritmo Merge sort. A situação detalhada na figura corresponde ao momento em
que o vetor L contém a sequência 2, 4, 5, 7 e o vetor R a sequência 1, 2, 3, 6. Ambos já
foram ordenados e agora precisam ser mesclados no vetor A de saída. As posições
destacadas no vetor A indicam os valores finais após a mesclagem de um par de
elementos de L e R. Na Figura 1(a) as primeiras posições de L e R são comparadas e o
menor valor (R[ 1 ] = 1) é copiado para A[ 9 ]. Após essas operações, o índice j de R é
incrementado, assim como o índice k do vetor A. Esse mesmo processo se repete nas
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 14/26
Figuras 1(b)-(d), representando apenas as próximas três iterações do laço principal do
procedimento. Ao final de todas as iterações referentes a essa mesclagem, o trecho A[ 9
.. 16 ] do vetor A conterá a sequência 1, 2, 2, 3, 4, 5, 6, 7.
Figura 2 – Algoritmo Merge sort em ação. Fonte: SKIENKA, 2008, p. 121. 
A Figura 2 apresenta uma execução completa do algoritmo Merge sort ordenando a
sequência M, E, R, G, E, S, O, R, T. Como o algoritmo constitui um típico exemplo de
aplicação da estratégia de divisão e conquista, a análise do seu comportamento
assintótico pode ser feita com base nos passos abrangidos por essa estratégia:
Divisão: a etapa de divisão apenas computa a posição correspondente à metade do
vetor, o que demanda um tempo constante Θ(1) [ #PraCegoVer : t theta de 1].
Conquista: o algoritmo recursivamente resolve dois subproblemas, cada qual de
tamanho n /2, o que agrega 2T( n /2) ao seu tempo de execução. 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 15/26
Combinação: o procedimento de mesclagem é responsável por esta etapa. Como
descrito pelo pseudocódigo acima, esse algoritmo percorre um vetor de tamanho n
cada vez que é invocado, o que demanda um tempo Θ(n) [ #PraCegoVer : theta de
n]. 
Reunindo os custos relacionados a cada uma das etapas do algoritmo, é possível
identificar a seguinte recorrência para descrever a complexidade do Merge sort:
Aplicando o primeiro caso do teorema mestre para obtenção de uma solução fechada
para essa recorrência, temos que a complexidade do algoritmo é da ordem de Θ(nlog(n))
[ #PraCegoVer : theta de n log de n]. Importante observar que, como o processo de
particionamento do vetor em subvetores é baseado em posições e não em valores das
chaves, o algoritmo tem a mesma complexidade tanto no pior como no melhor caso.
3.3 Complexidade do algoritmo quick sort no melhor caso
Quicksort é o algoritmo de ordenação interna mais rápido que se conhece para uma
ampla variedade de situações, sendo provavelmente mais utilizado do que qualquer outro
algoritmo. De acordo com Ziviani (1999), o algoritmo foi inventado por C. A. R. Hoare em
1960, quando visitava a Universidade de Moscou como estudante. O algoritmo foi
publicado mais tarde por Hoare (1962), após uma série de refinamentos. A ideia básica é
a de particionar o problema de ordenação de um conjunto com n itens em dois problemas
menores. A seguir, os problemas menores são ordenados independentemente, e depois
os resultados são combinados para produzir a solução do problema maior.
VOCÊ O CONHECE?
Charles Antony Richard Hoare, aos 26 anos, inventou o algoritmo quick sort
enquanto tentava ordenar palavras para o projeto de uma máquina de tradução
do russo para o inglês. Ele fez a seguinte avaliação geral do seu trabalho (em
tradução livre): “Tive muita sorte. Que maneira maravilhosa de começar uma
carreira em computação, descobrindo um novo algoritmo de ordenação!”
(HOARE, 1996). Vinte anos depois, ele recebeu o Prêmio Turing por
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 16/26
“contribuições fundamentais para a definição e projeto de linguagens de
programação”. Em 1980, ele também foi nomeado cavaleiro por serviços à
educação e à Ciência da Computação (LEVITIN, 2012). 
O quick sort, assim como o Merge sort, aplica uma estratégia de divisão e conquista. As
três etapas dessa estratégia implementadas pelo algoritmo para a ordenação de uma
sequência S de elementos são: 
1. Divisão. Se S tem pelo menos dois elementos (nada precisa ser feito se S tem zero
ou um elemento), selecionar um elemento x específico de S, o qual será chamado
de pivô. Remova todos os elementos de S e os coloque em três outras sequências: 
● L, contendo os elementos de S menores que x ; 
● E, contendo os elementos de S iguais x ; 
● G, contendo os elementos de S maiores que x . 
 
Naturalmente, se todos os elementos de S forem distintos, então E terá apenas um
elemento.
2. Conquista. Recursivamente ordene as sequências L e G. 
3. Combinação. Coloque os elementos de volta em S inserindo primeiro os elementos
de L, depois os de E e, finalmente os de G. 
A Figura 3 apresenta uma visão esquemática do funcionamento do algoritmo. 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 17/26
Figura 3 – Visão esquemática do algoritmo quick sort. Fonte: GOODRICH; TAMASSIA; GOLWASSWER, 2014, p.
544. (Adaptado). 
O pseudocódigo a seguir apresenta os passos executados pelo algoritmo. A parte mais
delicada deste procedimento é relativa à operação de partição (linha 2), a qual tem que
rearranjar o vetor A[ esq .. dir ] através da escolha arbitrária de um item do vetor
chamado pivô, de tal forma que ao final o vetor A está particionado em uma parte
esquerda com chaves menores ou iguais ao pivô, e uma parte direita com chaves
maiores ou iguais ao pivô. Naturalmente, depois que uma partição s é obtida, A[ s ]
estará em sua posição final no vetor ordenado e, dessa forma, o processo de ordenação
pode prosseguir para os dois subvetores à esquerda e à direita de A[ s ]
independentemente. 
Algoritmo quick sort 
Entrada: Subvetor de um vetor A[ 0 .. n – 1] definido pelos seus índices esq esquerdo e
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 18/26
dir direito. 
 Saída: Subvetor A[ esq .. dir ] ordenado de maneira crescente 
1. se esq < dir então
2. pivo ← Partição(A[ esq .. dir ])
3. QuickSort(A[ esq .. pivo - 1 ])
4. QuickSort(A[ pivo + 1 .. dir ])
Quick sort vs Merge sort
» Clique nas abas para saber mais sobre o assunto
O procedimento de partição do vetor é detalhado no pseudocódigo a seguir. Várias
estratégias podem ser adotadas para a escolha do elemento pivô. No algoritmo
apresentado, foi utilizada a estratégia proposta por Ziviani (1999), em que o pivô é
selecionado como sendo o elemento mais equidistantedas extremidades do vetor. O
procedimento pode ser resumido nos seguintes passos:
Escolha o elemento pivô segundo alguma estratégia (linha 03).
Percorra o vetor a partir da esquerda até que um elemento A[ i ] ≥ A[ pivo ] seja
encontrado (linha 05). Da mesma forma, percorra o vetor a partir da direita até que
um elemento A[ i ] ≤ A[ pivo ] seja encontrado (linha 06).
Como os dois elementos A[ i ] e A[ j ] estão fora do lugar no vetor final, troque os
dois de posição (linha 08).
Continue o processo até que os índices i e j se cruzem em algum ponto do vetor
Ao final, o vetor A[ esq .. dir ] estará particionado da seguinte forma:
Os elementos em A[ esq ], A[ esq + 1], …, A[ j ] serão menores ou iguais a A[ pivo ].
Os elementos em A[ i ], A[ i + 1], …, A[ dir ] serão maiores ou iguais a A[ pivo ].
Algoritmo Partição 
Entrada: Subvetor de um vetor A[ 0 .. n – 1] definido pelos seus índices esq esquerdo e
 
Estratégia de Divisão Etapa de Maior Esforço
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 19/26
dir direito com esq < dir . 
 Saída: Partição de A[ esq .. dir ] com a posição de pivô retornada pelo procedimento
1. i ← esq
2. j ← dir
3. pivo ← (i + j) / 2 
4. enquanto i < j faça
5. enquanto A[ pivo ] > A [ i ] faça i ← i + 1
6. enquanto A[ pivo ] < A [ j ] faça j ← j - 1 
7. se i ≤ j então
8. Trocar A[ i ] e A[ j ] de posições
9. i ← i + 1
10. j ← j - 1
11. retornar pivo
Figura 4 – Operação de partição de um vetor. Fonte: Elaborado pelo autor, 2020. 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 20/26
A Figura 4 ilustra o funcionamento do procedimento de partição aplicado sobre o vetor
com os elementos 85, 24, 63, 45, 17, 31, 96, 50. Na Figura 4(a), o elemento na posição 4
é selecionado como pivô. Na Figura 4(b), os elementos 85 (maior que 45) e 31 (menor
que 45) são selecionados para troca. Na sequência, a Figura 4(c) indica o elemento 63
(maior que 45) e 17 (menor que 45) para a próxima troca. A Figura 4(d) apresenta o vetor
após a conclusão do processo de partição quando os índices i e j se cruzam. 
Ordenação de arquivos com quick sort
» Clique nas abas para saber mais sobre o assunto
Considerando uma divisão o mais uniforme possível, o algoritmo de partição do quick
sort produz dois subproblemas, cada um de tamanho não maior que n /2, uma vez que
um tem tamanho ⌊ n/2 ⌋ [ #PraCegoVer : piso de n sobre 2] e outro tem tamanho ⌈ n /2⌉ -
1 [ #PraCegoVer : teto de n sobre 2 menos 1]. Nesse caso, o quick sort apresenta seu
melhor desempenho e a recorrência que descreve o seu tempo de execução é dada por 
Aplicando o caso 2 do teorema mestre, temos que uma solução fechada para a
recorrência pode ser expressa como T(n) = Θ(nlog (n)) [ #PraCegoVer : T de n é igual a
theta de n log de n]. Portanto, ao equilibrar igualmente os dois lados da partição em cada
nível da recursão, obtemos um algoritmo assintoticamente mais rápido. 
3.4 Complexidade do algoritmo quick sort no pior caso
Conforme apresentado previamente, o quick sort pode ser descrito por meio de quatro
passos principais, e a escolha do elemento pivô é crítica para a eficiência do processo de
ordenação. De acordo com Tenembaun, Langsam e Augenstein (1998), no Quick Sort
original, o pivô era tomado como o elemento mais à esquerda do vetor a ser particionado.
Nesse cenário, a boa eficiência do algoritmo depende de que o vetor original e todos os
 
Memória e Operações Versão recursiva Implementação
Estabilidade
2 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 21/26
subvetores resultantes não estejam ordenados, de modo que o valor do pivô sempre
encontre a sua posição correta no meio do subvetor.
Quick sort – passos gerais
» Clique nas setas ou arraste para visualizar o conteúdo
Supondo que as condições anteriores não se verifiquem e o vetor original esteja
ordenado (ou quase ordenado), a posição onde o pivô se encontra vai impactar
diretamente no desempenho da ordenação. Por exemplo, se o pivô estiver em sua
posição correta, o vetor original será dividido em subvetores de tamanhos 0 e n - 1. Se
esse processo continuar, um total de n - 1 subvetores será ordenado, sendo o primeiro
de tamanho n , o segundo de tamanho n - 1, o terceiro de tamanho n - 2 e assim por
diante. Pressupondo que sejam necessárias k comparações para reorganizar um vetor
de tamanho k , o número total de comparações para ordenar o vetor inteiro será dado
por:
ELEMENTOS:
PASSO 1
Se n = 0 ou n = 1, então o L está ordenado.
PASSO 2
Escolha qualquer elemento (pivô) x em L.
PASSO 3
Separe L - { x } em dois conjuntos disjuntos:
A ordenação deve ser chamada recursivamente para S e S .1 2 
PASSO 4
L recebe a concatenação de S , seguido de x, seguido de S .1 2 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 22/26
De maneira semelhante, se o vetor original estiver ordenado em ordem decrescente, a
posição final do pivô (ainda assumindo que o escolhido seja o elemento na extremidade
à esquerda do vetor) será na extrema direita do vetor e o vetor será novamente dividido
em dois subvetores que ficarão muito desequilibrados – tamanhos n - 1 e 0. Portanto, o
quick sort original apresenta a característica de funcionar melhor para vetores que
estejam sem qualquer ordenação e pior para vetores completamente ordenados.
VOCÊ SABIA?
Uma característica relevante do quick sort é a sua ineficiência quando executado
sobre arquivos já ordenados e quando a escolha do pivô é inadequada. Por
exemplo, a escolha sistemática dos extremos de um arquivo já ordenado leva ao
seu pior caso e o número de comparações passa a cerca de n /2 [
#PraCegoVer : n ao quadrado sobre 2]. Além disso, o tamanho da pilha auxiliar
necessária para as chamadas recursivas é cerca de n (ZIVIANI, 1999).
2 
Se for assumido que o particionamento do quick sort é feito de maneira desbalanceada
(pior caso), o custo de executar a partição a cada chamada recursiva será da ordem de
Θ(n) [ #PraCegoVer : theta de n]. Como a chamada recursiva sobre um vetor de
tamanho 0 não realiza qualquer operação (o procedimento apenas retorna), temos que
T(0) = Θ(1) [ #PraCegoVer : t de zero é igual a theta de um] e, portanto, a recorrência
para o tempo de execução do algoritmo será dada por (CORMEN et al., 2009) 
A soma dos custos incorridos em cada nível da recursão será expressa pelo mesmo
somatório já descrito previamente nessa seção, ou seja, a complexidade do pior caso do
quick sort será da ordem Θ(n ) [ #PraCegoVer : theta de n ao quadrado]. 
Teste seus conhecimentos
2 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 23/26
Síntese
Neste capítulo, tivemos a oportunidade de ampliar ainda mais o nosso conhecimento a
respeito de recorrências. Embora existam outros métodos muito utilizados para a
obtenção de soluções fechadas para funções desse tipo, o detalhamento do teorema
mestre ofereceu uma nova ferramenta para a manipulação de recorrências. Os três
casos contemplados por ele foram caracterizados dentro de exemplos práticos, o que
possibilitou uma visão mais clara de como as condições requeridas para sua aplicação
devem ser analisadas. 
Explorando ainda mais o conceito de recorrências, dois algoritmos de ordenação foram
estudados: o Merge sort e o quick sort. Ambos foram avaliados em relação ao seu
comportamento assintótico. Apesar da semelhança quanto à natureza recursiva, foi
mostrado que esses algoritmos apresentam diferentes desempenhos na ordenação de
chaves dentro da memória principal.Além disso, como o funcionamento de cada um foi
bem explorado através de pseudocódigos, conseguimos formar um conhecimento para
subsidiar a identificação dos cenários que sejam mais adequados para o empregado de
cada um dos algoritmos. 
SAIBA MAIS
Título : Estruturas de Dados e Algoritmos em Java 
Autores : Roberto Tamassia e Michael T. Godrich 
Atividade não pontuada.
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 24/26
Editora : Grupo A 
Ano : 2011 
Comentário : Concentre-se no Capítulo 11, onde os algoritmos Merge
sort e quick sort são bem explorados. Além disso, você vai encontrar
implementações desses algoritmos na linguagem de programação Java.
Isso possibilitará uma visão mais concreta de como trabalhar com esses
algoritmos na prática. 
Onde encontrar : Biblioteca Virtual da 
Título : Estruturas de dados e seus algoritmos 
Autor : Jayme Luiz Szwarcfiter 
Editora : LTC 
Ano : 2011 
Comentário : Explore o Capítulo 7 onde o funcionamento de vários
algoritmos de ordenação é detalhado, além de todos eles serem
analisados em seu comportamento assintótico. Em particular, os
algoritmos Merge sort e quick sort são descritos de maneira muito
didática. 
Onde encontrar: Biblioteca Virtual da Laureate
Título : Linguagens Formais e Autômatos 
Autor(a) : Paulo F. B. Menezes 
Editora : Grupo A 
Ano : 2011 
Comentário : Fique atento ao Capítulo 1, onde vários conceitos e
definições matemáticas são apresentadas como subsídio para uma
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 25/26
melhor compreensão da ideia de recursividade. Algumas técnicas de
demonstração também são exploradas e elas são muito úteis para a
formalização de resultados computacionais. 
Onde encontrar? Biblioteca Virtual da Laureate
Referências bibliográficas 
08/09/2022 22:02 Unidade 3 - Análise de algoritmos
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/CTI_ANLALG_21/unidade_3/ebook/index.html?redirect=1 26/26
CORMEN, T. H. et al. Introduction to Algorithms . Cambridge: Massachusetts Institute
of Technology, 2009. 
 
GOODRICH, M. T.; TAMASSIA, R.; GOLWASSWER, M. Data Structures & Algorithms .
New Jersey: John Wiley & Sons, 2014. 
HOARE, C. A. R. Quicksort. Great Papers in Computer Science , pp. 31-39, 1996.
Disponível em: < http://comjnl.oxfordjournals.org/content/5/1/10.full.pdf >. Acesso em: 6
jan. 2021. 
LEVITIN, A. Introduction to the design and analysis of algorithms . Boston: Addison-
Wesley, 2012. 
ROUGHGARDEN, T. Algorithms Illuminated – Part 1: The Basics. San Francisco:
Soundlikeyourself Publishing, 2017. 
SKIENKA, S. S. The Algorithm Design Manual . Nova York: Springer, 2008. 
SZWARCFITER, J. L.; MARKENZON, L. Estruturas de Dados e Seus Algoritmos . Rio
de Janeiro: LTC, 2015. 
TENEMBAUN, A. A.; LANGSAM, Y.; AUGENSTEIN, M. J. Data Structures Using C .
Nova York: McGraw-Hill, 1998. 
ZIVIANI, N. Projeto de Algoritmos com Implementações em Pascal e C . São Paulo:
Pioneira Informática, 1999.
http://comjnl.oxfordjournals.org/content/5/1/10.full.pdf