Em direção à busca linear auto-organizável

Consideramos técnicas para adaptar listas lineares de modo que os elementos mais frequentemente acessados sejam encontrados perto do início, mesmo que não nos sejam fornecidas as probabilidades de diversos elementos serem acessados. Os principais resultados são discutidos em duas seções. Talvez a mais interessante trate de técnicas que movem um elemento para o início apenas depois que ele foi solicitado k vezes seguidas. A outra seção, tecnicamente mais difícil, lida com a análise da heurística que move um elemento para o início da lista cada vez que é acessado. O comportamento desse esquema sob várias distribuições de probabilidade interessantes é discutido. Duas abordagens básicas para a técnica de mover um elemento para frente após ser acessado k vezes seguidas são debatidas. A primeira realiza a transformação após quaisquer k solicitações idênticas. A segunda, essencialmente, agrupa solicitações em lotes de pelo menos k e realiza a ação somente se as últimas k solicitações de um lote forem iguais. Adotando como transformação o movimento do elemento solicitado para o início da lista, a segunda abordagem é mostrada como levando a um tempo de busca médio mais rápido sob todas as distribuições de probabilidade não triviais para k ≥ 2. Também é mostrado que a abordagem "periódica", com k = 2, nunca leva a um tempo médio de busca maior que 1.21.. vezes aquele da ordenação ideal. Para a abordagem mais direta, uma razão de 1.36.. é mostrada sob as mesmas restrições. Ao estudar a heurística simples de mover para o início (ou seja, k = 1), é mostrado que para uma distribuição particular esse esquema pode levar a um número médio de sondagens π/2 vezes o da ordem ideal. Dentro de uma classe interessante de distribuições, isso é mostrado como o pior comportamento médio.