He estado notando un uso muy extraño de O (1) en la discusión de algoritmos que involucran hashing y tipos de búsqueda, a menudo en el contexto de usar un tipo de diccionario proporcionado por el sistema de lenguaje, o usar un diccionario o tipos de hash-array usados usando array -Notación de índice.

Básicamente, O (1) significa limitado por un tiempo constante y (típicamente) espacio fijo. Algunas operaciones bastante fundamentales son O (1), aunque el uso de lenguajes intermedios y máquinas virtuales especiales tiende a distorsionar a los que piensan aquí (por ejemplo, ¿cómo se amortiza el recolector de basura y otros procesos dinámicos sobre lo que de otro modo serían actividades O (1)).

Pero ignorando la amortización de las latencias, la recolección de basura, etc., todavía no entiendo cómo dar el salto a suponer que ciertas técnicas que implican algún tipo de búsqueda pueden ser O (1) excepto en condiciones muy especiales.

Aunque he notado esto antes, un ejemplo acaba de aparecer en elPregunta de Pandincus, "¿Colección 'adecuada' para usar para obtener elementos en O (1) tiempo en C # .NET?".

Como señalé allí, la única colección que conozco que proporciona acceso O (1) como límite garantizado es una matriz de límite fijo con un valor de índice entero. La presunción es que la matriz se implementa mediante alguna asignación a la memoria de acceso aleatorio que utiliza operaciones O (1) para ubicar la celda que tiene ese índice.

Para las colecciones que implican algún tipo de búsqueda para determinar la ubicación de una celda coincidente para un tipo diferente de índice (o para una matriz dispersa con índice entero), la vida no es tan fácil. En particular, si hay colisiones y es posible la congestión, el acceso no es exactamente O (1). Y si la colección es flexible, uno debe reconocer y amortizar el costo de expandir la estructura subyacente (como un árbol o una tabla hash) paracual alivio de la congestión (p. ej., alta incidencia de colisión o desequilibrio de los árboles).

Nunca hubiera pensado hablar de estas estructuras flexibles y dinámicas como O (1). Sin embargo, veo que se ofrecen como soluciones O (1) sin ninguna identificación de las condiciones que se deben mantener para que el acceso O (1) esté asegurado (y que esa constante sea insignificantemente pequeña).

LA PREGUNTA: Toda esta preparación es realmente para una pregunta. ¿Cuál es la casualidad en torno a O (1) y por qué se acepta tan ciegamente? ¿Se reconoce que incluso O (1) puede ser indeseablemente grande, aunque sea casi constante? ¿O es O (1) simplemente la apropiación de una noción de complejidad computacional para uso informal? Estoy confundido.

ACTUALIZACIÓN: Las Respuestas y los comentarios señalan dónde fui informal al definir O (1) yo mismo, y lo he reparado. Todavía estoy buscando buenas respuestas, y algunos de los hilos de comentarios son bastante más interesantes que sus respuestas, en algunos casos.