Ensaio Acadêmico Complexidade Algorítmica

Prévia do material em texto

CENTRO PAULA SOUZA 
FACULDADE DE TECNOLOGIA DE FRANCA 
“Dr. THOMAZ NOVELINO” 
 
 
 
TECNOLOGIA EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS 
 
 
 
 
 
 
CAIRO DE PAULA VIEIRA 
 
 
 
COMPLEXIDADE ALGORÍTMICA 
 
 
 
 
 
 
 FRANCA/SP 
2020 
 
CAIRO DE PAULA VIEIRA 
 
 
 
 
 
COMPLEXIDADE ALGORÍTMICA 
 
 
 
 
 
 
 
 
 
Ensaio Acadêmico apresentado à Disciplina 
de Estrutura de Dados, como parte dos 
requisitos necessários a aprovação da 
mesma. 
 
Docente: Fausto Gonçalves Cintra 
 
 
 
 
 
FRANCA/SP 
2020 
 
SUMÁRIO 
 
1 Introdução ………………………………..………………………………… 3 
2 Algoritmos .…………………………………………………………………. 4 
3 Complexidade Algorítmica ………………………………………………. 6 
3.1 Classes de Complexidade Assintótica………………………………….…. 6 
3.1.1 Notação Teta (Θ) ……………………………...…………………………..... 7 
3.1.2 Notação ​O ​(​O​) …………………………...……………………………..…… 8 
3.1.3 Notação Ômega (Ω) …………………………...……………………………. 9 
3.2 Análise de Pior Caso ……………………………………………………...... 9 
4 Algoritmos de Ordenação …………………………………………….….. 11 
4.1 Bubble Sort ………………………………………………..…………….…… 11 
4.2 Selection Sort ……………………………………..……………….....……... 12 
4.3 Merge Sort …………………………………………………….……………... 12 
4.4 Quick Sort …………………………………………………….……………… 13 
5 Análise Comparativa …………………………………………………….... 14 
6 Discussão e Conclusão …………………………………………………... 15 
Referências ……………………………………………………………………..……. 16 
 
 
 
 
 
 
 
 
 
3 
1 INTRODUÇÃO 
Hoje vivemos uma era em que a tecnologia computacional onipresente está mais 
firmemente estabelecida, afinal, a vivemos de perto nos diversos aspectos de nossas vidas 
cotidianas - para nos divertir, comprar, trabalhar, viajar, estudar, nos comunicar etc - que por 
sua vez, são mediados, produzidos e regulados por meio de dispositivos digitais e sistemas 
alimentados por softwares (GREENFIELD, 2006; KITCHIN & DODGE, 2011; 
MANOVICH, 2013; STEINER, 2012; ​apud​ KITCHIN, 2016). 
Os softwares são essencialmente compostos por algoritmos que por sua vez são 
conjuntos de etapas estruturadas para processar instruções e dados a fim de produzir uma 
saída. (GILLESPIE, 2014a; ​apud ​KITCHIN, 2016). Sem os algoritmos, não estaríamos 
vivendo do modo como vivemos hoje, haja visto que eles estão ligados à criptografia, 
recomendação de marketing, reconhecimento de padrões, compactação de dados, etc. 
(MACCORMICK, 2013; ​apud​ KITCHIN, 2016). 
Apesar de sua grande importância, seu estudo é frequentemente ignorado por diversas 
pessoas da área, desde universitários até profissionais já experientes. Os argumentos mais 
utilizados giram em torno do fato de que “as linguagens de programação atuais já 
implementam os algoritmos de forma mais eficiente” ou ainda “que os recursos de hardware 
disponíveis no mercado tornam essa questão desnecessária”. Todavia, como diz Cormen ​et al. 
(2009), por mais rápidos que os computadores sejam, eles não são infinitamente velozes e por 
mais baratas que as memórias sejam, elas não são gratuitas. 
Deste modo, se aprofundar no estudo dos algoritmos e estrutura de dados, analisando 
sua eficiência e eficácia, seja por uso de memória computacional ou análise do tempo para a 
execução de determinadas tarefas, torna-se imprescindível. 
O intuito deste ensaio acadêmico é discutir brevemente sobre os algoritmos e a 
complexidade algorítmica e apresentar uma tabela de comparação de tempo de quatro 
diferentes tipos de algoritmo de ordenação: Bubble Sort, Selection Sort, Merge Sort e Quick 
Sort. 
 
 
 
 
4 
2 ALGORITMOS 
 
