E2_COAL

Prévia do material em texto

Ariel Da Silva Dias
TIPOS ESPECÍFICOS DE 
ALGORITMOS
Sumário
INTRODUÇÃO ������������������������������������������������� 3
ALGORITMO CONSTANTE ����������������������������� 5
ALGORITMO LINEAR �������������������������������������� 8
ALGORITMO LOGARÍTMICO ������������������������12
ALGORITMO QUADRÁTICO ��������������������������19
ALGORITMO EXPONENCIAL ������������������������23
RECORRÊNCIAS �������������������������������������������25
Função recursiva direta ������������������������������������������������������ 28
Função recursiva indireta ��������������������������������������������������� 30
CONSIDERAÇÕES FINAIS ����������������������������32
REFERÊNCIAS BIBLIOGRÁFICAS & 
CONSULTADAS ��������������������������������������������34
2
INTRODUÇÃO
Ao nos depararmos com um problema computa-
cional, podemos projetar várias soluções, ou seja, 
desenvolvemos diversos algoritmos e escolhemos 
aquele que seja mais eficiente dentre os algoritmos 
desenvolvidos�
Quando um algoritmo usa instruções que são 
executadas apenas uma vez, ele sempre exigirá a 
mesma quantidade de tempo, e quando a instru-
ção está em uma estrutura de repetição, o tempo 
necessário aumenta dependendo do número de 
vezes que esta estrutura é executada�
Além disso, um algoritmo que tem uma combina-
ção de instruções executadas individualmente e 
instruções de repetição únicas ou aninhadas tem o 
tempo aumentado proporcionalmente, com base no 
número de vezes que cada instrução é executada�
Isso nos leva a fazer uma pergunta: como determi-
nar a relação entre a entrada e o tempo, dada uma 
declaração em um algoritmo? Para definir isso, 
estudaremos como cada declaração recebe uma 
ordem de notação para descrever a complexidade 
do tempo, que é chamada de notação Big O�
A complexidade do tempo é dada pelo tempo em 
função do comprimento da entrada� Logo, existe 
uma relação entre o tamanho dos dados de entra-
3
da (n) e um número de operações realizadas (N) 
em relação ao tempo� Essa relação é denotada 
como Ordem de crescimento na complexidade de 
Tempo e dada a notação O[n], em que O é a ordem 
de crescimento e n é o comprimento da entrada�
A notação Big O expressa o tempo de execução de 
um algoritmo em termos de quão rápido ele cresce 
em relação à entrada ‘n’, definindo o número N de 
operações que são feitas nele� Assim, a complexi-
dade de tempo de um algoritmo é denotada pela 
combinação de todos atribuídos a cada linha de 
função�
Existem diferentes tipos de complexidades de tempo 
usadas, vamos verificar uma a uma mais adiante:
 y Tempo constante: O (1) 
 y Tempo linear: O (n) 
 y Tempo logarítmico: O (log n) 
 y Tempo quadrático: O (n²) 
 y Tempo cúbico: O (n³) 
Além desses tipos, existem muitas notações mais 
complexas como tempo exponencial, tempo quasi-
linear, tempo fatorial, entre outros que são usadas 
com base no tipo de funções definidas�
4
ALGORITMO CONSTANTE
Diz-se que um algoritmo tem tempo constante com 
ordem O(1) quando não depende do tamanho da 
entrada n, ou seja, independentemente do tamanho 
de entrada n, o tempo de execução será sempre o 
mesmo� Observe um exemplo na tabela 1�
Tabela 1: exemplo de algoritmo com tempo constante
1 a = 2
2 b = 4
3 total = a + b
4 printf(‘%d’, total)
Fonte: elaborado pelo autor�
Observe com atenção o código da tabela 1� Note 
que ele possui quatro instruções, logo, o tempo de 
execução será 4UT� Nesse caso, se você alterar os 
valores das variáveis a ou b, ou então realizar uma 
outra operação aritmética na linha 3, o algoritmo 
sempre terá a mesma quantidade de instruções, 
independentemente da entrada fornecida� Esse, 
então, é um exemplo de algoritmo constante, pois 
o tempo de execução não é modificado.
Agora, considere o algoritmo da tabela 2, que é 
responsável por retornar o primeiro valor de um 
vetor com n inteiros�
5
Tabela 2: algoritmo para retornar o primeiro inteiro de um 
vetor
1 int primeiroElemento(int vet[]){
2 return vet[0];
3 }
Fonte: elaborado pelo autor�
No algoritmo da tabela 2, temos uma função cha-
mada primeiroElemento, que recebe como parâme-
tro um vetor com n valores inteiros� Observe que 
a única operação do vetor é retornar o valor que 
está na posição de índice zero� Logo, a consulta 
será direta, sem a necessidade de percorrer o ve-
tor inteiro� Deste modo, o número de instruções 
executadas é constante�
Em outras palavras, independentemente do com-
primento do array (n), o tempo de execução para 
obter o primeiro elemento em um array de qualquer 
tamanho é o mesmo� Se o tempo de execução 
for considerado como 1 unidade de tempo, leva 
apenas 1 unidade de tempo para executar ambas 
as matrizes, independentemente do comprimento� 
Assim, a função vem sob tempo constante com 
ordem O(1)�
A figura 1 a seguir representa o comportamento 
da função ao longo do tempo�
6
Figura 1: algoritmo de tempo constante
O(1)
4,5
4
3,5
3
2,5
2
1,5
1
1
0,5
0
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
N
úm
er
o 
de
 O
