search - optimized - seo image alt tag example

¿Qué pasa con O(1)? (13)

O (1) significa tiempo constante y (típicamente) espacio fijo

Para aclarar estas, hay dos declaraciones separadas. Puedes tener O (1) en el tiempo pero O (n) en el espacio o lo que sea.

¿Se reconoce que incluso O (1) puede ser indeseablemente grande, aunque sea casi constante?

O (1) puede ser impráctico ENORME y sigue siendo O (1). A menudo se descuida que si usted sabe que tendrá un conjunto de datos muy pequeño, la constante es más importante que la complejidad, y para conjuntos de datos razonablemente pequeños, es un equilibrio de los dos. Un algoritmo O (n!) Puede superar un O (1) si las constantes y tamaños de los conjuntos de datos son de la escala apropiada.

La notación O () es una medida de la complejidad, no del tiempo que tomará un algoritmo, o una medida pura de cuán "bueno" es un algoritmo dado para un propósito dado.

He estado notando un uso muy extraño de O (1) en la discusión de algoritmos que involucran hash y tipos de búsqueda, a menudo en el contexto de usar un tipo de diccionario proporcionado por el sistema de lenguaje, o usando tipos de diccionario o 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 las ideas aquí (por ejemplo, cómo se amortiza el recolector de basura y otros procesos dinámicos sobre actividades O (1)).

Pero ignorando la amortización de las latencias, la recolección de basura, etc., todavía no entiendo cómo el salto a la suposición de 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 la pregunta de Pandincus, "Colección ''adecuada'' para usar para obtener elementos en el tiempo O (1) en C # .NET?" .

Como señalé allí, la única colección que conozco proporciona acceso O (1) ya que un límite garantizado es una matriz de límite fijo con un valor de índice entero. La presunción es que la matriz es implementada por alguna asignación a memoria de acceso aleatorio que usa operaciones O (1) para localizar 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) para el alivio de la congestión (por ejemplo, alta incidencia de colisión o desequilibrio de árbol).

Nunca hubiera pensado hablar de estas estructuras flexibles y dinámicas como O (1). Sin embargo, los veo presentados como soluciones O (1) sin ninguna identificación de las condiciones que deben mantenerse para que realmente se garantice el acceso O (1) (y que esa constante sea insignificante).

LA PREGUNTA: Toda esta preparación es realmente para una pregunta. ¿Cuál es la informalidad 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 el uso informal? Estoy confundido.

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

Creo que cuando muchas personas utilizan el término "O (1)" implícitamente tienen en mente una constante "pequeña", lo que sea que "pequeño" signifique en su contexto.

Tienes que tomar todo este análisis de la gran O con contexto y sentido común. Puede ser una herramienta extremadamente útil o puede ser ridículo, dependiendo de cómo lo use.

El problema es que la gente es muy descuidada con la terminología. Hay 3 clases importantes pero distintas aquí:

O (1) peor caso

Esto es simple: todas las operaciones no requieren más que una cantidad de tiempo constante en el peor de los casos, y por lo tanto en todos los casos. El acceso a un elemento de una matriz es O(1) peor de los casos.

O (1) peor caso amortizado

Amortizado significa que no todas las operaciones son O(1) en el peor de los casos, pero para cualquier secuencia de N operaciones, el costo total de la secuencia no es O(N) en el peor de los casos. Esto significa que, aunque no podemos consolidar el coste de una sola operación por una constante, siempre habrá suficientes operaciones "rápidas" para compensar las operaciones "lentas" de modo que el tiempo de ejecución de la secuencia de operaciones sea lineal en el numero de operaciones

Por ejemplo, la matriz dinámica estándar que dobla su capacidad cuando se llena requiere O(1) tiempo amortizado para insertar un elemento al final, aunque algunas inserciones requieren O(N) tiempo - siempre hay suficientes inserciones O(1) que insertando N elementos siempre toma O(N) tiempo total.

O (1) promedio de casos

Este es el más complicado. Hay dos definiciones posibles de caso promedio: una para algoritmos aleatorizados con entradas fijas, y otra para algoritmos determinísticos con entradas aleatorias.

Para los algoritmos aleatorizados con entradas fijas, podemos calcular el tiempo medio de ejecución de una entrada dada analizando el algoritmo y determinando la distribución de probabilidad de todos los tiempos de ejecución posibles y tomando el promedio sobre esa distribución (dependiendo del algoritmo, esto puede o puede no ser posible debido al problema de detención).

