DEV Community: Mateus Costa

Um resumo sobre: grafos.

Mateus Costa — Wed, 15 Mar 2023 20:52:27 +0000

Introdução:

Embora os grafos tenham nós conectados por arestas, eles são diferentes das árvores, uma vez que os grafos não possuem uma estrutura hierárquica como a árvore que possui raiz, pais e filhos. Além disso, os grafos podem ter ciclos e possuem arestas direcionadas e não direcionadas, enquanto a árvore não tem ciclos e suas arestas não são direcionadas.
A primeira figura é uma árvore, enquanto a segunda é um grafo:

Conceitos Básicos:

Agora irei abordar alguns conceitos básicos sobre os grafos:

Adjacência: Quando um nó é conectado ao outro por uma única aresta. Exemplo: o 5 é adjacente do: 6, 9, 4.

Caminhos: sequência de arestas;
Grafos conectados e não conectados:

Grafos orientados: quando há uma orientação quanto a direção. Exemplo: o 7 vai até o 11, mas o 11 não vai até o 7.

Grafos ponderados: Cada aresta tem um peso ou valor associados a ela.

Logo abaixo está um exemplo de um grafo orientado e ponderado:

Nós e arestas: Um nó pode representar um objeto da vida real (uma cidade, por exemplo) e uma aresta é o caminho até este nó.
Representação: Matriz de adjacência e lista de adjacência.

Algoritmos de Busca:

Busca em profundidade:

A busca em profundidade (DFS, do inglês Depth-First Search) é um algoritmo de busca utilizado em grafos que percorre o grafo explorando o máximo possível em profundidade antes de retroceder para explorar outros ramos do grafo.
O algoritmo funciona da seguinte forma:

Começa-se a partir de um vértice inicial, marcando-o como visitado e empilhando-o em uma pilha.
O algoritmo escolhe um vértice da pilha e verifica se ele possui vértices adjacentes ainda não visitados. Se existirem, um deles é escolhido e marcado como visitado, empilhado na pilha e o passo 2 é repetido a partir deste vértice.
Se todos os vértices adjacentes já tiverem sido visitados, o algoritmo desempilha o vértice atual e continua no vértice anterior.
O algoritmo continua este processo até que a pilha esteja vazia.

A busca em profundidade visita todos os vértices e arestas do grafo que são alcançáveis a partir do vértice inicial. É possível modificar o algoritmo para encontrar caminhos específicos ou para percorrer o grafo de outras formas, por exemplo, visitando os vértices em ordem lexicográfica.
O tempo de execução do algoritmo de busca em profundidade depende do tamanho do grafo e da estrutura de dados utilizada para armazená-lo. Em geral, o tempo de execução é proporcional ao número de vértices e arestas do grafo, ou seja, O(V + E).

Busca em Largura:

A busca em largura (BFS, do inglês Breadth-First Search) é outro algoritmo de busca utilizado em grafos que percorre o grafo em largura, ou seja, visita todos os vértices em uma mesma profundidade antes de avançar para a próxima profundidade.
O algoritmo funciona da seguinte forma:

Começa-se a partir de um vértice inicial, marcando-o como visitado e inseri-lo em uma fila.
O algoritmo retira um vértice da fila e verifica se ele possui vértices adjacentes ainda não visitados. Se existirem, um deles é escolhido e marcado como visitado, inserido na fila e o passo 2 é repetido a partir deste vértice.
O algoritmo continua a retirar vértices da fila e adicionar seus vizinhos na fila até que a fila esteja vazia. A busca em largura visita todos os vértices e arestas do grafo que são alcançáveis a partir do vértice inicial em ordem crescente de profundidade. O algoritmo também pode ser utilizado para encontrar caminhos mais curtos entre dois vértices.

Busca Gulosa:

A busca gulosa (também conhecida como busca heurística) é um algoritmo de busca em grafos que utiliza uma heurística para escolher o próximo nó a ser explorado. A heurística é uma função de avaliação que estima o quão promissor é um determinado nó em relação ao objetivo final da busca.
Em cada passo, a busca gulosa escolhe o nó com a melhor estimativa heurística e explora seus vizinhos. O objetivo é chegar ao nó objetivo com a menor quantidade de passos possível.
No entanto, a busca gulosa pode levar a soluções subótimas, já que a escolha do próximo nó a ser explorado é baseada apenas na heurística e não leva em consideração o caminho percorrido até o momento.
Por exemplo, imagine que um caminho longo pareça promissor com base na heurística, mas um caminho mais curto seria mais eficiente. A busca gulosa pode escolher o caminho longo e, portanto, não encontrar a solução mais otimizada.
Apesar dessa limitação, a busca gulosa pode ser uma boa opção para grafos muito grandes ou para problemas onde a solução ótima não é crucial. É importante, no entanto, escolher uma boa heurística para maximizar a eficiência do algoritmo.

O tempo de execução do algoritmo de busca em largura também depende do tamanho do grafo e da estrutura de dados utilizada para armazená-lo. Em geral, o tempo de execução é proporcional ao número de vértices e arestas do grafo, ou seja, O(V + E). No entanto, a busca em largura geralmente é mais lenta que a busca em profundidade em grafos densos, já que requer a criação de uma fila para armazenar todos os vértices a serem visitados.

Busca A *:

A busca A* (A-star) é um algoritmo de busca heurística que também é usado para encontrar o caminho mais curto entre um nó de partida e um nó de destino em um grafo ponderado. É semelhante à busca gulosa em que utiliza uma heurística para estimar a distância do nó atual até o nó de destino, mas também leva em consideração o custo do caminho percorrido até o momento.
O algoritmo A* usa uma função de avaliação que combina a heurística e o custo do caminho até o nó atual. A função de avaliação é definida como f(n) = g(n) + h(n), onde g(n) é o custo do caminho do nó inicial até o nó atual e h(n) é a estimativa heurística da distância do nó atual até o nó de destino. O objetivo da busca é encontrar o caminho com o menor valor de f(n).
A busca A* é considerada uma das melhores técnicas para encontrar o caminho mais curto em um grafo ponderado porque é completa (encontra uma solução se ela existe) e ótima (encontra a solução com o menor custo possível). No entanto, ela pode ser mais lenta do que a busca gulosa, dependendo da heurística escolhida e da complexidade do grafo.

Nestas duas imagens veremos a diferença entre a busca gulosa (imagem 1) e a busca A*:

Estas imagens representam um caminho entre uma cidade e outra, para montar um algoritmo eficiente para traçar um caminho entre as duas cidades, nós podemos utilizar a busca gulosa e a busca A*. Na busca gulosa foi levada em consideração somente a heurística, em que as cidades que seriam percorridas seriam a com menor distância entre o destino. Já na busca A*, além desse parâmetro, foi utilizado também o ‘peso’ do vetor, que seria a distância entre as cidades adjacentes.

