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