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!
Top comments (0)