Algoritmo de Dijkstra:

O algoritmo de Dijkstra é um método utilizado para encontrar o caminho mais curto em um grafo com arestas não negativas, partindo de um vértice de origem. Ele seleciona os vértices com as menores distâncias da origem e atualiza as distâncias dos vértices adjacentes caso seja possível encontrar um caminho mais curto. Esse processo continua até que todas as distâncias tenham sido determinadas. No final, o algoritmo retorna a distância mais curta de cada vértice para a origem e o caminho mais curto correspondente.

Veja na imagem que ele foi de A até F e escolheu o menor caminho vendo o todo:

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: Estruturas de dados e algoritmos em python

Um resumo sobre: árvore binária de busca.

Mateus Costa — Sun, 12 Mar 2023 23:46:39 +0000

Introdução:

Uma árvore binária combina as vantagens de duas estruturas:

Um vetor ordenado e uma lista encadeada.

Vantagens:

Busca rápida como um vetor ordenado;
Inserção e exclusão é rápida como uma lista encadeada;

Olhe a representação de duas árvores, a primeira é a árvore do sistema operacional Linux e a segunda é uma árvore do HTML:

Vamos falar agora mais especificamente sobre a árvore binária:

Ela consiste em nós conectados por arestas;
Esse tipo de árvores tem no máximo dois filhos (um filho à esquerda e outra à direita);
Mas também pode ter um ou nenhum filho.

Repare na imagem:

Existem algumas terminologias que também precisamos saber:

Caminho: que liga um nó até o outro. Lembre-se que a aresta é a conexão direta entre dois nós adjacentes e o caminho é uma sequência de arestas que conectam dois nós diferentes em uma árvore;
Raiz: é o nó na parte superior, no caso da figura acima, a raiz é o número 2. Lembrando que há apenas uma raiz em uma árvore e deve haver somente um caminho da raiz até qualquer outro nó. Olhe esse exemplo de um grafo, que não é uma árvore:
Pai: qualquer nó, exceto a raiz, tem uma aresta acima dele que sobe para outro nó. Esse nó de cima é chamado de pai do nó;
Filho: o nó pode ter um ou dois nós ligados diretamente abaixo dele, esses nós que estão abaixo, são os filhos do nó de cima;
Folha: é um nó que não tem filhos;
Subárvore: qualquer nó pode ser considerado a raiz de uma subárvore, que consiste em seus filhos(na imagem acima podemos considerar uma subárvore em que a raiz é o 7, ou outra subárvore que a raiz é o nó número 5);
Visitando: um nó é visitado quando o controle do programa chega ao nó, em geral para a finalidade de executar alguma operação no nó;
Percorrendo: visitar todos os nós em alguma ordem específica;
Níveis: refere-se quantas gerações o nó está da raiz;
Chaves: valor utilizado para buscar um item.

Dentro da árvore binária, existe um tipo específico, que é a árvore binária de busca:

O filho à esquerda do pai, tem que ter uma chave menor que o pai e o filho à direita de um nó tem que ter uma chave maior ou igual ao seu pai;

Vamos analisar a partir de agora como funciona a inserção, a pesquisa e a exclusão neste tipo de estrutura.

Inserção:

O local para inserir deve ser encontrado;
Segue-se o caminho da raiz até o devido nó, que será o pai do novo nó;
Quando o pai for localizado, o novo nó será conectado como seu filho à direita ou à esquerda(dependendo da chave do novo nó ser maior ou menor que o pai);
Para um melhor visualização, crie sua árvore acessando este link;
Em relação ao Big-O, para a inserção é O(log n) para caso médio e O(n) para o pior caso.

Veja na imagem um algoritmo de inserção em uma árvore binária feito em python:

Pesquisa:
Para realizarmos a pesquisa em uma árvore binária, nós iremos procurar nas sub árvores direita e esquerda. É possível ter uma melhor visualização acessando este link. Já em termos do Big-O, teremos O(log n) em casos médios e O(n) no pior caso.

Aqui está um algoritmo de pesquisa feito em python para a pesquisa de um nó em uma árvore binária:

Existem três principais ordens para visitar uma árvore binária:

Pré-ordem (Pre-order): Começando pela raiz da árvore, visite cada nó primeiro antes de visitar seus filhos. Em outras palavras, a visita começa pelo nó raiz, depois visita o filho esquerdo e, em seguida, visita o filho direito. A ordem de visita é: raiz, filho esquerdo, filho direito.
Em-ordem (In-order): Visite o filho esquerdo, depois a raiz e, em seguida, o filho direito. A ordem de visita é: filho esquerdo, raiz, filho direito. Essa ordem é especialmente útil quando a árvore binária representa uma expressão matemática, onde a ordem de precedência dos operadores é levada em consideração. Retorna os números em ordem crescente.
Pós-ordem (Post-order): Visite cada filho antes de visitar a raiz. Em outras palavras, a visita começa pelo filho esquerdo, depois visita o filho direito e, em seguida, visita a raiz. A ordem de visita é: filho esquerdo, filho direito, raiz. Essas ordens de visita podem ser usadas para resolver problemas específicos, dependendo das necessidades da aplicação.

Algoritmo em python representando a pré-ordem, ordem e pós-ordem, respectivamente:

Exclusão:
Para excluir um dado em uma árvore binária de busca, existem alguns cenários:

O nó a ser apagado é uma folha (maneira mais simples);
O nó a ser apagado tem um filho;
O nó a ser apagado tem dois filhos (maneira mais difícil)

Dessa maneira, para o processo de exclusão, precisamos primeiro pesquisar o elemento que queremos apagar e depois identificar em qual dos três casos ele se encaixa. Aqui um algoritmos que representa a parte da pesquisa:

A segunda parte, caso o nó a ser apagado fosse uma folha:

A segunda parte caso o nó a ser apagado tiver somente um filho:
Neste caso, nós iremos cortá-lo e conectar o filho dele com o pai. Além disso, iremos verificar se ele não possui filho à direita ou à esquerda.
Para uma melhor visualização acesse este link.

A segunda parte caso o nó a ser apagado possuir dois filhos:

Ele deve ser substituído pelo seu sucessor em ordem (direita esquerda). Para melhor visualização, lembre de utilizar o link anterior.
Neste exemplo, se excluirmos o número 66, o que irá entrar no lugar dele será o sucessor em ordem, que é o 73. O próximo, maior que ele.

Primeiro passo que iremos fazer neste processo é encontrar o sucessor, com isso iremos fazer uma função para encontrar o sucessor de um número. O função será esta:

