Tenho notado algum uso muito estranho de O (1) na discussão de algoritmos que envolvem hash e tipos de pesquisa, geralmente no contexto de usar um tipo de dicionário fornecido pelo sistema de idiomas ou usar tipos de dicionário ou matriz de hash usados usando matriz notação de índice.

Basicamente, O (1) significa limitado por um tempo constante e (normalmente) espaço fixo. Algumas operações bastante fundamentais são O (1), embora o uso de linguagens intermediárias e VMs especiais tende a distorcer os que pensam aqui (por exemplo, como amortizar o coletor de lixo e outros processos dinâmicos sobre o que de outra forma seriam atividades O (1)).

Mas ignorando a amortização de latências, coleta de lixo e assim por diante, ainda não entendo como o salto para supor que certas técnicas que envolvem algum tipo de pesquisa podem ser O (1), exceto em condições muito especiais.

Embora eu tenha notado isso antes, um exemplo apareceu noPergunta Pandincus, "Coleção 'adequada' a ser usada para obter itens no tempo O (1) no C # .NET?".

Como observei lá, a única coleção que conheço que fornece acesso O (1) como um limite garantido é uma matriz de limite fixo com um valor de índice inteiro. A suposição é que a matriz seja implementada por algum mapeamento para a memória de acesso aleatório que usa operações O (1) para localizar a célula que possui esse índice.

Para coleções que envolvem algum tipo de pesquisa para determinar o local de uma célula correspondente para um tipo diferente de índice (ou para uma matriz esparsa com índice inteiro), a vida não é tão fácil. Em particular, se houver colisões e o congestionamento for possível, o acesso não será exatamente O (1). E se a coleção é flexível, é preciso reconhecer e amortizar o custo de expansão da estrutura subjacente (como uma árvore ou uma tabela de hash) paraqual alívio de congestionamento (por exemplo, alta incidência de colisão ou desequilíbrio das árvores).

Eu nunca teria pensado em falar dessas estruturas flexíveis e dinâmicas como O (1). No entanto, eu os vejo oferecidos como soluções O (1) sem qualquer identificação das condições que devem ser mantidas para que o acesso ao O (1) seja realmente garantido (assim como essa constante é insignificante pequena).

A PERGUNTA: Toda essa preparação é realmente para uma pergunta. Qual é a casualidade em torno de O (1) e por que é aceita tão cegamente? É reconhecido que mesmo O (1) pode ser indesejávelmente grande, embora quase constante? Ou O (1) é simplesmente a apropriação de uma noção de complexidade computacional ao uso informal? Estou confuso.

ATUALIZAÇÃO: As respostas e os comentários apontam onde eu fui casual sobre a definição de O (1), e eu consertei isso. Ainda estou procurando boas respostas, e alguns dos tópicos de comentários são bastante mais interessantes do que suas respostas, em alguns casos.