Informalmente, um algoritmo é qualquer procedimento computacional bem definido 
que recebe algum valor, ou conjunto de valores como entrada e produz algum valor, ou 
conjunto de valores, como saída/resultado. Também podemos visualizar um algoritmo como 
uma ferramenta para resolver um problema computacional bem especificado (CORMEN ​et 
al.​, 2009). 
Um algoritmo pode ser especificado em uma língua natural como o Português, como 
um programa de computador ou mesmo como um design de hardware. O único requisito é 
que a especificação deve fornecer uma descrição precisa do procedimento computacional a ser 
seguido. 
Um exemplo bastante comum na prática é a classificação de uma determinada 
sequência de números de maneira crescente. 
Entrada:​ Sequência de ​n​ números (​a​1​, a​2​, a​3​, …, a​n​); 
Saída: A permutação (reordem) (​a’​1​, a’​2​, a’​3​, …, a’​n​) da entrada de forma que ​a’​1 ≤ a’​2 
≤ a’​3​ ≤ … ≤ a’​n​. 
Ou seja, temos a instância de um problema que consiste na entrada e sua solução que 
consiste na saída. Dizemos que um algoritmo está correto se, para cada instância de entrada, 
ele trazer uma saída correta, em outras palavras, resolve o problema. 
A reordenação numérica não é de forma alguma o único problema computacional para 
o qual os algoritmos foram desenvolvidos. Como dito anteriormente, temos várias aplicações 
práticas de algoritmos como o Projeto Genoma Humano; o acesso à Internet; a possibilidade 
do comércio eletrônico; a melhor rota entre um trajeto de um ponto a outro (CORMEN ​et al.​, 
2009). Como diz Steiner (2012), os algoritmos já têm controle sobre os fundos do mercado 
monetário, ações e contas de aposentadoria, com quem conversamos por telefone, quais 
músicas ouvimos, quais as chances de se conseguir órgãos para transplante e para milhões de 
pessoas, podem até decidir com quem elas se casarão (​apud​ KITCHIN, 2016). 
A lista é exaustivamente grande, mas apresenta uma característica comum a muitos 
problemas algorítmicos. Como temos muitos desafios, temos também muitas soluções já 
estabelecidas na literatura e vivência prática, podendo algumas serem as mais eficientes para 
determinada questão, ou ainda constatar que para outras, não temos uma solução eficiente. 
5 
A principal medida usada para estabelecer a eficiência de um algoritmo é a 
velocidade, ou seja, o tempo necessário que um algoritmo leva para produzir seu resultado. 
Essa análise e metrificação é fundamental e objeto de estudo crescente na área da 
Computação, compreendendo não só a observações de algoritmos considerados “padrão 
ouro”, como também a investigação de novas soluções e suas complexidades. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6 
3 COMPLEXIDADE ALGORÍTMICA 
 