E para realizar o processo de exclusão é só localizar o sucessor e realizar as devidas trocas, dessa maneira:

O código completo para exclusão, inserção e pesquisa, está neste link.

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: Estruturas de dados e algoritmos em python

Um resumo sobre: algoritmos de ordenação.

Mateus Costa — Tue, 07 Mar 2023 01:04:15 +0000

Introdução.
Após a construção de uma base de dados, pode ser necessário a ordenação dessas informações. Essa ordenação pode ser nomes em ordem alfabética, endereço pelo cep, vendas por preço, cidades em ordem crescente de população e etc. Ter esses dados ordenados faz com que tenhamos performance na pesquisa de dados, por exemplo, escolhendo a pesquisa binária O(log n), no lugar da linear O(n). Você pode saber mais sobre pesquisa linear e binária com este link e notação Big-O, para entender sobre a comparação da complexidade de algoritmos pela entrada que ele recebe, neste link.
Sempre bom termos em mente, quando pensamos em dados, é pensar na inserção, exclusão e pesquisa dos dados. Se por um lado a pesquisa de dados em vetores ordenados é mais performática que em vetores não ordenados, pela possibilidade que realizar a pesquisa binária, por outro lado, em vetores ordenados, a performance para inserção de dados pode não ser tão boa quanto em vetores não ordenados, uma vez que para inserir em um vetor ordenado, iremos precisar pesquisar onde o dados irá ser inserido e deslocar os demais dados para que o elemento em questão ocupe a sua devida posição.
Aí entra a estrutura de ordenação de dados, para inserirmos com a agilidade dos vetores não ordenados e pesquisarmos com a rapidez dos vetores ordenados. Para entendermos como funcionam esses algoritmos de ordenação, iremos ver: bubble sort (bolha), selection sort (seleção), insertion sort(inserção), shell sort, merge sort e quick sort.

Bubble Sort (bolha).
O mais lento e simples de todos os algoritmos de ordenação.
Ele funciona da seguinte maneira:

Compara dois números, se o da esquerda for maior, os elementos devem ser trocados, sendo que o menor se desloca uma posição à esquerda.
À medida que o algoritmo avança, os itens maiores “surgem como uma bolha” na extremidade superior do vetor.

Com este link podemos ter uma excelente noção de como funciona esta estrutura de ordenação com o passo a passo (é muito importante acessarem o último link para ver o algoritmo em funcionamento). Em uma visão geral, caso tenhamos um vetor com 10 elementos, o algoritmo fará 9 comparações na primeira rodada, 8 na segunda, 7 na terceira e assim por diante. Neste caso, ele fará 45 comparações. O Big-O dele será quadrático O(n²), sendo assim, o algoritmo irá comparar, aproximadamente, (n² / 2) comparações. Nós dividimos por 2, pois é uma média. No caso de 10 elementos, dará aproximadamente 50 passos. Nesse caso, foram exatamente 45 passos, pois o valor é aproximado. Em 99% das vezes temos mais comparação do que trocas de fato dos valores, uma vez que os valores só serão trocados quando houver necessidade.

Aqui está um algoritmo feito em python utilizando a ideia de bubble sort:

Selection Sort (seleção):
Melhora a ordenação do método da bolha, uma vez que a selection sort reduz o número de trocas necessárias, reduzindo de N² para N. Entretanto, o número de comparações permanece N².
Esta estrutura funciona da seguinte maneira:

Percorre todos o elementos e seleciona o menor;
O menor elemento é trocado com o elemento da extremidade esquerda do vetor(posições iniciais);
Os elementos se organizam à esquerda, diferente da bolha que organiza seus elementos à direita.

Neste link, você selecione o selection sort e assista calmamente como ocorre o processo. Repare que o algoritmo faz a varredura e marca o menor valor com a cor vermelha. Ao final do processo, o menor se deslocará para o início.
Em uma visão geral, caso tenhamos um vetor com 10 elementos, funcionará da mesma maneira que o bubble sort na COMPARAÇÃO:

O algoritmo fará 9 comparações na primeira rodada, 8 na segunda, 7 na terceira e assim por diante. Neste caso, ele fará 45 comparações. O Big-O dele será quadrático O(n²), sendo assim, o algoritmo irá comparar, aproximadamente, (n² / 2) comparações. Nós dividimos por 2, pois é uma média. No caso de 10 elementos dará aproximadamente, 50 passos. Nesse caso, foram exatamente 45 passos, pois o valor é aproximado. Aqui está a grande diferença entre o bubble sort e o selection sort: enquanto o bubble sort precisará de 3 passos vezes o número de trocas sendo que no pior dos casos no selection, nós iremos realizar 10 passos.

Aqui está um algoritmo feito em python utilizando a ideia de Selection Sort:

Insertion Sort:
Essa é a ordenação por inserção, sendo duas vezes mais rápida do que a bubble sort e um pouco mais ágil que a selection sort. Em questão de funcionamento, ela age da seguinte forma:

Há um marcador no meio do vetor;
Os elementos à esquerda estão parcialmente ordenados (ordenados entre eles, porém não estão na posição final);
Os elementos à direita do marcador não estão ordenados;

Repare que o vermelho é a posição marcada do vetor. Ele irá procurar a posição que ele irá ocupar à direita:

Repare que o elemento vermelho foi inserido e agora o elemento marcado é o verde:

Com este link você clica em insertion sort e veja como funciona este algoritmo de ordenação.
Para esta estrutura, faremos as seguintes análises:

Para dados que já estão parcialmente ordenados, esta estrutura de ordenação pode ser mais eficiente que as outras apresentadas até aqui;
Se os dados estiverem em ordem inversa, esse método é mais lento que o método da bolha;
Em termos de comparação dos dados, este tem uma média de metade dos passos das ordenações bubble e selection.

Aqui está um algoritmo feito em python utilizando a ideia de Insertion Sort:

Shell Sort (Shell -> pesquisador que inventou esse de algoritmo)

Este algoritmo melhora a ordenação do insertion sort, assim, podemos dizer que é uma versão melhorada do insertion.

Ele funciona da seguinte maneira:

O vetor original é quebrado em subvetores;
Cada subvetor é ordenado comprando e trocando os valores;
No final da rodada esse subvetor é quebrado em mais um subvetor. Observe nesta imagem:

O vetor é dividido no meio. Pegou a posição 0, pulou duas posições e pegou a posição 3. Ele compara os valores e joga o menor para a esquerda e o maior para a direita. Em seguida, pula uma casa, o que estava no 0 vai para o 1 e o que estava no 3 vai para o 4, em seguida faz novamente a comparação. Esse procedimento segue até terminar. Após isso, ele é quebrado novamente no meio.