En el otro caso, necesitamos una distribución de probabilidad sobre las entradas. Por ejemplo, si tuviéramos que medir un algoritmo de clasificación, una de esas distribuciones de probabilidad sería la distribución que tiene todas las N! posibles permutaciones de la entrada igualmente probables. Luego, el tiempo medio de ejecución del caso es el tiempo de ejecución promedio sobre todas las entradas posibles, ponderado por la probabilidad de cada entrada.

Como el tema de esta pregunta son las tablas hash, que son deterministas, me centraré en la segunda definición de caso medio. Ahora, no siempre podemos determinar la distribución de probabilidad de las entradas porque, bueno, podríamos hacer hash casi cualquier cosa, y esos elementos podrían provenir de un usuario que los ingresa o desde un sistema de archivos. Por lo tanto, cuando se habla de tablas hash, la mayoría de la gente simplemente asume que las entradas son correctas y que la función hash se comporta bien, de modo que el valor hash de cualquier entrada se distribuye de forma aleatoria de manera uniforme en el rango de posibles valores hash.

Tómese un momento y deje que el último punto se hunda: el rendimiento promedio de O(1) para las tablas hash proviene de asumir que todos los valores hash estén distribuidos uniformemente. Si se viola esta suposición (que generalmente no es, pero ciertamente puede ocurrir y pasa), el tiempo de ejecución ya no es O(1) en promedio.

Ver también Denegación de servicio por Complejidad Algorítmica . En este documento, los autores discuten cómo explotaron algunas debilidades en las funciones predeterminadas de hash usadas por dos versiones de Perl para generar grandes cantidades de cadenas con colisiones hash. Armados con esta lista de cadenas, generaron un ataque de denegación de servicio en algunos servidores web al alimentarlos con cadenas que resultaron en el peor comportamiento O(N) en las tablas hash usadas por los servidores web.

En general, creo que la gente los usa comparativamente sin tener en cuenta la exactitud. Por ejemplo, las estructuras de datos basadas en hash son O (1) (promedio) de búsqueda si están bien diseñadas y usted tiene un buen hash. Si todo se reduce a un solo cubo, entonces es O (n). En general, aunque uno usa un buen algoritmo y las claves están razonablemente distribuidas, es conveniente hablar de ello como O (1) sin todas las calificaciones. Del mismo modo, con listas, árboles, etc. Tenemos en mente ciertas implementaciones y es simplemente más conveniente hablar de ellas, cuando se discuten generalidades, sin las calificaciones. Si, por otro lado, estamos discutiendo implementaciones específicas, entonces probablemente sea más preciso.

En la práctica, las implementaciones de tablas hash no son "exactamente" O (1) en uso. Si prueba una, encontrará una media de alrededor de 1.5 búsquedas para encontrar una clave determinada en un gran conjunto de datos.

(debido al hecho de que se producen colisiones, y al colisionar, se debe asignar una ubicación diferente)

Además, en la práctica, los HashMaps están respaldados por matrices con un tamaño inicial, que es "crecido" al doble de tamaño cuando alcanza un 70% de plenitud en promedio, lo que proporciona un espacio de direccionamiento relativamente bueno. Después de un 70%, las tasas de colisión de plenitud crecen más rápido.

La teoría de Big O establece que si tiene un algoritmo O (1) o incluso un algoritmo O (2), el factor crítico es el grado de la relación entre el tamaño del conjunto de entrada y los pasos para insertar / buscar uno de ellos. O (2) todavía es tiempo constante, por lo que solo lo aproximamos como O (1), porque significa más o menos lo mismo.

En realidad, solo hay 1 forma de tener una "tabla hash perfecta" con O (1), y eso requiere:

Un generador de claves Global Perfect Hash
Un espacio de direccionamiento ilimitado.

( Caso de excepción : si puede calcular por adelantado todas las permutaciones de claves permitidas para el sistema, y el espacio de direcciones de la tienda de respaldo de destino se define como el tamaño donde puede contener todas las claves que están permitidas, entonces puede tener un hash perfecto , pero es una perfección "dominio limitado")

Dada una asignación de memoria fija, no es plausible en absoluto tener esto, ya que supondría que tiene alguna forma mágica de empaquetar una cantidad infinita de datos en una cantidad fija de espacio sin pérdida de datos, y eso es logísticamente imposible .

Entonces, de forma retrospectiva, obteniendo O (1.5) que todavía es tiempo constante, en una cantidad finita de memoria incluso con un generador de claves hash relativamente Naïve, considero bastante malditamente increíble.

Nota de sufijos Nota: uso O (1.5) y O (2) aquí. En realidad, estos no existen en big-o. Esto es simplemente lo que las personas que no saben que Big-o asumen es la razón fundamental.

Si algo lleva 1,5 pasos para encontrar una clave, o 2 pasos para encontrar esa clave, o 1 paso para encontrar esa clave, pero el número de pasos nunca excede 2 y si se necesita 1 paso o 2 es completamente aleatorio, entonces sigue siendo Big-O de O (1). Esto se debe a que no importa cuántos elementos agregue al tamaño del conjunto de datos, aún mantiene los <2 pasos. Si para todas las tablas> 500 teclas se necesitan 2 pasos, entonces puede suponer que esos 2 pasos son de hecho un paso con 2 partes, ... que todavía es O (1).

Si no puede hacer esta suposición, entonces no está pensando en Big-O, porque entonces debe usar el número que representa el número de pasos computacionales finitos requeridos para hacer todo y "un paso" no tiene sentido para usted. Simplemente piense que NO existe una correlación directa entre Big-O y el número de ciclos de ejecución involucrados.

Las búsquedas HashTable son O (1) con respecto al número de elementos en la tabla, porque no importa cuántos elementos agregues a la lista, el costo de hash de un solo elemento es prácticamente el mismo, y la creación del hash te dirá usted la dirección del artículo.

Para responder por qué esto es relevante: el OP preguntó por qué O (1) parecía ser arrojado de manera tan casual cuando, en su opinión, obviamente no podía aplicarse en muchas circunstancias. Esta respuesta explica que O (1) el tiempo realmente es posible en esas circunstancias.

No puedo hablar sobre las otras discusiones que ha visto, pero hay al menos un algoritmo hash que se garantiza que es O (1).

El hash de cuco mantiene un invariante para que no haya encadenamiento en la tabla hash. La inserción se amortiza O (1), la recuperación siempre es O (1). Nunca he visto una implementación de él, es algo que se descubrió recientemente cuando estaba en la universidad. Para conjuntos de datos relativamente estáticos, debería ser una muy buena O (1), ya que calcula dos funciones hash, realiza dos búsquedas e inmediatamente conoce la respuesta.

Eso sí, esto es asumiendo que la calcinación de hash también es O (1). Se podría argumentar que para las cadenas K de longitud, cualquier hash es mínimamente O (K). En realidad, puede enlazar K bastante fácilmente, digamos K <1000. O (K) ~ = O (1) para K <1000.

O (1) significa, exactamente, que la complejidad de tiempo del algoritmo está limitada por un valor fijo. Esto no significa que sea constante, solo que está limitado independientemente de los valores de entrada. Estrictamente hablando, muchos algoritmos supuestamente O (1) de tiempo no son en realidad O (1) y simplemente van tan lentamente que están limitados para todos los valores de entrada prácticos.

Puede haber un error conceptual en cuanto a la forma en que entiendes la notación Big-Oh. Lo que significa es que, dado un algoritmo y un conjunto de datos de entrada, el límite superior para el tiempo de ejecución del algoritmo depende del valor de la función O cuando el tamaño del conjunto de datos tiende a infinito.

Cuando uno dice que un algoritmo toma O (n) tiempo, significa que el tiempo de ejecución para el peor caso de un algoritmo depende linealmente del tamaño del conjunto de entrada.

Cuando un algoritmo toma O (1) tiempo, lo único que significa es que, dada una función T (f) que calcula el tiempo de ejecución de una función f (n), existe un número positivo natural k tal que T (f) <k para cualquier entrada n. Esencialmente, significa que el límite superior para el tiempo de ejecución de un algoritmo no depende de su tamaño, y tiene un límite fijo y finito.

Ahora, eso no significa en modo alguno que el límite sea pequeño, solo que es independiente del tamaño del conjunto de entrada. Entonces, si defino artificialmente un límite k para el tamaño de un conjunto de datos, entonces su complejidad será O (k) == O (1).

Por ejemplo, buscar una instancia de un valor en una lista vinculada es una operación O (n). Pero si digo que una lista tiene como máximo 8 elementos, entonces O (n) se convierte en O (8) y se convierte en O (1).

En este caso, usamos una estructura de datos trie como un diccionario (un árbol de caracteres, donde el nodo hoja contiene el valor de la cadena utilizada como clave), si la clave está limitada, entonces su tiempo de búsqueda puede considerarse O ( 1) (Si defino que un campo de caracteres tiene a lo sumo k caracteres de longitud, lo que puede ser una suposición razonable para muchos casos).

Para una tabla hash, siempre que suponga que la función hashing es buena (distribuida aleatoriamente) y suficientemente dispersa como para minimizar las colisiones, y que se repite cuando la estructura de datos es suficientemente densa, puede considerarla como una O (1 ) estructura de tiempo de acceso.

En conclusión, el tiempo O (1) puede estar sobrevalorado por muchas cosas. Para estructuras de datos grandes, la complejidad de una función hash adecuada puede no ser trivial, y existen casos de esquina suficientes donde la cantidad de colisiones lo llevan a comportarse como una estructura de datos O (n), y el reajuste puede ser prohibitivamente costoso. En tal caso, una estructura O (log (n)) como una AVL o un B-tree puede ser una alternativa superior.

Puedo ver lo que dices, pero creo que hay un par de suposiciones básicas que subyacen a la afirmación de que las búsquedas en una tabla Hash tienen una complejidad de O (1).

La función hash está razonablemente diseñada para evitar una gran cantidad de colisiones.
El conjunto de claves está prácticamente distribuido al azar, o al menos no diseñado a propósito para hacer que la función hash funcione mal.

La peor complejidad de caso de una tabla Hash es O (n), pero eso es extremadamente improbable dado los 2 supuestos anteriores.

Sí, la recolección de basura afecta la complejidad asintótica de los algoritmos que se ejecutan en la arena de recolección de basura. No es sin costo, pero es muy difícil de analizar sin métodos empíricos, porque los costos de interacción no son compositivos.

El tiempo dedicado a la recolección de basura depende del algoritmo que se usa. Por lo general, los recolectores de basura modernos cambian de modo a medida que la memoria se llena para mantener estos costos bajo control. Por ejemplo, un enfoque común es usar un colector de copias Cheney cuando la presión de la memoria es baja porque paga un costo proporcional al tamaño del Live Set a cambio de usar más espacio, y cambiar a una marca y barrer el colector cuando la presión de la memoria se vuelve más grande, porque a pesar de que paga un costo proporcional al conjunto en vivo para marcar y a todo el montón o conjunto muerto para barrido. En el momento en que agregue marcado de tarjetas y otras optimizaciones, etc., los peores costos de casos para un práctico recolector de basura en realidad pueden ser un poco peores, tomando un factor logarítmico adicional para algunos patrones de uso.

Entonces, si asigna una gran tabla hash, incluso si accede a ella usando O (1) busca todo el tiempo durante su vida útil, si lo hace en un entorno recolectado basura, ocasionalmente el recolector de basura atravesará toda la matriz, porque tiene el tamaño O (n) y pagará ese costo periódicamente durante la recolección.

La razón por la que generalmente lo dejamos fuera del análisis de complejidad de los algoritmos es que la recolección de basura interactúa con su algoritmo de maneras no triviales. Cuán malo es el costo depende en gran medida de lo que esté haciendo en el mismo proceso, por lo que el análisis no es compositivo.

Además, más allá de la copia frente a la compacta frente a la marca y el barrido, los detalles de implementación pueden afectar drásticamente las complejidades resultantes:

Los recolectores de basura incrementales que rastrean bits sucios, etc. pueden hacer desaparecer esos re-viajes más grandes.
Depende de si su GC funciona periódicamente en función del tiempo del reloj de pared o se ejecuta proporcionalmente al número de asignaciones.
Si un algoritmo de marca y estilo de barrido es concurrente o stop-the-world
Si marca nuevas asignaciones en negro si las deja en blanco hasta que las deja caer en un contenedor negro.
Si su lenguaje admite modificaciones de indicadores, puede dejar que algunos recolectores de basura trabajen de una sola vez.

Finalmente, cuando hablamos de un algoritmo, estamos discutiendo sobre un hombre de paja. Los asintóticos nunca incorporarán completamente todas las variables de su entorno. Rara vez alguna vez implementa cada detalle de una estructura de datos como está diseñado. Usted toma prestada una característica aquí y allá, suelta una tabla hash porque necesita acceso rápido de clave no ordenada, usa una unión-encuentra sobre conjuntos disjuntos con compresión de ruta y unión por rango para fusionar regiones de memoria allí porque no puede permitirse pagar un costo proporcional al tamaño de las regiones cuando las fusiona o lo que tiene. Estas estructuras son primitivas y las asintóticas lo ayudan a planificar las características generales de desempeño para la estructura "en general", pero el conocimiento de las constantes también es importante.

Puede implementar esa tabla hash con características asintóticas perfectamente O (1), simplemente no use la recolección de basura; asignarlo a la memoria desde un archivo y administrarlo usted mismo. Sin embargo, probablemente no te gusten las constantes involucradas.

Hashtables es una estructura de datos que admite O (1) búsqueda e inserción.

Una tabla hash usualmente tiene una clave y un par de valores, donde la clave se usa como parámetro para una función (una función hash ) que determinará la ubicación del valor en su estructura de datos interna , generalmente una matriz.

Como la inserción y la búsqueda solo dependen del resultado de la función hash y no del tamaño de la tabla hash ni del número de elementos almacenados, una tabla hash tiene O (1) inserción y búsqueda.

Sin embargo, hay una advertencia . Es decir, a medida que la tabla hash se llena cada vez más, habrá colisiones hash donde la función hash devolverá un elemento de una matriz que ya está ocupada. Esto requerirá una resolución de colisión para encontrar otro elemento vacío.

Cuando se produce una colisión hash, no se puede realizar una búsqueda o inserción en O (1) tiempo. Sin embargo, los buenos algoritmos de resolución de colisiones pueden reducir el número de intentos para encontrar otro lugar vacío apto para el uso de una suite, o aumentar el tamaño del hashtable puede reducir el número de colisiones en primer lugar.

Entonces, en teoría, solo una tabla hash respaldada por una matriz con un número infinito de elementos y una función hash perfecta sería capaz de lograr un rendimiento O (1) , ya que esa es la única forma de evitar las colisiones hash que aumentan el número de operaciones requeridas. Por lo tanto, para cualquier matriz de tamaño finito será en un momento u otro inferior a O (1) debido a las colisiones hash.

Echemos un vistazo a un ejemplo. Usemos una tabla hash para almacenar los siguientes pares (key, value) :

(Name, Bob)
(Occupation, Student)
(Location, Earth)

Implementaremos el back-end de hashtable con una matriz de 100 elementos.

La key se usará para determinar un elemento de la matriz para almacenar el par ( key , value ). Para determinar el elemento, se hash_function la función hash_function :

hash_function("Name") devuelve 18
hash_function("Occupation") devuelve 32
hash_function("Location") devuelve 74 .

A partir del resultado anterior, asignaremos los pares (key, value) a los elementos de la matriz.

array[18] = ("Name", "Bob") array[32] = ("Occupation", "Student") array[74] = ("Location", "Earth")

La inserción solo requiere el uso de una función hash, y no depende del tamaño de la tabla hash ni de sus elementos, por lo que se puede realizar en tiempo O (1).

Del mismo modo, la búsqueda de un elemento utiliza la función hash.

Si queremos buscar la clave "Name" , realizaremos una función hash_function("Name") para descubrir qué elemento de la matriz reside el valor deseado.

Además, la búsqueda no depende del tamaño de la tabla hash ni del número de elementos almacenados, por lo tanto, una operación O (1).

Todo está bien. Intentemos agregar una entrada adicional de ("Pet", "Dog") . Sin embargo, hay un problema, ya que hash_function("Pet") devuelve 18 , que es el mismo hash para la clave "Name" .

Por lo tanto, tendremos que resolver esta colisión hash. Supongamos que la función de resolución de colisión hash que usamos encontró que el nuevo elemento vacío es 29 :

array[29] = ("Pet", "Dog")

Como hubo una colisión hash en esta inserción, nuestro rendimiento no fue del todo O (1).

Este problema también surgirá cuando intentemos buscar la clave "Pet" , ya que al intentar encontrar el elemento que contiene la tecla "Pet" al ejecutar hash_function("Pet") siempre se devolverá 18 inicialmente.

Una vez que busquemos el elemento 18, encontraremos la clave "Name" lugar de "Pet" . Cuando encontremos esta incoherencia, tendremos que resolver la colisión para recuperar el elemento correcto que contiene la clave real "Pet" . La resolución de una colisión hash es una operación adicional que hace que la tabla no funcione a O (1) vez.

Entiendo que O (1) no es necesariamente constante; más bien, no depende de las variables consideradas. Por lo tanto, se puede decir que una búsqueda hash es O (1) con respecto al número de elementos en el hash, pero no con respecto a la longitud de los datos que se procesan o la proporción de elementos a los segmentos en el hash.

El otro elemento de confusión es que la notación O grande describe el comportamiento limitante. Por lo tanto, una función f (N) para valores pequeños de N puede mostrar una gran variación, pero aún sería correcto decir que es O (1) si el límite cuando N se acerca al infinito es constante con respecto a N.