Depois que um algoritmo é desenvolvido para resolver um problema computacional é 
inevitável fazer a pergunta: "Seria possível torná-lo melhor?". Geralmente é possível sim 
pensar em soluções cada vez mais eficientes, mas eventualmente, estamos diante de uma 
barreira quase invisível, que torna as melhorias muito difíceis de alcançar. 
Desta forma, depois de inúmeras tentativas, é natural se perguntar se o “ponto ótimo” 
de determinado algoritmo já foi alcançado e para provar esta hipótese, torna-se necessário 
embasar-se em técnicas matemáticas formais. A esse conjunto de modelos e técnicas, damos o 
nome de Complexidade Algorítmica (RALSTON; EDWIN; HEMMENDINGER, 2003). 
Vários autores divergem entre si sobre qual seria o método mais adequado para medir 
a complexidade. Embora a maioria tenha acordado que tempo e espaço computacional são os 
mais indicados. 
Kronsjö (1987) e Rosen (1999) definem a complexidade de tempo de um algoritmo 
como a quantidadede tempo usada por um computador para resolver um problema de um 
tamanho específico usando o algoritmo. Eles definem a complexidade espacial de um 
algoritmo como a quantidade de memória computacional necessária para implementar o 
algoritmo. Assim, a complexidade do espaço e do tempo está ligada às estruturas de dados 
específicas usadas para implementar o algoritmo. Além disso, eles descrevem a complexidade 
computacional de um algoritmo como o poder computacional necessário para resolver o 
problema. Isso é medido contando o número de operações elementares realizada pelo 
algoritmo, como por exemplo número de multiplicações e/ou adições necessárias para avaliar 
um polinômio, o número de comparações necessárias para ordenar uma sequência, o número 
de multiplicações necessárias para multiplicar duas matrizes, o número de instruções para 
alcançar determinado fim etc. (​apud​ NASAR, 2016). 
 
3.1 ​Classes de Complexidade Assintótica 
 
Contar o número de instruções é uma das maneiras de analisar a complexidade de um 
algoritmo - como já mencionado - todavia, seria uma tarefa muito maçante ficar contando o 
número de instruções para cada trecho de código, sem considerar o fato de que esse número 
varia muito dependendo da escolha da linguagem, compiladores e até o processador utilizado. 
7 
Também como já foi elucidado, outra forma de analisar a complexidade é executar 
determinado algoritmo e medir sua velocidade utilizando alguma unidade de tempo, no 
entanto, esse tipo de análise não é mais confiável, haja visto que a linguagem empregada no 
algoritmo, o programa em que está sendo executado, os dados de entrada, e a capacidade de 
processamento da máquina, variam de máquina para máquina e escolha do programador, 
tornando a classificação, de certa forma, não muito confiável (IQBAL ​et al.​, 2019). 
Com isso em mente, uma forma de driblar esses vieses é empregar a análise 
assintótica. Neste tipo de análise, leva-se em conta apenas grandes entradas de dados, afinal, 
para valores pequenos, a maioria dos algoritmos levará pouco tempo e o que faz um 
profissional escolher um algoritmo em detrimento de outro é o seu desempenho para grandes 
massas de dados. Ou seja, a análise assintótica se preocupa com o aumento do tempo de 
execução a medida que o tamanho da entrada aumenta indefinidamente ​(ASCENCIO; 
ARAÚJO, 2011). 
Matematicamente falando, quando analisamos qualquer algoritmo, geralmente 
obtemos uma fórmula para representar a quantidade de tempo necessária para a execução ou o 
tempo necessário para o computador executar as linhas de código do algoritmo, número de 
acessos à memória, número de comparações, variáveis temporárias que ocupam memória etc. 
Essa fórmula geralmente contém detalhes sem importância que realmente não nos dizem nada 
sobre o tempo de execução. Por exemplo, se algum algoritmo tiver uma complexidade de 
tempo de ​T(n) = (n​2 + 3n + 4)​, que é uma equação quadrática. Para grandes valores de ​n​, a 
parte ​3n + 4 se tornará insignificante em comparação com a parte ​n​2​. Para ​n = 1000​, ​n​2 será 
1000000​ enquanto ​3n + 4​ será ​3004​, por exemplo ​(AHLAWAT, 2020). 
Portanto, um algoritmo que demora ​200n​2 será mais rápido que outro algoritmo que 
leva tempo ​n​3​, para qualquer valor de ​n maior que ​200​. Como estamos interessados apenas no 
comportamento assintótico do crescimento da função, o fator constante pode ser ignorado. 
Basicamente usa-se três tipos de notações assintóticas para representar o crescimento 
de qualquer algoritmo, à medida que a entrada aumenta: Notação Teta (Θ), Notação ​O ​(​O​) e 
Notação Ômega (Ω). 
 
3.1.1 Notação Teta (Θ) 
 