Neste link você terá uma melhor noção de como funciona este algoritmo de ordenação.

A complexidade deste algoritmo dependerá dos intervalos escolhidos, sendo que o pior caso será O(n²) e o melhor caso O(n * log n). Lembrando que o melhor caso do selection sort é O(n²) e do bubble sort é O(n²)

Merge Sort(juntar):
Um dos algoritmos de ordenação mais populares, o merge sort funciona da seguinte maneira:

Ele segue a premissa de dividir para conquistar, com isso, ele divide a lista diversas vezes até ter um único elemento;
Após dividir ao máximo, ele vai juntando(merge) e ordenando.

Veja o fluxograma para uma melhor visualização:

Em relação a notação Big-O, no pior e no melhor caso são O(n* log n). Em comparação com o bubble sort e o selection sort, o merge sort é melhor, uma vezes que os outros são O(n²) e o shellsort, no pior caso é O(n²) e no melhor é O(n*log n).

Esse algoritmo feito em python exemplifica o modelo merge sort:

Quick Sort:
É um algoritmo rápido e eficiente criado em 1960, sendo que seu funcionamento consiste da seguinte forma:

O vetor é dividido em sub vetores e é chamado recursivamente para ordenar os elementos;
Utiliza a estratégia da divisão e conquista.

Esse algoritmo possui um conceito de elemento pivô, sendo que a cada rodada ele compara esse elemento com os demais da lista. O elemento que inicia como pivô é o da posição 0. Na comparação, os elementos menores são dispostos do lado esquerdo e os maiores do lado direito, após a comparação o pivô toma a posição do meio, sendo que os maiores ficarão à direita e os menores à esquerda.

Repare que neste vetor, o pivô é o número 27 e os elementos verdes são menores e os roxos estão à direita:

Agora o 27 toma a posição do meio, trocando com o 16 que está na última posição entre os menores:

Agora o 27 é o final da lista e o 16 será o pivô, repare que agora todos os números maiores que o da posição 6 são maiores que o 16 e lembre-se que ele irá medir até o 27, porque os acima são obrigatoriamente maiores:

Agora o 16 irá trocar com o 6 e o 16 passará a ser o final e o 6 passará a ser o pivô:

Depois de realizar as comparações, o 6 irá trocar de lugar com o 3 e do 3 até o 15 já está ordenado e o 25 passará a ser o pivô:

Depois do reajuste do 25, terminamos a parte da esquerda. Agora iniciamos a parte da direita com o pivô como 32 e assim ficará depois das comparações:

Assim irá até o final. Para uma melhor visualização, acesse este link e clique no botão quick sort.

O pior caso dessa ordenação será O(n²) e o melhor caso O(n * log n).

Aqui está um algoritmo de ordenação quick sort feito em python:

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: Estruturas de dados e algoritmos em python

Um resumo sobre: recursão.

Mateus Costa — Tue, 28 Feb 2023 19:55:55 +0000

Introdução:
Neste resumo irei dar uma breve explicação sobre recursão e mostrar a diferença entre ela e o laço de repetição. Sendo assim, aqui irei abordar os seguintes tópicos:

Conceito geral sobre recursão;
Diferenças entre recursão e laço de repetição;
Quando utilizar laço e quando utilizar recursão.

Conceito geral sobre recursão:

Muito utilizada em estruturas mais complexas, a recursão ocorre quando uma função chama ela mesma até a sua resolução. Dessa maneira, é utilizada quando é necessário fazer uma repetição de tarefas, mas que um laço de repetição não é adequado. Essa imagem do Bob Esponja, representa muito bem a ideia de recursão e em que tipo de estrutura devemos utilizá-la.

Diferenças entre recursão e laço de repetição:

Antes de partirmos para exemplos práticos, vamos pensar em problemas do dia a dia da programação. Vamos supor que você precisa contar a quantidade de comentários de uma postagem, entretanto cada comentário permite a inserção de outro comentário e esse comentário do comentário, pode ter um outro comentário nele e assim por diante. Problemas assim que a recursão pode ser uma mão na roda. Além desses, problemas básicos como fatorial ou exponenciação também podem ser resolvidos com recursão.

Veremos alguns exemplos práticos:

Utilizando laço de repetição:

Utilizando a técnica de recursão para a mesma solução:

Repare que na recursão precisamos ter uma variável que irá controlar a quantidade de chamadas, uma vez que se não houver, a recursão será infinita.
Lembrando que quando nós fazemos essas chamadas da função no retorno, essas funções vão entrando na pilha de processamento. Quando terminar essas chamadas, as funções irão desempilhando(FILO - first in last out) uma a uma.

Repare agora outro exemplo da diferença entre um laço de repetição e uma função recursiva:

Agora olhe que interessante quando comparamos a performance das estruturas utilizando o TimeIt do python:

A recursão neste caso é menos performática do que o laço, sendo quase o dobro do tempo do laço. Isso, pode se dar ao fato da recursão empilhar as chamadas e desempilhá-las após o término das chamadas e também do laço agir de forma linear sem o empilhamento da estrutura.

Portanto, uma função recursiva ela:

Chama ela mesma;
Precisa ser controlada para não gerar um looping.
A cada chamada ela se aproxima do fim;

Dentro da recursão podemos ter a recursão direta (quando uma função chama ela mesma), recursão indireta (quando ela chama outra função e essa outra função chama ela novamente), função recursiva em cauda (quando a chamada da recursividade é a última a ser executada) e por último temos a função non-tail recursive (função sem cauda).

Deixarei mais dois algoritmos utilizando recursão em Python. O primeiro calcula o fatorial e o segundo calcula o exponencial:

Quando utilizar laço e quando utilizar recursão:

Por fim, utilizamos recursão quando:

O problema pode ser dividido em subproblemas menores e idênticos ao problema original.
A solução do problema original depende da solução dos subproblemas menores.
A estrutura de dados subjacente ao problema é naturalmente recursiva, como árvores ou grafos.
A recursão torna a solução mais fácil de entender e manter .

Utilizamos laço quando:

O problema não pode ser facilmente dividido em subproblemas menores.
A solução do problema não depende da solução de subproblemas menores.
A estrutura de dados subjacente ao problema é linear, como uma lista ou matriz.
O desempenho é uma consideração importante, já que a recursão pode ser mais lenta do que o loop devido ao overhead (custo adicional) da pilha de chamadas.

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: Estruturas de dados e algoritmos em python

Um resumo sobre: listas duplamente encadeadas.

Mateus Costa — Mon, 27 Feb 2023 20:33:07 +0000