pe
ra
çõ
es
Tamanho dos dados de entrada
Fonte: elaborado pelo autor�
Observe pelo gráfico que em uma função constante 
o número de operações será sempre o mesmo no 
decorrer do tempo, independentemente do tamanho 
dos dados de entrada, ou seja, sempre teremos 
quatro instruções�
7
ALGORITMO LINEAR
Diz-se que um algoritmo tem uma complexidade 
de tempo linear quando o tempo de execução au-
menta linearmente com o comprimento da entrada� 
Quando a função envolve a verificação de todos 
os valores nos dados de entrada, tal função tem 
complexidade de tempo com ordem O(n) � Observe 
um código de exemplo na tabela 3�
Tabela 3: exemplo de algoritmo de tempo linear
1 int somarElementos(int vet[]){
2 int soma = 0;
3 for(int i=0; ik, 
que é o valor que está sendo procurado no vetor�
Note que o pior caso desse algoritmo será se o 
valor procurado estiver na última posição ou se o 
valor k não estiver presente no vetor� Nesses casos, 
o laço for da linha 2 (e todo o seu escopo) será 
executado obrigatoriamente n vezes� Conforme o 
valor de n aumenta, o tempo de execução, de modo 
linear e proporcional, também aumenta�
Observe na figura 2 o comportamento de uma 
função O(n) no decorrer do tempo de acordo com 
que novos dados vão sendo inseridos em um vetor�
10
Figura 2: algoritmo de tempo linear
N
úm
er
o 
de
 O
pe
ra
çõ
es
10
250
O(n)
20 30 40 50 60 70 80 90 100110120130140150160170180190200
Tamanho dos dados de entrada
200
150
100
50
0
Fonte: elaborado pelo autor�
Nesse algoritmo, observe que quando o tamanho 
dos dados de entrada é igual a 50, por exemplo, 
teremos 50 operações� Em outro caso, se um vetor 
tiver 200 valores armazenados nele, para encontrar-
mos o elemento que está em sua última posição 
(pior caso), serão necessárias 200 operações� 
Essa figura 2 apresenta o comportamento linear 
da função O(n)�
11
ALGORITMO LOGARÍTMICO
Para falarmos dos algoritmos logarítmicos, pri-
meiramente vamos abordar um dos tipos mais 
clássicos de algoritmo: a busca binária� Isso será 
feito pois, em qualquer sistema computacional, a 
busca é uma das funcionalidades mais críticas a 
serem desenvolvidas� As técnicas de pesquisa são 
usadas em recuperações de arquivos, indexação 
e muitas outras aplicações� Existem muitas técni-
cas de pesquisa disponíveis e a técnica de busca 
binária é uma das mais utilizadas�
Um algoritmo de busca binária funciona com a 
ideia de ignorar metade da lista em cada iteração, 
isso quer dizer que ele continua dividindo a lista 
até encontrar o valor que está procurando em uma 
determinada lista� Um algoritmo de pesquisa bi-
nária é uma atualização rápida para um algoritmo 
de pesquisa sequencial (ou linear) simples que foi 
visto anteriormente na tabela 4�
A primeira coisa a notar é que um algoritmo de busca 
binária sempre funciona em uma lista ordenada� 
Portanto, o primeiro passo lógico é classificar a 
lista fornecida� Após a ordenação, a mediana da 
lista é verificada com o valor desejado.
12
 y Se o valor desejado for igual ao valor do índice 
central, o índice será retornado como resposta;
 y Se o valor de destino for menor que o índice 
central da lista, o lado direito da lista será ignorado;
 y Se o valor desejado for maior que o valor do 
índice central, a metade esquerda é descartada; 
O processo apresentado é então repetido em listas 
reduzidas até que o valor alvo seja encontrado�
Vamos então considerar que existe um vetor com 
8 elementos , sendo eles: 3, 6, 7, 8, 14, 15, 23, 27� 
Nessa lista o nosso objetivo é encontrar o valor 27� 
O primeiro passo é encontrar o meio desta lista que, 
neste caso, como são 8 elementos, fica no índice 
4 e o valor é 8. Então, seguiremos a verificação 
citada anteriormente, verificando se o número 
desejado (27) é igual ao valor central, menor ou 
maior� Nesse caso, o valor 27 é maior que o valor 
central, então, certamente 27 não está à esquerda 
do número 8, mas sim, à direita, logo, ignoraremos 
o número 8 e sua esquerda, gerando um subvetor 
com os valores 14, 15, 23 e 27�
O próximo passo agora é dividir este vetor de 4 
valores pela metade e, logo, centro desse vetor 
será o número 15. Realizando a mesma verificação, 
notamos que 27 é maior que 15, logo, ignoraremos 
a metade esquerda dele e analisaremos a metade 
13
da direita� Teremos então um novo subvetor for-
mado pelos valores 23 e 27�
Aplicaremos então a verificação apresentada ini-
cialmente� O número central será o 23� O número 
27 é igual a 23? Não! É menor que 23? Não! Então 
só pode ser maior, logo, ignoramos o número 23 
e dividimos novamente o vetor�
Observe que agora o nosso subvetor possui apenas 
um valor: 27� Vamos dividir esse vetor ao meio, ou 
seja, o centro de um vetor com um valor é o pró-
prio valor. Em seguida, realizaremos a verificação. 
Neste caso, 27 é igual a 27, logo, encontramos o 
valor desejado�
A figura 3 ilustra todo este nosso processo para 
encontrar o número 27 no vetor�
Figura 3: algoritmo de busca binária
3
início
início
início/meio
6 7 8 14 15 23 27
14 15 23 27
23 27
27
meio
meio
fim
fim
fim
Fonte: elaborado pelo autor�
14
Observe pela figura 3 que, para um vetor com n=8 
foram necessárias três instruções de divisão desse 
vetor até encontrarmos o valor 27� Logo, o tempo 
de complexidade é de 3 UT (unidades de tempo)� 
Observe agora a figura 4, que demonstra o mesmo 
algoritmo para encontrar o valor 27, porém agora 
em um vetor com n=4 e outro vetor com n=2�
Figura 4: algoritmo de busca binária, exemplos de n = 4 (a) 
e n= 2 (b)
3
início
(a) (b)
início/meio
início/meio
7 3
14
27
27
meio fim fim
fim
14 27
27
27
Fonte: elaborado pelo autor�
Observe na figura 4(a) que, para um vetor com n=4, 
foram necessárias 2 iterações� De modo seme-
lhante, em um vetor com n=2 tivemos 1 iteração 
para encontrar o valor 27� Observe então a tabela 
comparativa a seguir�
Tabela 5: iterações do algoritmo de busca binária x busca 
sequencial
n iterações (busca 
binária)
iterações (busca 
sequencial)
2 1 2
15
4 2 4
8 3 8
Fonte: elaborado pelo autor�
Observe pela tabela 5 que existe um padrão e é 
esperado que, para um vetor com n=16, o número 
máximo de iterações seja 4� Por seguinte, em um 
vetor com n=32, serão necessárias 5 iterações, e 
assim por diante�
Neste caso temos um algoritmo com tempo lo-
garítmico, que é apresentado na tabela 6 a seguir�
Tabela 6: iterações do algoritmo de busca binária
n iterações (busca 
binária)
Tempo
2 1 log2 2 = 1
4 2 log2 4 = 2
8 3 log2 8 = 3
16 4 log2 16 = 4
32 5 log2 32 = 5
n log2 n
Fonte: elaborado pelo autor�
Note que a expressão que melhor define o tempo 
de execução de um algoritmo de busca binária no 
pior caso é:
(log n)ouLog
2
O
16
Por outro lado, em uma busca sequencial, o número 
de iterações (passos) dentro do vetor será sempre 
relacionado a n e, por esse motivo, uma busca 
sequencial é categorizada como O(n)�
Em outras palavras, um algoritmo tem uma com-
plexidade de tempo logarítmica quando reduz o 
tamanho dos dados de entrada em cada etapa� 
Isso indica que o número de operações não é 
igual ao tamanho da entrada original� O número 
de operações é reduzido à medida que o tamanho 
da entrada aumenta�
FIQUE ATENTO
Algoritmos com complexidade de tempo logarítmica são 
encontrados em árvores binárias ou funções de busca 
binária� Isso envolve a pesquisa de um determinado valor 
em uma matriz, dividindo a matriz em duas e iniciando a 
pesquisa em uma divisão� Isso garante que a operação 
não seja feita em todos os elementos dos dados (como 
ocorre na busca sequencial)�
A figura 5 ilustra o comportamento da função log n.
REFLITASAIBA MAISFIQUE ATENTO
17
Figura 5: algoritmo de tempo logarítmico
N
úm
er
o 
de
 O
pe
ra
çõ
es
O(log n)
9
8
7
6
5
4
3
2
1
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Tamanho dos dados de entrada
Fonte: elaborado pelo autor�
Observe pelo gráfico da figura 5 que, dado um 
aumento no tamanho dos dados de entrada, o nú-
mero de operações executadas sofre um aumento 
menor quando comparado com o comportamento 
do gráfico da figura 2.
18
ALGORITMO QUADRÁTICO
Um dado algoritmo tem uma complexidade de 
tempo não linear (ou quadrática) quando o tempo 
de execução aumenta não linearmente, ou seja, 
(n2), com o comprimento da entrada� Geralmente, 
os loops aninhados estão nessa ordem de comple-
xidade de tempo, em que um loop leva O(n) e se a 
função envolve um loop dentro de um loop, então 
ela vai para O(n) * O(n) = O(n2) iterações�
Considere o algoritmo da tabela 7 a seguir, em 
que há um algoritmo de Bubble Sort, um dos mais 
clássicos algoritmos de ordenação da computação�
Tabela 7: algoritmo de ordenação Bubble Sort�
1 int bubble(int arr[]) {
2 int aux;
3for(int i=0; i vet[j+1]) {
6 aux = vet[j];
7 vet[j] = vet[j+1];
8 vet[j+1] = aux;
9 }
10 }
11 }
12 return arr;
13 }
Fonte: elaborado pelo autor�
19
Observe na tabela 7 que na linha 3 temos uma 
estrutura de repetição for que percorrerá o vetor de 
0 até n, ou seja, até o tamanho máximo do vetor� 
Dentro desse laço de repetição, na linha 4, temos 
outro laço for que inicia em 0 e percorrerá o vetor 
até o final do vetor arr.
O laço de repetição interno, da linha 4, será exe-
cutado em função do laço de repetição da linha 3� 
Logo, se o tamanho do vetor for igual a 5 (n = 5), 
então serão 5 x 5 iterações, ou seja, 25 iterações 
para ordenar o vetor vet�
A notação Big O do algoritmo agora apresentado 
é O(c1 * n2) + O(c2 * n) + O(c3)� Como tomamos 
a maior ordem de crescimento no Big O, nossa 
expressão será reduzida para O(n2)�
Da mesma forma, se houver ‘m’ loops definidos na 
função, então a ordem é dada por O(nm), que são 
chamadas de funções de complexidade de tempo 
polinomial� Observe um exemplo nas tabelas 8 e 
9 a seguir�
Tabela 8: algoritmo com três estruturas de repetição
1 for(int i=0; inão for a última instrução ou 
a última etapa processada pela função, isso quer 
dizer que depois de retornar da pilha de chamadas, 
resta algum código para avaliar� No caso de uma 
função, a chamada recursiva é a primeira instrução 
a ser processada pela função – tal tipo de recursão 
é denominado como recursão de cabeça, pois é 
a primeira chamada e não há nenhuma chamada 
recursiva antes dela;
 y Recursão em árvore: recursão na qual a função 
chama a si mesma por mais de uma vez dentro de 
seu bloco� Se a chamada for feita apenas uma vez 
dentro do bloco de função, ela será chamada de 
Recursão Linear, se for chamada mais vezes, será 
Recursão em Árvore� Um exemplo famoso desse 
tipo de recursão está no problema do enésimo 
número de Fibonacci, em que, dado um número, 
temos que encontrar o enésimo valor do termo na 
série de Fibonacci�
O código da tabela 10 ilustra um exemplo de re-
cursão direta�
Tabela 10: exemplo de recursão direta
1 int funcao(int num){
2 if(num == 0)
3 return 0;
4 Else
29
5 return funcao(num-1);
6 }
Fonte: elaborado pelo autor�
Observe pelo código da tabela 10 que temos, na 
linha 5, a chamada recursiva da função funcao 
enquanto o valor da variável num for diferente de 
zero� Logo, a função é chamada novamente e o valor 
que é passado por parâmetro será decrementado 
em 1� Quando num for igual a zero, a recursividade 
será finalizada.
A complexidade de tempo da recursão da árvore é 
exponencial, pois notamos que o crescimento da 
árvore dobra com cada adição de cada chamada 
recursiva� Portanto, a complexidade é 0(2n) , quando 
n chamadas são feitas�
FUNÇÃO RECURSIVA INDIRETA
Recursão indireta ou recursão mútua é um tipo 
único de recursão, pois ocorre quando função 
(fun1) chama outra função (fun2) e então a outra 
função (fun2) chama a função anterior (fun1) 
novamente direta ou indiretamente� Nesse caso, 
fun1 e fun2 são indiretamente recursivos� Nesse 
tipo de recursão, pode haver mais de uma função 
chamando uma a outra de forma cíclica�
Observe na tabela 11 um exemplo de recursão 
indireta�
30
Tabela 11: exemplo de recursão indireta
1 int funcA(int num){
2 if(num == 0)
3 return 0;
4 Else
5 return funcB(num - 1);
6 }
7 int funcB(int num2){
8 return funcA(num2 - 1);
9 }
Fonte: elaborado pelo autor�
Observe pela tabela 11 que a função funcA invoca 
a função funcB e, por sua vez, funcB invoca funcA� 
Nesse exemplo, existe uma recursividade indireta, 
pois a primeira função invocou uma segunda fun-
ção, e a segunda chamou a original novamente�
Um processo que um método ‘X’ chama o método 
‘Y’, que chama o método ‘Z’, que novamente leva a 
‘X’ ser invocado é chamado de recursivo indireto 
ou mutuamente recursivo�
31
CONSIDERAÇÕES FINAIS
Neste e-book você pôde compreender os diferentes 
tipos de notação de complexidade de tempo dos 
algoritmos� Inicialmente você conheceu a notação 
de tempo constante, em que o valor da entrada 
não varia no decorrer do tempo� Tal notação é 
representada por 0(1)�
Em seguida você conheceu as notações cujo valor 
de n varia ao longo do tempo, começando pela 
notação linear, representada por 0(n), em que n 
representa também o número de instruções que 
serão executadas� Um exemplo de algoritmo nesta 
complexidade é o de busca linear ou sequencial�
Você também pode conhecer a notação 0(n2), nes-
te caso, existe uma estrutura de repetição dentro 
de outra� Alguns exemplos são os algoritmos de 
ordenação Bubble Sort e também o Insertion Sort� 
Vale ressaltar que, de acordo com que você vai adi-
cionando um for dentro do outro, a complexidade 
vai aumentando� Por exemplo, três estruturas de 
repetição, uma dentro da outra, será 0(n3)�
Outra notação estudada foi 0(log n)� Neste caso, 
a ordem de crescimento é logarítmica e o tempo 
de execução é melhor quando se comparado a 
0(n), O(n2) e O(n3)�
32
Por fim, pôde conhecer sobre recursividade, sua 
aplicação e os diferentes tipos de recursão exis-
tentes no desenvolvimento de algoritmos�
33
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]�
	_Hlk95737027
	Introdução
	Algoritmo constante
	Algoritmo linear
	Algoritmo logarítmico
	Algoritmo quadrático
	Algoritmo exponencial
	Recorrências
	Função recursiva direta
	Função recursiva indireta
	Considerações finais
	Referências Bibliográficas & Consultadas