A complexidade de tempo representada pela notação Θ é semelhante ao valor ou 
8 
intervalo médio dentro do qual será o tempo real de execução do algoritmo. Por exemplo, se 
para algum algoritmo a complexidade do tempo é representada pela expressão ​3n​2 + 5n​, e 
usamos a notação Θ para representá-lo, a complexidade do tempo seria Θ(​n​2​), ou seja, 
ignora-se o coeficiente constante e remove a parte insignificante, que é ​5n​. 
 
Figura 1​ - Representação Gráfica da Notação Teta (Θ) 
Fonte: StudyTonight, 2020. 
 
No exemplo acima, a complexidade de Θ(​n​2​) significa que o tempo médio de qualquer 
entrada ​n permanecerá no meio, ​k1 * n​2 e ​k2 * n​2​, onde ​k1 e ​k2 são duas constantes, 
vinculando firmemente a expressão que representa o crescimento do algoritmo ​(AHLAWAT, 
2020). 
 
3.1.2 Notação ​O ​(​O​) 
 
Essa notação é conhecida como o limite superior do algoritmo ou o pior caso de um 
algoritmo. Ela nos diz que uma determinada função nunca excederá um tempo especificado 
para qualquer valor da entrada ​n​. A questão é por que precisamos dessa representação quando 
já temos a notação Θ, que representa o tempo de execução fortemente vinculado a qualquer 
algoritmo? 
Vamos tomar como exemplo o algoritmo de Busca Linear, no qual percorremos os 
elementos de um vetor, um por um, para pesquisar um determinado número. Na pior das 
hipóteses, encontraremos o elemento ou o número que estamos procurando no final, o que 
9 
levará a uma complexidade de tempo ​n​, onde ​n representa o número de elementos totais. Mas 
pode acontecer do elemento procurado ser o primeiro, nesse caso, a complexidade do tempo 
será ​1​. 
Assim, dizer que a complexidade de tempo na notação Θ para a Busca Linear é Θ(​n​), 
significa que o tempo necessário sempre estará relacionado a ​n​, pois esse é o caminho para 
representar a complexidade média do tempo, mas quando usamos a notação ​O​, queremos 
dizer que a complexidade do tempo é ​O​(​n​), ou seja, a complexidade do tempo nunca excederá 
n​, definindo o limite superior e, portanto, dizendo que ela pode ser menor ou igual a ​n​, que é a 
representação correta (​AHLAWAT, 2020). 
Por esse motivo, na maioria das vezes, a notação ​O é usada para representar a 
complexidade do tempo de qualquer algoritmo. 
 
3.1.3 Notação Ômega (Ω) 
 
A notação Ω é usada para definir o limite inferior de qualquer algoritmo ou o melhor 
caso de qualquer algoritmo. Isso indica o tempo mínimo necessário para qualquer algoritmo 
para todos os valores de entrada, portanto, o melhor caso de qualquer algoritmo. 
Em palavras simples, quando representamos uma complexidade de tempo para 
qualquer algoritmo na notação Ω, queremos dizer que o algoritmo levará pelo menos esse 
tempo para completar sua execução ​(AHLAWAT, 2020). 
 
3.2 Análise de Pior Caso 
 
 
Comparar algoritmos e determinar qual o melhor diante de determinado cenário, não é 
tarefa fácil, isso porque além dos pontos já mostrados, diferentes formas de entrada de dados 
influenciam diretamente nessa questão. Por exemplo, alguns algoritmos podem ter um 
desempenho melhor do que outros em dados já ordenados e pior em dados totalmente 
desordenados. Quando dois algoritmos têm desempenho incomparável, como podemos 
considerar um deles "melhor” que o outro? 
A análise de pior caso é uma ferramenta utilizada na análise de algoritmos, em que o 
desempenho geral de um algoritmo é resumido por seudesempenho no pior cenário possível 
em qualquer entrada de um determinado tamanho, assim, o “melhor” algoritmo é aquele com 
10 
melhor performance no pior caso, trazendo em termos populares, este tipo de análise seria 
como a "Lei de Murphy". Embora grosseira, a análise do pior caso pode ser extremamente 
útil, e é o paradigma dominante para a análise de algoritmos na ciência da computação teórica 
(ROUGHGARDEN, 2019). 
Para ilustrar melhor vamos usar como exemplo um array ​A de cinco elementos ​A = 
[10, 50, 30, 20, 40] em que desejamos ordenar de forma crescente. O pior caso seria a 
ordenação desse vetor na seguinte forma ​A = [50, 40, 30, 20, 10]​, enquanto o melhor caso 
seria o oposto, ou o vetor já ordenado ​A = [10, 20, 30, 40, 50]​. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
11 
4 ALGORITMOS DE ORDENAÇÃO 
 
 
Os algoritmos de ordenação nada mais são que algoritmos que colocam os elementos 
de uma determinada entrada de dados em ordem, ou seja, efetua a ordenação de forma 
completa ou parcial. 
O problema de ordenação de dados foi um dos primeiros e mais estudados tópicos em 
Ciência da Computação, uma vez que seu uso é rotineiro no dia a dia prático. Eles podem ser 
utilizados em situações particulares de triagem, cálculos de processamento de dados, melhoria 
de desempenho da memória etc. Por serem tão comuns, diversos tipos desses algoritmos 
foram criados, cada um com suas especificidades e uns julgando-se serem mais rápidos do 
que outros, porém, todos com apenas um intuito, facilitar o trabalho dos profissionais da área 
(JUGÉ, 2020). 
Embora existam múltiplos algoritmos de ordenação, neste ensaio contemplaremos 
quatro deles: Bubble Sort, Selection Sort, Merge Sort e Quick Sort. 
 
4.1 Bubble Sort 
 
O algoritmo de ordenação Bubble Sort é um dos algoritmos mais antigos e mais 
simples, contudo, sua criação é incerta. Estudos antigos mostram que um algoritmo de 
ordenação com funcionamento semelhante já era utilizado em 1956 sob o nome de 
“ordenação por troca”, todavia, o termo Bubble Sort data de 1962, quando foi usado por 
Kenneth E. Iverson (1962) em seu livro “Uma Linguagem de Programação” (​apud 
ASTRACHAM, 2003). 
Seu funcionamento caracteriza-se na comparação de todos os elementos fornecidos 
um a um, classificando-os de acordo com o seu valor. Se os dados precisam ser ordenados em 
ordem crescente, por exemplo, o algoritmo começará comparando o primeiro elemento com o 
segundo; se o primeiro elemento for maior que o segundo, ele trocará a posição dos dois, em 
seguida, prosseguirá para comparar o segundo elemento com o terceiro, e assim por diante. 
Quanto ao tipo, ele é classificado como um algoritmo de permuta e quanto à 
complexidade de tempo é tido como ​O​(n​2​) na análise de pior caso, ​O​(n) na de melhor caso, 
O​(n​2​) na complexidade média e ​O​(1) na análise de espaço ​(AHLAWAT, 2020). 
 
12 
4.2 Selection Sort 
 
Assim como o Bubble Sort, a criação do Selection Sort também é incerta. Uma de suas 
primeiras aparições está no artigo “Os Princípios de Ordenação” de Bell (1958), o qual cita 
dentre diversos tipos de ordenação, a do tipo seleção (​apud​ ASTRACHAM, 2003). 
Seu funcionamento também é simples e ocorre da seguinte forma: primeiro 
encontra-se o menor elemento da sequência e é feita a troca com o elemento da primeira 
posição; depois, encontra-se o segundo menor elemento e é feita a troca com o elemento da 
segunda posição; e assim sucessivamente até toda a entrada estar ordenada. 
Ele é classificado quanto ao tipo em um algoritmo do tipo seleção e permuta, e quanto 
à complexidade é categorizado em ​O​(n​2​) na análise de pior caso, melhor caso e complexidade 
média e em ​O​(1) na análise de espaço ​(AHLAWAT, 2020). 
 
4.3 Merge Sort 
 
O Merge Sort é tão importante na história dos algoritmos de ordenação, quanto a 
ordenação é importante na história da computação. Uma descrição detalhada do algoritmo 
apareceu pela primeira vez em um relatório de Goldstine e Von Neumann (1948), tendo assim 
o segundo autor como o inventor da operação (​apud​ KATAJAINEN; TRÄFF, 1997)​. 
O algoritmo segue a regra de “dividir e conquistar” para ordenar determinado 
conjunto, isso acontece por meio da recursividade, o que leva a uma ordenação mais rápida, 
mesmo que consuma um espaço maior na memória. A ideia é dividir um grande problema 
(sequência a ser organizada) em subproblemas menores (vetores menores da sequência) para 
que depois seja feita a combinação das soluções desses subproblemas em uma grande solução 
(sequência ordenada). 
O vetor a ser ordenado é dividido ao meio, depois em subvetores, até que cada um 
tenha apenas um elemento. Depois, a ideia é que esse subvetor faça o caminho inverso, se 
recompondo ao seu tamanho original, porém, de forma ordenada, para que por fim, tenhamos 
atingido o objetivo. 
Portanto, ele é classificado como um algoritmo de divisão e conquista e quanto à 
complexidade em ​O​(n*log n) ​na análise de pior caso, melhor caso e complexidade média e 
em ​O​(n) na análise de espaço ​(AHLAWAT, 2020). 
13 
4.4 Quick Sort 
 
O Quick Sort também é baseado no conceito de divisão e conquista e seu inventor foi 
Hoare, que o descreveu em um trabalho de 1962 ​(HOARE, 1962). 
Ele funciona da seguinte maneira: primeiramente é selecionado um elemento como 
pivô (geralmente o que ocupa a última posição) e o conjunto é então dividido. Os elementos 
são posicionados de forma que todos os elementos menores que o pivô fiquem à esquerda dele 
e os maiores, à direita. Ao fim do processo o pivô estará em sua posição final e haverá duas 
sub listas não ordenadas. Recursivamente, a ordenação acontece nos subconjuntos dos valores 
menores e depois, nos maiores. 
Como dito anteriormente, o algoritmo se enquadra na classificação de divisão e 
conquista e quanto à complexidade é categorizado em ​O​(n​2​) na análise de pior caso, ​O​(n*log 
n) na análise de melhor caso e complexidade média e também na análise de espaço 
(AHLAWAT, 2020). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
14 
5 ANÁLISE COMPARATIVA 
 
 
Abaixo temos a análise comparativa dos quatro algoritmos de ordenação aqui expostos 
para amostras de ​1000, 10000, 25000 e 100000 nomes em um ​notebook com as seguintes 
configurações. 
Tabela 1​ - Especificação do equipamento 
Sistema Operacional Ubuntu 20.04 LTS 
Processador Intel® Core i7-4500U CPU @ 1.80Ghz x 4 
Arquitetura (32 ou 64 
bits) 
64 bits 
Memória RAM Total 8 GB 
Versão do Node.js 12.16.3 
Fonte: Fausto Gonçalves Cintra, 2020. 
Tabela 2 ​- Análise de eficiência 
 Tamanho da amostra 
Algoritmo 1000 10.000 25.000 100.000 
Bubble Sort 18,487ms 
0,018487s 
 2096,840ms 
2,09684s 
14666,064ms 
14,666064s 
246704,901ms 
4,11174835 min 
Selection 
Sort 
11,870ms 
0,01187s 
746,299ms 
0,746299s 
4731,262ms 
4,731262s 
80268,434ms 
1,33780723333 min 
Merge Sort 10,897ms 
0,010897s 
22,097ms 
0,022097s 
40,818ms 
0,040818s 
116,118ms 
1,9353 min 
Quick Sort 2,652ms 
0,002652s 
8,218ms 
0,008218s 
15,801ms 
0,015801s 
55,685ms 
0,055685s 
Fonte: Fausto Gonçalves Cintra, 2020. 
 
 
 
 
 
 
156 DISCUSSÃO E CONCLUSÃO 
 
Como observado na Análise Comparativa, poderíamos inferir que o algoritmo Quick 
Sort é o melhor a ser utilizado para a ordenação de um determinado conjunto de dados, no 
entanto, precisamos ter em mente, que o melhor algoritmo é aquele que possui a menor 
complexidade de tempo e espaço, de acordo com a máquina e linguagem utilizadas. 
Este ensaio foi apenas uma breve apresentação sobre a Complexidade Algorítmica e 
sua importância. Para entender mais sobre o assunto é necessário estudar a fundo os tópicos 
citados e além. 
Implementar algoritmos eficientes e eficazes são primordiais para construir aplicações 
de qualidade e que permitam uma boa experiência ao usuário. Embora os recursos de 
hardware vêm se tornando cada vez mais baratos e eficientes, a necessidade de entender como 
melhorar o dia a dia profissional é de extrema importância. Afinal, o conhecimento e técnica 
de algoritmos é algo que separa os excelentes programadores dos medianos. Claro que com a 
tecnologia computacional atual, é possível executar trabalhos sem saber muito sobre o 
assunto, mas conhecendo-o é possível fazer muito mais. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
16 
REFERÊNCIAS 
 
 
AHLAWAT, Abhishek. ​StudyTonight​. Disponível em: 
https://www.studytonight.com/data-structures/aysmptotic-notations. Acesso em: 19 
maio 2020. 
 
AHLAWAT, Abhishek. ​StudyTonight​. Disponível em: 
https://www.studytonight.com/data-structures/bubble-sort. Acesso em: 19 maio 2020. 
 
AHLAWAT, Abhishek. ​StudyTonight​. Disponível em: 
https://www.studytonight.com/data-structures/merge-sort. Acesso em: 19 maio 2020. 
 
AHLAWAT, Abhishek. ​StudyTonight​. Disponível em: 
https://www.studytonight.com/data-structures/quick-sort. Acesso em: 19 maio 2020. 
 
AHLAWAT, Abhishek. ​StudyTonight​. Disponível em: 
https://www.studytonight.com/data-structures/selection-sorting. Acesso em: 19 maio 
2020. 
 
ASCENCIO, Ana Fernanda Gomes; ARAÚJO, Graziela Santos de. ​Estruturas de 
Dados: algoritmos, análise da complexidade e implementações em JAVA e 
C/C++​. São Paulo: Pearson, 2011. 
 
ASTRACHAN, Owen. Bubble Sort: An Archaeological Algorithmic Analysis. ​ACM 
SIGCSE Bulletin. ​Durham, p. 1-5. jan. 2003. 
 
CORMEN, Thomas H. ​et al​. ​Introduction to Algorithms​. 3. ed. Cambridge: Mit 
Press, 2009. 
 
HOARE, C. A. R.. Quicksort. ​The Computer Journal​, [s.l.], v. 5, n. 1, p. 10-16, 1 jan. 
1962. 
 
IQBAL, Nadeem. ​et al.​ Formalization of Asymptotic Notations in HOL4. ​2019 Ieee 4th 
International Conference On Computer And Communication Systems. 
Islamabad, p. 383-387. fev. 2019. 
 
JUGÉ, Vincent. Adaptive Shivers Sort: An Alternative Sorting Algorithm. ​SODA '03: 
Proceedings Of The Fourteenth Annual ACM-SIAM Symposium On Discrete 
Algorithms. ​Philadelphia, p. 1639-1654. jan. 2020. 
 
KATAJAINEN, Jyrki; TRÄFF, Jesper Larsson. A Meticulous Analysis of Mergesort 
Programs. ​Algorithms And Complexity​, Berlin, v. 1203, n. -, p. 217-228, mar. 1997. 
 
KITCHIN, Rob. ​Thinking critically about and researching algorithms​. Information, 
Communication & Society. County Kildare, p. 14-29. 25 fev. 2016. 
 
NASAR, Audrey A.. The history of Algorithmic complexity. ​The Mathematics 
Enthusiast. ​Missoula, p. 217-237. ago. 2016. 
17 
 
REILLY, Edwin D.; RALSTON, Anthony; HEMMENDINGER, David. ​Encyclopedia of 
Computer Science​. 5. ed. California: Nature Publishing Group, 2003. 
 
ROUGHGARDEN, Tim. Beyond worst-case analysis. ​Communications Of The 
ACM​, [s.l.], v. 62, n. 3, p. 88-96, 21 fev. 2019.