Para um melhor entendimento deste resumo, leia sobre lista encadeada simples, pois lá faço uma boa introdução sobre as listas encadeadas.
Aqui irei abordar sobre as listas duplamente encadeadas.

Fechando o tema de listas encadeadas, vou para este último tópico:

As listas encadeadas simples, possuem algumas limitações, por exemplo, quando percorremos este tipo de estrutura, ao avançarmos, nós não poderemos retroceder, pois o caminho delas são da esquerda para a direita, mas não percorrem da direita para a esquerda. As listas duplamente encadeadas, resolvem este problemas, uma vez que os nós apontam para o valor anterior e o próximo. Perceba a diferença entre elas.
Listas encadeadas com extremidades duplas:

Listas duplamente encadeadas:

Para inserir um elemento no início, nós iremos:
1- Criar um nó com o anterior igual a none;
2- Colocar o “próximo” do novo elemento vai apontar para o primeiro elemento (que será o segundo);
3- O antigo primeiro elemento, não aponta mais o “anterior” para o nulo, mas, sim, para o que será o primeiro elemento;
4- A cabeça da lista agora apontará para o novo elemento e não para o antigo.
Com essa imagem ficará mais claro:

Podemos também inserir um elemento no final da lista:
1- Criar um nó que o “próximo” aponta para nulo;
2- Apontar o anterior do novo para o elemento que era o último e agora será o penúltimo;
3- Cortamos a ligação do posterior do atual penúltimo com o nulo e ligamos ao atual último;
4- Retiramos o link que aponta o antigo último e colocamos ele apontando para o novo elemento.
Com a imagem ficará mais fácil a visualização:

Para excluir no início:
1- Colocamos o anterior da segunda posição apontando para o nulo,
2- Colocamos a referência “cabeça de lista” apontando para o segundo.

Para excluir no final da lista:
1- Apontar o “próximo” do penúltimo ao valor nulo;
2- Apontamos a referência do último ao nó penúltimo.

Excluir na posição:

1- Fazer pesquisa para saber qual elemento apagar (pode ser da direita para a esquerda ou da esquerda para a direita),
2- Apontar o próximo do anterior do atual para o próximo do atual,
3- Apontar o anterior do próximo do atual para o anterior do atual,
4- Lembrando que nenhum elemento é apagado em si, ele apenas desfaz as ligações que faz com que ele faça parte da lista.

Aqui está um algoritmo feito em python com a ideia de listas duplamente encadeadas, com inserção no início e no final, exclusão no início, no final e numa posição específica.

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: Estruturas de dados e algoritmos em python

Um resumo sobre: listas encadeadas com extremidades duplas.

Mateus Costa — Mon, 27 Feb 2023 14:34:48 +0000

Para um melhor entendimento deste resumo, leia sobre lista encadeada simples, pois lá faço uma boa introdução sobre as listas encadeadas.
Aqui irei abordar sobre as listas encadeadas com extremidades duplas.

Enquanto a lista simples com uma única extremidade possui uma referência para o primeiro nó, a lista com extremidades duplas, referencia o primeiro e o último nó. Dessa maneira, nós podemos ter acesso tanto ao primeiro elemento da lista, quanto ao último, sendo que o último podemos inserir também dados no final. Entretanto, nós não excluímos elemento diretamente do final, somente pesquisando elemento por elemento, até chegar no último, como nas listas encadeadas com extremidade única. Isso ocorre, porque só podemos percorrer a lista da esquerda para a direita, sendo assim, se excluirmos o último, não conseguimos ter acesso ao anterior para indicar que o anterior será o último. Repare na imagem que as setas vão em uma única direção (esquerda para direita):

Para inserir um item na última posição:
1- Criamos um novo nó;
2- O objeto que era o último não aponta mais para Null e passa a apontar para o novo objeto;
3- O novo objeto irá apontar para null;
4- Por fim, nós tiramos o link do cabeça da lista apontando para o que era o último e apontamos para o que agora é o último.

A imagem irá facilitar a visualização:

Para acessar as outras operações acesse este link sobre as filas encadeadas com extremidade única, pois é a mesma ideia.

Quanto ao Big-O dessas operações, ficam da seguinte maneira:

Na inserção e exclusão do início e do final, será O(1) - constante. (Excelente performance).
Pesquisar, inserir e excluir um item específico, requer buscar os itens, o que resulta em uma notação O(n) - linear. Entretanto, na exclusão, não é necessário o remanejamento dos itens, como nos vetores.
Por fim, essa estrutura utiliza somente a memória que necessitar, podendo ser expandida de acordo com o aumento da lista, como nas listas simples com extremidades únicas.

Aqui está um algoritmo feito em python com a ideia de listas encadeadas com extremidades duplas.

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: Estruturas de dados e algoritmos em python

Um resumo sobre: listas encadeadas simples.

Mateus Costa — Sat, 25 Feb 2023 03:19:53 +0000

Neste resumo irei abordar dois tópicos principais:

Diferença entre vetores e listas encadeadas;
Processo de pesquisa, exclusão e inserção de dados em listas encadeadas simples.

Diferença entre vetores e listas encadeadas:

Vetores:

Em um vetor não ordenado a busca é lenta;
Vetor ordenado a inserção é lenta;
Em ambos a remoção é lenta;
O tamanho do vetor não pode ser alterado depois de criado;
Mesmo vazios ocupam espaço na memória;

Lista encadeada:

Cada item de dado é incorporado em um nó, sendo que cada nó possui referência para o próximo nó da lista;
A lista possui cabeça e cauda que é apontada.

Em um vetor nós trabalhamos com posição, já em uma lista, nós trabalhamos com relacionamento. No vetor, nós trabalhamos com o item em uma certa posição e nós acessamos esses elementos por meio do índice que esses itens ocupam.
Com as listas nós trabalhamos com relacionamento e a posição do elemento é no endereço da memória. Dessa maneira, nós teremos acesso ao primeiro da lista e para chegarmos ao último, precisamos acessar todos até encontrá-lo. Os dados não podem ser acessados diretamente. Cada elemento da lista é armazenado em um objeto, sendo que esse elemento referencia o próximo e é alocado dinamicamente conforme a necessidade. Lembrando que o vetor é pré criado, o que ocupa mais lugar na memória. Imagina que estivéssemos em um ambiente que cabe mil pessoas e quando forem surgindo pessoas, nós inserimos ela dentro desse ambiente. Agora termos uma segunda situação, nós inserimos uma pessoa e ela fica em um ambiente suficiente para ela e conforme for entrando, o espaço é aumentado. O primeiro é o vetor e neste último caso é uma lista, que aumenta conforme a necessidade. Para referenciar o primeiro elemento, é utilizado o elemento cabeça da lista. Sabemos que a lista chegou ao final, quando o próximo elemento for nulo.
Nessas duas imagens você terá uma comparação entre vetores de listas:

Vetores:

Listas:

Depois dessa visão geral sobre a comparação entre as listas e os vetores, vamos falar um pouco sobre as listas simples.

Listas Simples:

Nessa estrutura, nós podemos realizar 5 operações: Inserir no início, excluir no início, mostrar lista, pesquisar e excluir da posição.

Inserir no início: Este é o local mais fácil de inserir um item. Quando inserimos o novo nó (elemento), o que era o primeiro passa a ser o segundo da lista e o novo dado terá um ponteiro indicando que ele é a cabeça da lista. Na próxima imagem nós iremos ver 3 operações básicas.
1- Criar o novo nó
2- Apontar o novo nó para o nó que antes era o primeiro
3- Apontar a cabeça da lista para o primeiro elemento.

Excluir no início: É inverso do inserir no início. Iremos sobrescrever o ponteiro que indicava a cabeça da lista que agora irá indicar que o primeiro nó é o que era o segundo. O segundo nó é encontrado por meio do ‘próximo’ do primeiro nó. Observe na imagem:

Mostrar lista e pesquisar: Para essas duas operações, irá funcionar de forma parecida. O programa irá iniciar no primeiro nó e irá percorrer de nó em nó, até chegar em um nó que irá apontar para o ‘próximo’ que será nulo. Se quisermos mostrar a lista toda, ele percorrerá todo nó, se quisermos encontrar um elemento, ele segue do início de nó em nó até encontrar e caso não exista o elemento ele irá percorrer toda a lista e não achará. Muito parecido com a pesquisa linear que vimos nos vetores.

Excluir na posição: Por fim, essa operação é realizada quando queremos excluir um nó específico da lista. Iremos basicamente realizar uma pesquisa até encontrar o elemento desejado e então faremos com que o nó anterior a ele aponte o ‘Próximo’ para o que está posterior ao nó excluído. Observe na imagem:

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: Estruturas de dados e algoritmos em python

Um resumo sobre: deque.

Mateus Costa — Thu, 23 Feb 2023 19:46:14 +0000

Deque é uma abreviação de Double Ended Queue (fila de duas pontas), ele pode ser utilizado para implementar estrutura do tipo fila(FIFO) e pilha(FILO). Caso não saibam o funcionamento dessas duas estruturas de dados, sugiro que leiam. Entretanto, vou abordar algumas características de ambas, a fim de comparar com o deque. Na fila de modo geral, nós adicionamos os elementos na cauda e tiramos na cabeça. A inserção dos dados é do tipo constante, o que agiliza o processo, entretanto, quando tratamos da exclusão dos dados, o Big-O passa a ser O(n) - linear, porque precisamos remanejar todos os dados para que a primeira posição não fique vazia. Enquanto isso, o deque adiciona e remove itens em qualquer direção com o desempenho aproximado O(1), segundo o python collections. Sendo assim, quando comparamos a inserção e remoção de elementos, o deque ganha em questão de performance. O deque pode se comportar como fila(até mesmo as filas de prioridade) ou pilha, com isso, nós podemos excluir e adicionar elementos tanto no início, quanto no final da estruturas.
Veja esta imagem que mostra a diferença entre as três:

A implementação de exclusão e inserção de dados nos deques podem ser realizadas de forma estática ou circular. A forma circular é muito parecida com a da fila que vimos nos resumos passados. Basicamente, a implementação deste tipo é formado por um ponteiro indicando o início e o final da fila, sendo que esta é a forma mais indicada para este tipo de estrutura de dados. Já a forma estática, não é tão indicada por ter sua notação linear O(n), devido ao reajuste das casas para inserção e exclusão de itens do início do vetor.

Aqui está um algoritmo em python com a ideia de deque.

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: Estruturas de dados e algoritmos em python

Um resumo sobre: filas.

Mateus Costa — Wed, 22 Feb 2023 21:20:31 +0000

Neste resumo irei abordar os seguintes tópicos:

Introdução:

Conceito geral de fila
Fila circular
Fila de prioridade

Conceito Geral:
Hoje irei abordar sobre a fila. Essa estrutura de dados é muito parecida com a fila que temos na vida real. Em uma fila, o primeiro a chegar é o primeiro a ser atendido e o último a chegar, será o último a sair. Com isso, temos o principal conceito de uma fila FIFO(first-in-first-out), ou seja, o primeiro elemento a ser inserido, será o primeiro elemento a ser removido.
Para inserir um item nessa estrutura, nós iremos enfileirar, o que significa que iremos adicionar o dado no final da fila. Para remover, iremos desenfileirar, assim, retiramos o elemento do início do vetor. Por fim, para visualizarmos um elemento, nós iremos ver o primeiro da fila.

Fila Circular:
Irei abordar um conceito muito importante nessa estrutura que é a fila circular. Como vimos em vetores ordenados e vetores não ordenados, se excluirmos um dado no início ou no meio do vetor, nós iremos remanejar todos os itens posteriores para que não haja nenhuma casa vazia, com essa imagem ficará fácil de visualizar:

Essa abordagem aumenta um número n de passos de acordo com o tamanho de dados do vetor. A fila circular faz com que esse remanejamento não aconteça, melhorando, dessa maneira, a performance da aplicação. Ela funciona da seguinte forma: existem dois ponteiros, um que representa o início da fila e outro que representa o final, quando entra um elemento novo, o ponteiro do final da fila muda de posição e quando sai um elemento, o ponteiro de início da fila também muda de posição. Imagina uma fila de banco, só que quando você entra na sua posição da fila você não pode mais se mover, somente se for para sair. Vamos supor que tem uma fila montada e que ninguém foi atendido e assim que você chega a pessoa que era última te entrega a placa que identifica que agora você é o último. A primeira pessoa quando for atendida ninguém sai do lugar, mas ela passa a plaquinha para o segundo da fila para informar que o segundo agora é o primeiro. Quando chegar uma próxima pessoa, ela vai para o lugar vazio, que é onde estava o primeiro, assim, você entrega a placa de último lugar para ela.
Observe na imagem para facilitar a visualização:

O número 6 é o primeiro da fila e o 5 é o último. Após isso chega o número 7 que recebe a plaquinha do último da fila, o número 6 sai da fila e quando chegar o número 1, este ocupa a casa que o 6 deixou, mas recebe a placa de último da fila e os dados irão circulando entre as posições.
Quando utilizamos as filas normais, o Big-O será linear O(n), mas quando utilizamos as filas circulares o Big-O será constante. Isso faz com que as filas circulares tenham um excelente desempenho, quando comparamos com as demais estruturas.
Irei contextualizar com Javascript e Python:
Com JS, inserimos os dados em um array com o push( ), pois ele sempre será inserido no final da fila. Para excluirmos um dado, utilizamos o método de array shift( ). E para a pesquisa é só pegar o primeiro item, array[0]. Lembrando que essa ideia de fila que estou passando é uma fila comum e não circular.

