Suponha que precisamos descobrir se o endereço de e-mail “demensdeum@gmail.com” está incluído na lista de endereços de e-mail permitidos para recebimento de cartas .
Vamos percorrer toda a lista do primeiro ao último elemento, verificando se o elemento é igual ao endereço especificado – Vamos implementar um algoritmo de busca linear. Mas isso vai demorar muito ou não?
Para responder a esta pergunta, use a notação “Complexidade de tempo dos algoritmos”, “O”. O tempo de operação da busca linear no pior caso é igual ao enésimo número de elementos do array, vamos escrever isso na notação “O” – Sobre). A seguir, precisamos explicar que para qualquer algoritmo conhecido existem três indicadores de desempenho – tempos de execução do melhor caso, do pior caso e do caso médio. Por exemplo, o endereço de e-mail “demensdeum@gmail.com” está no primeiro índice do array, então ele será encontrado na primeira etapa do do algoritmo, segue-se que o tempo de execução é, na melhor das hipóteses, – O(1); e se estiver no final da lista, então este é o pior caso – Sobre(n)
Mas e os detalhes de implementação de software e desempenho de hardware, eles devem influenciar o grande O? Agora respire fundo e imagine que o cálculo da complexidade do tempo é calculado para alguma máquina abstrata ideal, na qual existe apenas esse algoritmo e nada mais.
Algoritmo
Ok, acontece que a pesquisa linear é bastante lenta, vamos tentar usar a pesquisa binária. Para começar, deve-se esclarecer que não trabalharemos com dados binários; este nome foi dado a este método devido às peculiaridades de seu trabalho. Inicialmente classificamos o array em ordem lexicográfica, então o algoritmo pega o intervalo de todo o array, obtém o elemento do meio do intervalo, compara-o lexicograficamente, e dependendo do resultado da comparação, decide qual intervalo usar para pesquisas adicionais – a metade superior da corrente ou a parte inferior. Ou seja, a cada etapa da pesquisa é tomada uma decisão a partir de dois – lógica binária. Esta etapa é repetida até que a palavra seja encontrada ou não seja encontrada (ocorre a intersecção dos índices inferior e superior do intervalo).
Desempenho deste algoritmo – o melhor caso é quando um elemento é imediatamente encontrado no meio do array O(1), o pior caso de enumeração é O(log n)
Armadilhas
Ao implementar a pesquisa binária, não apenas encontrei o interessante problema da falta de padronização da comparação lexicográfica em bibliotecas de linguagens de programação, mas também descobri a ausência de um padrão unificado para implementação localeCompare em JavaScript. O padrão ECMAScript permite diferentes implementações desta função, e é por isso que ao classificar usando localeCompare, resultados completamente diferentes podem ser observados em diferentes motores JavaScript.
Portanto, para que o algoritmo funcione corretamente, é necessário classificar e usar apenas o mesmo algoritmo de comparação lexicográfica, caso contrário nada funcionará. Co-mas se, por exemplo, você tentar classificar um array no Scala e pesquisar usando nodejs, sem implementar sua própria classificação/classificação de uma implementação, nada o aguardará, exceto decepção com a humanidade.
Fontes
O que é comparação lexicográfica e o que ela representa?
Почему для вычисления сложности алгоритмов используется log N вместо lb N?
Двоичный поиск
Знай сложности алгоритмов
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript
Código fonte
https://gitlab.com/demensdeum/algorithms
