Estudo da Complexidade de Algoritmos

Prévia do material em texto

Ariel Da Silva Dias
ESTUDO DA 
COMPLEXIDADE DE 
ALGORITMOS
Sumário
INTRODUÇÃO ������������������������������������������������� 3
CONTAGEM DE INSTRUÇÕES ������������������������ 7
Contando as instruções ������������������������������������������������������� 8
CONSUMO DE TEMPO ASSINTÓTICO ��������� 19
Melhor caso, pior caso e caso médio �������������������������������� 21
Notação Big-O ��������������������������������������������������������������������� 25
Notação Θ (Teta) ����������������������������������������������������������������� 29
Notação Ω (Ômega) ������������������������������������������������������������ 29
HABILIDADES MATEMÁTICAS 
NECESSÁRIAS ���������������������������������������������31
REVISÃO DOS ALGORITMOS DE 
ORDENAÇÃO E MÉTODOS DE PESQUISA ���� 34
Bubble Sort �������������������������������������������������������������������������� 34
Merge Sort ��������������������������������������������������������������������������� 35
Quick Sort ���������������������������������������������������������������������������� 35
CONSIDERAÇÕES FINAIS ����������������������������36
REFERÊNCIAS BIBLIOGRÁFICAS & 
CONSULTADAS ��������������������������������������������37
2
INTRODUÇÃO
Todos os dias nos deparamos com muitos proble-
mas e encontramos uma ou mais soluções para 
solucioná-los� Dentre essas possíveis soluções, 
algumas podem ser mais eficientes do que outras, 
entretanto, sempre buscamos pela solução mais 
eficiente.
Por exemplo, ao ir de sua casa para seu escritório, 
escola ou faculdade, pode haver “n” número de 
caminhos, entretanto, você escolhe apenas um 
caminho para ir ao seu destino, normalmente o 
caminho mais curto�
Aplicamos a mesma ideia no caso dos problemas 
computacionais ou resolução de problemas via 
computador� Temos um problema computacio-
nal e podemos projetar várias soluções, ou seja, 
algoritmos, e escolhemos o mais eficiente dentre 
os algoritmos desenvolvidos� Um bom algoritmo 
é aquele que pode ser passado para outra pessoa 
seguir sem a necessidade de nenhuma explicação 
extra� O mundo está cheio de algoritmos: receitas 
culinárias, montagem de móveis, trocar o pneu de 
um carro, escovar os dentes, comprar um produto 
em um mercado, entre outros�
Quanto mais você pensa sobre algoritmos, mais 
começa a perceber que tende a seguir muitos 
3
conjuntos de instruções todos os dias� Alguns 
exemplos são claramente sinalizados, enquanto 
outros são mais subtendidos, por exemplo, manter 
o limite de velocidade ao dirigir seu carro, subir 
ou descer uma escada ou seguir um código de 
conduta em uma empresa�
Às vezes, há mais de um algoritmo (ou mais de 
uma maneira) possível para se resolver um pro-
blema� Pense no seguinte caso: Ana é residente 
na cidade de São Paulo e Beatriz é residente na 
cidade de Fortaleza, no estado de Ceará� Em um 
dado dia, Ana resolveu ir passar férias na cada de 
Beatriz� Como ela pode chegar a Fortaleza? Note, 
temos um problema e os possíveis algoritmos para 
resolver este problema são:
1� Ana pode se deslocar até o aeroporto de Gua-
rulhos, em São Paulo, e embarcar em um voo com 
destino a Fortaleza� Do aeroporto, Ana pode pegar 
um táxi até a casa de Beatriz;
2� Ana pode pegar seu carro e sair da cidade de São 
Paulo rumo à Fortaleza, começando pela rodovia 
Fernão Dias, cruzando os estados de Minas Gerais, 
Bahia, Piauí e, por fim, chegar no Ceará;
3� Ana também pode ir pelo mesmo caminho do 
algoritmo 2, porém utilizando sua motocicleta, 
observando a paisagem até chegar em Fortaleza;
4
4. Por fim, Ana pode ir a pé pela rodovia dos Ban-
deirantes, no estado de São Paulo, até chegar na 
casa de sua amiga;
Observe por este exemplo que existem quatro 
modos possíveis para Ana chegar até a casa de 
sua amiga, ou seja, quatro algoritmos para resolver 
o mesmo problema� Cada um desses algoritmos 
possui situações diferentes de deslocamento, bem 
como tempos diferentes� No primeiro algoritmo 
Ana irá de Avião e o tempo total de deslocamento 
até a casa de Beatriz será de aproximadamente 
quatro horas. Por outro lado, no quarto algoritmo 
Ana irá a pé, economizará dinheiro de passagem, 
porém levará 586 horas para chegar até a casa de 
Beatriz – isso se Ana não dormir e não parar em 
nenhum momento!!!
Este é um exemplo simples para demonstrar que 
um mesmo problema pode ter muitas soluções 
diferentes e que uma solução se difere da outra, 
seja em tempo ou em custo� Nos algoritmos 3 e 
4, por exemplo, Ana fará o mesmo caminho, po-
rém o desgaste em se deslocar com o carro será 
menor que o desgaste de se deslocar com uma 
motocicleta�
Dito tudo isso, torna-se necessário que o desen-
volvedor aprenda a comparar o desempenho de 
diferentes algoritmos e escolher o melhor para 
5
resolver um determinado problema� Ao analisar um 
algoritmo, consideramos principalmente a com-
plexidade do tempo e a complexidade do espaço:
• A complexidade de tempo de um algoritmo quan-
tifica a quantidade de tempo que ele levará para ser 
executado em função do comprimento da entrada�
• A complexidade do espaço de um algoritmo quan-
tifica a quantidade de espaço ou memória ocupada 
por um algoritmo para ser executado em função do 
comprimento da entrada�
A complexidade de tempo e espaço depende de 
muitas coisas como hardware, sistema operacional, 
processadores, entre outros� No entanto, durante o 
estudo será considerado apenas o tempo de exe-
cução de um algoritmo, afinal, há um tempo atrás 
a memória era um componente muito caro para 
um computador, logo, havia a preocupação com a 
complexidade de espaço, porém, com a evolução 
da tecnologia, a memória ficou mais barata e hoje 
é o menos preocupante�
6
CONTAGEM DE 
INSTRUÇÕES
A complexidade de tempo de um programa é a 
quantidade de tempo que o computador precisa 
para concluir a execução de determinado progra-
ma� O tempo, T(p), tomado por um programa p, é 
a soma do tempo de compilação e do tempo de 
execução das instruções� O tempo de compilação 
não depende das características da instância� 
Além disso, podemos assumir que um programa 
compilado será executado várias vezes sem re-
compilação� Logo, não consideraremos o tempo 
de compilação, vamos nos preocupar apenas com 
o tempo de execução do programa� O tempo de 
execução é definido por tp (características da 
instância)�
O tempo de execução de um algoritmo é obtido 
contando o número de instruções que ele realiza, 
deste modo entrará em nossa contagem:
 y Atribuição de valores a variáveis;
 y Chamadas de métodos;
 y Operações lógicas e aritméticas;
 y Comparação de dois números;
 y Acesso a elemento de um array;
 y Seguir uma referência de objeto (acesso a 
objeto);
 y Retorno de um método�
7
Mas quanto tempo leva para uma instrução ser 
executada? Depende, pois cada arquitetura com-
putacional possui um desempenho diferente� Logo, 
uma instrução A em um processador X pode levar 
0,01 nanossegundo para executar, enquanto a 
mesma instrução A em um processador Y pode 
levar 1 milissegundo�
Deste modo, neste estudo assumiremos que as 
instruções possuem o mesmo custo, o que chama-
remos de 1UT ou 1 Unidade de Tempo� Por outro 
lado, algumas instruções terão tempo 0, como as 
instruções de seleção�
CONTANDO AS INSTRUÇÕES
Agora que o conceito de contagem de instruções 
foi definido e que uma instrução leva 1UT para 
ser executada, vamos verificar alguns exemplos 
práticos de contagem de instruções� O primeiro 
exemplo está presente na tabela 1: a linguagem é 
parecida com C, porém a mesma análise vale para 
qualquer outra linguagem.
Tabela 1: código com quatro instruções
1 a = 2
2 b = 4
3 total = a + b
4 printf(‘%d’, total)
Fonte: elaborado pelo autor�
8
No código da tabela 1 temos quatro instruções, 
sendo que cada linha é uma instrução diferente. 
Anteriormente foi definido que cada instrução leva 
1UT. Logo, temos que T(p) = 1 + 1 + 1 + = 4� Ou 
seja, este algoritmo leva 4UT para ser executado�
Vamos então para um segundo exemplo, neste 
teremos uma estrutura condicional� Observe entãoa tabela 2 com código em JavaScript – lembre-se, 
não importa a linguagem, a análise está relacionada 
na instrução!
Tabela 2: código com condicional (versão 1)�
1 numero = read();
2 if (numero % 2 == 0)
3 console.log(“par”);
4 if (numero % 2 != 0)
5 console.log(“impar”);
6
7 console.log(numero);
Fonte: elaborado pelo autor�
Observe no código da tabela 2 que a variável núme-
ro recebe uma entrada na linha 1� Em seguida, na 
linha 2, temos uma condicional if que verifica se o 
resto da divisão do número por 2 é igual a zero, ou 
seja, se o valor é par� Se for par, será executada a 
instrução da linha 3. Já na linha 4, será verificado 
se o número é ímpar, caso seja, será executada 
9
a instrução da linha 5. Por fim, será executada a 
instrução da linha 7�
Agora vamos analisar esse código e obter a quan-
tidade de instruções que serão executadas. A ta-
bela 3 a seguir trata da contagem das instruções� 
Observe com atenção�
Tabela 3: contagem das instruções do código com condi-
cional (versão 1)
Código Custo Quantidade de 
execuções
numero = read(); c1 1
if (numero % 2 == 0) c2 1
 console.log(“par”); c3 1
if (numero % 2 != 0) c4 1
 console.log(“impar”); c5 0
0 0
console.log(numero); c6 1
Fonte: elaborado pelo autor�
Na tabela 3 temos a coluna com o código, uma 
coluna chamada custo, com valores c1, c2, c3,���, 
entre outros, e a coluna que marca a quantidade de 
execuções da instrução. Observe que neste caso 
específico consideramos que a análise está sendo 
feita para quando o usuário digita um número par, 
logo, a linha 5 não será executada�
Temos, então, o seguinte resultado da soma de 
tempo:
10
T(p) = 1 * c1 * c2 + 1 * c3 + 1 * c4 + 0 * c5 + 0 + 1 * 
c6
Conforme já foi exposto anteriormente, vamos 
assumir que o custo computacional é 1 para todos. 
Logo temos:
T(p)=1 * 1 + 1 * 1 + 1 * 1 + 1 * 1 + 0 * 1 + 0 + 1 * 
1 = 5 UT 
Logo, nosso algoritmo leva 5 UT para ser executado� 
Apesar de tratar-se de um bom tempo, é possível 
melhorar a execução desse algoritmo? Ou seja, 
é possível diminuir o número de instruções em 
execução? Sim! Assim como no exemplo da Ana 
que estava indo para Fortaleza encontrar a amiga, 
aqui também temos mais de um caminho. Observe 
então o código da tabela 4�
Tabela 4: código com condicional (versão 2)
1 numero = read();
2 if (numero % 2 == 0)
3 console.log(“par”);
4 else
5 console.log(“impar”);
6
7 console.log(numero);
Fonte: elaborado pelo autor�
Observe no código da tabela 4 que adicionamos 
um else na linha 4 e removemos a condicional if� 
Isso foi feito pois um número é par ou ímpar, não 
11
existe uma terceira opção� Logo, o else fará com 
que reduza o número de instruções. Observe agora 
como fica a tabela de contagem de instruções a 
seguir�
Tabela 5: contagem das instruções do código com condi-
cional (versão 2)
Código Custo Quantidade de 
execuções
numero = read(); c1 1
if (numero % 2 == 0) c2 1
 console.log(“par”); c3 1
else 0 0
 console.log(“impar”); c4 0
0 0
console.log(numero); c5 1
Fonte: elaborado pelo autor�
Analisando a tabela 5, temos então o seguinte 
resultado da soma de tempo:
T(p)=1*c1+1*c2+1*c3+0+0*c4+1*c5
Conforme já foi exposto anteriormente, vamos 
assumir que o custo computacional é 1 para todos. 
Logo temos:
T(p)=1*1+1*1+1*1+0+0+1=4 UT
Logo, nosso novo algoritmo leva 4 UT para ser 
executado, uma melhora de 1UT, o que pode ser 
muito significativo em algoritmos maiores. Neste 
caso, o que ocorreria se o número fosse ímpar? O 
12
resultado seria o mesmo, afinal, o else não é uma 
instrução, portanto, se o número for ímpar, a exe-
cução sairá da linha 2 para a linha 5 diretamente�
Até aqui você viu a contagem de instruções em dois 
cenários distintos: em um algoritmo sequencial sem 
condicional e em um algoritmo com condicional� 
Agora vamos contar as instruções de um laço de 
repetição for� Observe o código da tabela 6 a seguir�
Tabela 6: código com estrutura de repetição (versão 1)
1 for(j=0; ja seguinte contagem de 
instruções:
 y Ao iniciar o algoritmo teremos suas instruções, 
que são j = 1 e juma notação dife-
rente para descrever o comportamento limitante 
de uma função�
NOTAÇÃO BIG-O
A notação Big-O (ou simplesmente O) define o 
limite superior de qualquer algoritmo, ou seja, seu 
algoritmo não pode demorar mais do que esse 
tempo. Em outras palavras, podemos dizer que 
a notação O denota o tempo máximo gasto por 
um algoritmo ou a complexidade de tempo do 
pior caso de um algoritmo� Assim, a notação O 
é a notação mais usada para a complexidade de 
tempo de um algoritmo� Logo, se uma função é 
g(n), então a representação O de g(n) é mostrada 
como O(g(n)) e a relação é mostrada como:
O(g(n)) = { f(n): existem constantes positivas c e n0
tal que 0≤f(n)≤g(n) para todo n≥0 }
A expressão pode ser lida como Big-O de g(n) é 
definido como um conjunto de funções f(n) para 
as quais existem algumas constantes c e n0 tais 
que f(n) é maior ou igual a 0 e f(n) é menor ou igual 
a c*g(n) para todo n maior ou igual a n0�
A notação Big-O é a notação mais usada para ex-
pressar a complexidade de tempo de um algoritmo 
25
e você vai perceber isso a partir de um exemplo 
a seguir, em que teremos dois algoritmos para 
encontrar a soma dos n primeiros números�
FIQUE ATENTO
Nos exemplos aqui utilizado estamos considerando 
valores pequenos para n. Entretanto, em casos reais, 
os valores para n serão muito grandes: imagine, por 
exemplo, um sistema para análise de crédito de todos 
os clientes de um banco! São milhares de clientes, ou 
seja, o valor de n (número de clientes) em um banco de 
dados pode ser superior a casa de seis dígitos� Desse 
modo então, na análise assintótica, geralmente lidamos 
com tamanho de entrada n muito grande!
Nesse exemplo, temos que encontrar a soma dos 
primeiros n números� Por exemplo, se n = 4, nossa 
saída deve ser 1 + 2 + 3 + 4 = 10� Se n = 5, então a 
saída deve ser 1 + 2 + 3 + 4 + 5 = 15� Vamos tentar 
duas soluções de algoritmo para resolver esse 
problema e comparar esses códigos�
Tabela 11: solução O(1)
1 int soma(int n) {
2 return n * (n+1)/2;
3 }
Fonte: elaborado pelo autor�
REFLITASAIBA MAISFIQUE ATENTO
26
No código da tabela 11, há apenas uma instrução 
e sabemos que uma instrução leva um tempo 
constante para sua execução� A ideia básica é: se a 
instrução estiver demorando um tempo constante, 
levará a mesma quantidade de tempo para todo o 
tamanho de entrada e denotamos isso como O(1)�
Em outras palavras, se fizermos soma(5000) 
receberemos como resultado a soma dos 5000 
primeiros números em um tempo constante, afi-
nal, temos apenas uma única instrução que será 
executada apenas uma vez. Observe então que, 
independentemente do valor de n, o tempo sempre 
será o mesmo, não tem como ser pior do que esse 
limite constante�
Agora observe com atenção o código da tabela 12, 
que possui uma estrutura de repetição.
Tabela 12: solução O(n)
1 int soma(int n) {
2 int total = 0;
3 for(int i=1; i0,a>0 e a≠1,
𝑦𝑦 = 	 log'	x	se ,somente 	se, x = a0	
A base do logaritmo é a� Isso pode ser lido como 
log base a de x� As duas bases mais comuns usa-
das em funções logarítmicas são a base 10 e a 
base e. Sendo que a função logarítmica com base 
10 é chamada de função logarítmica comum e é 
denotada por log 10 ou simplesmente log�
Nos exemplos a seguir da tabela 13, no lado es-
querdo temos uma equação exponencial e do lado 
direito temos sua forma logarítmica equivalente.
Tabela 13: equação exponencial para forma logarítmica
Equação exponencial Forma logarítmica
32 = 9 2 = log3 9
23 = 8 3 = log2 8
103 = 1000 3 = log10 1000
x16 = 64 16= logx 64
814 = x 4 = log81 x
Fonte: elaborado pelo autor�
As funções logarítmicas possuem algumas das 
propriedades que permitem simplificar os logarit-
mos quando a entrada está na forma de produto, 
quociente ou o valor elevado à potência. Algumas 
das propriedades estão listadas abaixo�
32
Regra do produto
logb MN = logb M + logb NA multiplicação de dois logaritmos de mesma 
base é igual à soma desses logaritmos de base 
igual� Exemplo:
log 30 + log 2 = log (30.2) = log60
Regra do quociente
log$
M
N
= 	log$ 	M− 	log$ 	N
A divisão de dois logaritmos de mesma base é 
igual à subtração desses logaritmos de base igual� 
Exemplo:
log$	56−	 log$	7 = log$	
56
7
= log$	8 = 1
Entender o comportamento das funções logarít-
micas é fundamental para as análises de alguns 
tipos de algoritmos, como é o caso dos algoritmos 
de ordenação e busca binária�
33
REVISÃO DOS 
ALGORITMOS DE 
ORDENAÇÃO E MÉTODOS 
DE PESQUISA
Os Algoritmos de Ordenação são métodos de 
reorganização de um grande número de itens em 
alguma ordem específica, como do maior para o 
menor, ou vice-versa, ou mesmo em alguma ordem 
alfabética�
Esses algoritmos pegam uma lista de entrada, a 
processam (ou seja, executam algumas operações 
nela) e produzem a lista ordenada�
Neste primeiro momento, apresentaremos os 
principais algoritmos de ordenação e métodos 
de pesquisa, não entrando (ainda) em detalhes 
sobre sua complexidade, logo, trata-se de uma 
breve revisão�
BUBBLE SORT
Bubble sort é um algoritmo de ordenação sim-
ples que percorre repetidamente a lista, compara 
elementos adjacentes e os troca se estiverem na 
ordem errada� Esse é o algoritmo mais simples e 
ineficiente ao mesmo tempo. No entanto, é muito 
34
necessário aprender sobre isso, pois representa 
os fundamentos básicos da classificação.
MERGE SORT
O Merge sort é um dos algoritmos de ordenação 
mais eficientes e funciona no princípio da Divisão 
e Conquista. O merge sort divide repetidamente 
uma lista em várias sublistas até que cada uma 
delas consista em um único elemento, além disso, 
ele mescla essas sublistas de uma maneira que 
resulte em uma lista classificada.
QUICK SORT
O nome “Quick Sort” vem do fato de que ele é ca-
paz de ordenar uma lista de elementos de dados 
significativos mais rapidamente (duas ou três vezes 
mais rápido) do que qualquer um dos algoritmos 
de ordenação� Trata-se de um dos algoritmos de 
ordenação mais eficientes e baseia-se na divisão de 
um array em outros menores e na troca com base 
na comparação com o elemento ‘pivô’ selecionado� 
Devido a isso, o quick sort também é chamada de 
classificação “Partition Exchange”. Assim como a 
ordenação por merge sort, o quick sort também 
se enquadra nas categorias de abordagem de 
divisão e conquista da metodologia de resolução 
de problemas�
35
CONSIDERAÇÕES FINAIS
Neste e-book você pôde compreender o conceito de 
algoritmos como uma ferramenta para resolução 
de problemas� Conforme foi apresentado, existem 
diversos algoritmos para resolver um mesmo pro-
blema, conforme ilustrado no exemplo de Ana que 
deseja ir visitar sua amiga em Fortaleza, partindo 
de São Paulo�
Você também conheceu os conceitos de melhor 
caso, pior caso e caso médio, que são os possíveis 
casos que um algoritmo pode se enquadrar. Por 
exemplo, tendo um molho com 10 chaves, encontrar 
“de primeira” a chave que abre a gaveta é o melhor 
caso, por outro lado, encontrar na décima tentativa 
a chave que abre uma gaveta ou não encontrar a 
chave seriam os piores casos� Todas as outras 
possibilidades se enquadram no caso médio.
Você também pôde compreender o que é notação 
assintótica e o crescimento assintótico de um al-
goritmo, que pode ser realizado após a contagem 
de instruções de um dado código�
Por fim, pôde relembrar os conceitos de logarit-
mos e também rever os principais algoritmos de 
ordenação�
36
Referências Bibliográficas 
& Consultadas
BORIN, V. P. Estrutura de dados. Curitiba: 
Contentus, 2020. [Biblioteca Virtual].
CAMPOS FILHO, F. F. Algoritmos numéricos: 
uma abordagem moderna de cálculo numérico. 
3. ed. Rio de Janeiro: LTC, 2018. [Minha 
Biblioteca].
CORMEN, T. H. Desmistificando algoritmos. 
1. ed. Rio de Janeiro: LTC, 2014. [Minha 
Biblioteca].
DROZDEK, A. Estrutura de dados e 
algoritmos em C++. 4. ed. Cengage Learning, 
2017. [Minha Biblioteca].
GOLDBARG, M. C.; GOLDBARG, E. G., LUNA, 
H. P. L. Otimização combinatória e meta-
heurísticas: Algoritmos e Aplicações. 1. ed. 
Rio de Janeiro: GEN / Elsevier, 2016. [Minha 
Biblioteca].
PINTO, R. A.; PRESTES, L. P.; SERPA, M. S.; 
COUTO, J. M. C.; BIANCO, C. M.; NUNES, P. 
C. M. Estrutura de dados. Porto Alegre: Sagah, 
2019. [Minha Biblioteca].
TOSCANI, L. V., VELOSO, P. A. S. 
Complexidade de algoritmos. 3. ed. Porto 
Alegre: Bookman, 2012. [Minha Biblioteca].
WAZLAWICK, R. S. Introdução a algoritmos 
e programação com Python: uma abordagem 
dirigida por testes; 1. ed. Rio de Janeiro: 
Elsevier, 2017. [Minha Biblioteca].
	Introdução
	Contagem de instruções
	Contando as instruções
	Consumo de tempo assintótico
	Melhor caso, pior caso e caso médio
	Notação Big-O
	Notação Θ (Teta)
	Notação Ω (Ômega)
	Habilidades matemáticas necessárias
	Revisão dos algoritmos de ordenação e métodos de pesquisa
	Bubble Sort
	Merge Sort
	Quick Sort
	Considerações finais
	Referências Bibliográficas & Consultadas