Para realizarmos algoritmos com filas circulares, podemos fazer por meio de classes ou funções. Segue um exemplo de um algoritmo circular feito em python:

Fila de prioridade
Neste tipo de estrutura, os itens são ordenados por valor-chave, em que os elementos com o valor alto ou baixo (depende de como será definido), terão prioridade na fila. Vamos supor que quanto menor o número da chave, mais será a prioridade. Dessa maneira, se temos um array com valores [1,5,10,15,24,30] e entrar o item com chave número 3, ele ficará na segunda posição [1, 3, 5, 10, 15, 24, 30]. Pensa nos grupos prioritários em uma fila de mercado, banco e etc.
Veja este outro exemplo para ficar mais claro:

Deixarei um algoritmo feito em python que representa uma fila de prioridade:

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!
Este resumo é baseados no curso: Estruturas de dados e algoritmos em python

Veja sobre pilhas!

Um resumo sobre: pilha

Mateus Costa — Wed, 22 Feb 2023 03:36:57 +0000

Pilha é uma estrutura de dados que representa um elemento sobre o outro. Imagine uma pilha de papéis ou uma pilha de moedas, repare que quando pensamos em uma pilha de alguma coisa, pensamos em um elemento sobre o outro. Caso deseje retirar um elemento do meio desta pilha você terá uma certa dificuldade, assim, precisará tirar todos os elementos de cima, de um a um, até que o objeto que você deseja retirar seja o último da pilha. Aí está a primeira característica desta estrutura de dados, o primeiro elemento a entrar, será o último a sair (LIFO - Last-in-First-out). Perceba bem que nesse tipo de estrutura nós teremos acesso ao último elemento da pilha (ou elemento do topo).
Para inserir um dado nesse tipo de estrutura nós iremos empilhar, ou seja, colocar um elemento no topo da pilha. Para excluir, nós iremos excluir o dado que estará no topo da pilha. Podemos também pesquisar somente o topo da pilha. Só é possível pesquisar, inserir e excluir o item do topo da pilha, isso não pode ocorrer no meio dela.

Para contextualizar com javascript, imagine um array que iremos inserir dados, assim, o método push(elemento a ser inserido) passa a ideia de inserção em uma pilha, ele sempre irá inserir no topo/final do vetor. Já o método pop( ), funcionará como a exclusão de elementos de uma pilha, pois ele irá tirar o último elemento do array. Por fim, se quisermos pesquisar o último elemento, nós temos algumas formas, dentre elas temos o at(-1).

Fiz um exemplo em que eu insiro em JS que insiro vários elementos e depois retiro o último e por fim eu imprimo o elemento do topo.

Por fim, segue um exemplo de um algoritmo que fiz em python que utiliza também a ideia de pilha:

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Big-O
Vetores não ordenados
Um resumo sobre: vetores ordenados e pesquisa linear e binária.

Um resumo sobre: vetores ordenados e pesquisa linear e binária.

Mateus Costa — Tue, 21 Feb 2023 00:40:12 +0000

Introdução
Nesse resumo irei abordar os seguintes temas:

Vetores ordenados: pesquisa, inserção e exclusão de dados;
Pesquisa linear e binária
Diferença de performance entre vetores ordenados e não ordenados

Vetores Ordenados: pesquisa, inclusão e exclusão de dados
Os vetores ordenados, estão dispostos em ordem crescente, em que a menor chave está na posição 0 e a próxima posição terá a chave maior que a posição anterior. Ele pode agilizar bastante o tempo de pesquisa(tanto a linear, quanto a binária) quando comparamos com vetores não ordenados. Para a inserção de dados em vetores não ordenados (pense sempre nos vetores como array no javascript e dados ou chaves como os valores inseridos nele, sendo que esses valores podem ser números, strings e etc), é preciso somente inserir. Agora, quando tratamos de vetores ordenados, nós precisamos percorrer o vetor até encontrar um próximo número que seja maior que ele e, assim, mover os números posteriores para casa da frente para que o número ocupe sua devida posição.
Observe na imagem quando inserimos o número 3:

Lembrando que o Big-O será O(n). Embora a pesquisa seja linear (não estou falando da binária, que só é possível em vetores ordenados) em vetores ordenados e não ordenados, o número de passos será menor nos vetores ordenados, uma vez que, na maioria das vezes, o programa não precisará percorrer o vetor inteiro, pois achando o número ele para a execução.
Para uma melhor visualização, você pode entrar nesse link e no canto superior esquerdo você insere um número para ser procurado e clique em pesquisar e ele vai mostrar os passos que o programa faz para achar o número digitado. Caso não tenha o número na lista, o retorno será -1 e se achar o programa retornará o index do array.
Já para excluir um número desse vetor ordenado, não possui grandes diferenças entre os vetores não ordenados. A maior diferença é que o número de passos pode ser um pouco menor, uma vez que assim que ele encontrar o número, ele apaga e não precisa continuar percorrendo o vetor.
Veja o processo de exclusão na imagem, retirei o número 4:

Pesquisa binária:

Até o momento vimos sobre a pesquisa linear, em que ele executa passo a passo para encontrar um número. Por exemplo, se tivermos um array ordenado de números 1 a 101 e precisarmos encontrar o número 60, o programa percorrerá a posição 0, 1, 2, 3, 4 e assim sucessivamente até encontrar a chave 60.
Já a pesquisa binária resolveria assim:temos a posição do array de 0 até 100, então divido por dois que será a posição 50, assim, ele verifica o número da posição 50 se é maior, menor ou igual ao número 60, como neste caso é menor que 60, ele ficará entre a posição 51 a 101. Nisso, ele encontra a posição do meio entre essas duas, que é 76, ele verifica se o número dessa posição é maior do que 60, dessa maneira, ele sabe que está entre a posição 51 e a posição 76. Com isso, ele encontra o meio entre essas posições que dará aproximadamente 64 e faz a verificação e vê que é maior do que o que estamos procurando, agora ele observa entre a posição 51 e 64, que dá 57, como o número 60 está na posição 59 do array, ficará entre 57 e 64, a posição será a 60 aproximadamente, nisso ele verifica que é menor e procura a posição entre 57 e 60, que dá na a 59(valor aproximado) e encontra. Embora complexo à primeira vista, essa busca economiza muito o passo a passo para pesquisar as posições em listas ordenadas. Enquanto a pesquisa linear dá 60 passos, a pesquisa binária faz apenas 6 passos, ou seja, 10 vezes menos, nesse exemplo.
Neste Link você pode comparar ambas. Basta colocar um número para fazer a pesquisa linear e depois a binária.
Olhe este exemplo com menos quantidade de números:
Para procurar o 9, o programa dividirá as posições por dois, verificar, dividir novamente e verificar. Esse ciclo ocorre até encontrar ou não encontrar.

Agora vai uma comparação entre a pesquisa linear e a binária:
Lembrando que a comparação linear está O(n/2) pois é uma média dos passos que será dado, será n e no mais otimizado(caso o número seja o primeiro da lista), será O(1).
Enquanto busca linear e O(n), a binária é O(log n), que se aproxima muito da constante que é a mais otimizada.

Com essa comparação nós podemos concluir que a pesquisa binária é absurdamente mais otimizada que a pesquisa linear. Aí está a grande importância de termos lista de dados ordenados.
Este é um exemplo de um código que fiz para a realização de uma busca binária em Javascript:

Passando a função binSearch(“array”, “começando na posição 0 à esquerda”, “vai até a última posição - o -1 é porque o array inicia em 0”, “por último é o número que queremos pesquisar”).

Resumo geral entre performance de vetores ordenados e não ordenados para inserção e pesquisa de dados:

Se precisarmos inserir um dado, vetores não ordenados são mais ágeis do que vetores ordenados, uma vez que nos vetores ordenados, os itens precisam ser movidos para abrir espaço. Vetor não ordenado: Big-O constante O(1) e Vetor ordenado: Big-O linear O(n);
Se precisarmos pesquisar um dado, vetores não ordenados são muito mais devagar do que vetores ordenados, pelo fato de poder fazer a busca binária e também na busca linear o algoritmo não precisa passar por todo array. Vetor não ordenado: Big-O linear O(n) e Vetor ordenado: Big-O log de n O(log n);
As remoções para os dois vetores são lentas, pois quando retiramos um dado, tem a necessidade de preencher o buraco, gerando o deslocamento dos dados posteriores, sendo os dois lineares O(n);

Conclusão:

Vetores ordenados são úteis para pesquisas mais frequentes, entretanto os não ordenados são mais úteis para a inserção de dados.Dessa maneira, é necessário entender as maiores necessidades da aplicação para implementar a melhor estrutura de dados.

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Big-O
Vetores não ordenados

Um resumo sobre: vetores não ordenados.

Mateus Costa — Sun, 19 Feb 2023 20:24:51 +0000

Linhas gerais sobre inserção, pesquisa e exclusão de dados em um vetor não ordenado.

Para trabalharmos em um determinado sistema, as operações básicas que utilizamos são: inserção, pesquisa e remoção. Vamos para exemplos práticos: vamos supor que estamos em um treino de futebol, quando entra um jogador é como se entrasse um novo dado nessa estrutura de dados ou vetor, quando sai um jogador, quer dizer que excluímos um dado.
Podemos ver o time como um array com 11 posições e os jogadores serão inseridos de forma aleatória (não ordenada) nesse array, vamos inserindo ocupando a posição 0, 1, 2, 3 e assim por diante. Se pensarmos no Big-O, para inserir um novo jogador nesse array é necessário um passo somente ArrayTime.push(Jogador). Assim, a notação big-o será constante O(1).
Agora vamos supor que precisássemos encontrar um elemento(jogador) nesse Array Time. Em javascript, usamos a função find para percorrer o array e encontrar o jogador. Em notação Big-O será O(n), ou seja, quanto maior o array e quantidade de dados, maior a complexidade, sendo assim, linear.
Se quisermos excluir um jogador, iremos percorrer o array em um número n de passos e tirá-lo da posição, após isso precisamos remanejar as posições para que a posição tirada não fique vazia. Para remanejar, precisamos dar mais uma quantidade n de passos, pois isso irá depender do número que tiramos e qual posição ele estava. Perceba na imagem:

Lembrando que como são vetores não ordenados, os números, logicamente, não estão ordenados nem em ordem crescente, nem decrescente, apenas de forma aleatória.
Na imagem, retiramos o número 1. Com isso, foram necessários 5 passos.

Passo 1 - verificar a posição zero.
Passo 2 - verificar a posição um.
Passo 3 - verificar a posição dois e tirar o número 1.
Passo 4- Remanejar o número 8 para a segunda posição.
Passo 5 - Remanejar o 5 para a terceira posição.

Em Big-O, a notação ficaria assim: O(2n), como N é infinito, ficaria infinito mais infinito que ficaria O(n), ou seja, linear.

Chaves únicas X Chaves duplicadas:

No exemplo anterior, não estávamos levando em consideração se as chaves eram duplicadas ou únicas, dei apenas uma visão bem simplificada. Entretanto, neste tópico irei abordar sobre a comparação entre chaves únicas e duplicadas na verificação, inserção e exclusão de dados. No exemplo dos jogadores, não é permitido jogadores com o mesmo número na camisa, assim, não é permitido valores duplicados. Se a chave fosse pelo nome do jogador, aí seria permitida chaves duplicadas, pois em um time, jogadores podem ter o mesmo nome. Se uma estrutura permitir chaves duplicadas, na pesquisa, o programa ao invés de procurar a primeira chave até encontrar e após isso pausar, ele precisará percorrer todo o array. Em JS se as chaves não forem duplicadas, podemos passar o método find no array, mas se as chaves forem duplicadas, passaremos o método filter. Retornando para o exemplo do time de futebol, se as chaves forem o número da camisa, nós utilizamos o find, se forem os nomes, utilizamos o filter, pois terá a possibilidade de haver mais de um jogador com o mesmo nome. Para inserção de um jogador, se as chaves forem o nome, é só inserir na última posição e pronto, pois não precisamos preocupar se está repetida ou não. Se forem os números, teremos que percorrer todo o array para verificar se há algum número igual ao que vai entrar para não haver chaves duplicadas, logo após a verificação, é só inserir. Por último, a exclusão, caso a chave for única, iremos percorrer o array até encontrar o elemento para excluir e depois reorganizar as posições, aplicar o método find no array e depois o splice. Se a chave for duplicada o processo será: Procura e exclui, rearranja, procura e exclui e rearranja novamente, faz esse processo até chegar ao fim do array, precisaremos utilizar o método filter.
Em todas as chaves, a notação big-o será linear, ou seja, quanto maior a entrada de dados, maior será o n, embora a quantidade de passos mudará consideravelmente para cada caso, como descrevi.

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Caso tenha dúvidas sobre os métodos find, splice e filter do Javascript.

Leia sobre o artigo de Big-O para entender melhor o tema: