¿Qué pasa con el O(1)?

Question

He estado notando algo muy extraño uso de O(1) en la discusión de los algoritmos que involucran hash y tipos de búsquedas, a menudo en el contexto de la utilización de un tipo de diccionario proporcionados por el sistema de lenguaje, o uso de diccionario o hash-tipos de matriz, con la utilización de la matriz de índice de notación.

Básicamente, S(1) significa acotado por una constante de tiempo y (normalmente) espacio fijo.Algunos bastante operaciones fundamentales son O(1), aunque el uso de lenguajes intermedios y especiales VMs tiende a distorsionar queridos pensamiento (p. ej., ¿cómo hace uno para amortizar el recolector de basura y otros procesos dinámicos más de lo que sería O(1) actividades).

Pero haciendo caso omiso de la amortización de las latencias, recolección de basura, y así sucesivamente, 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 puede ser O(1) excepto bajo condiciones muy especiales.

Aunque me he dado cuenta de esto antes, un ejemplo sólo se presentó en el Pandincus pregunta, "'Correcto' de la colección que se utiliza para obtener los elementos en O(1) vez en C# .NETA?".

Como señalé, el único de la colección sé de que proporciona O(1) acceso garantizado bound es un fijo vinculado matriz con un número entero, el valor del índice.La presunción es que la matriz es implementado por algunos de asignación de memoria de acceso aleatorio que se utiliza O(1) las operaciones para localizar la celda que tiene ese índice.

Para las colecciones que involucran algún tipo de búsqueda para determinar la ubicación de una coincidencia de células de un tipo diferente de índice (o para una matriz dispersa con índice de tipo entero), la vida no es tan fácil.En particular, si hay collisons y la congestión es posible, el acceso no es exactamente O(1).Y si la colección es flexible, se debe reconocer y amortizar el costo de la expansión de la estructura subyacente (tal como un árbol o una tabla hash) para que el alivio de la congestión (por ejemplo, la alta incidencia de la colisión o árbol de desequilibrio).

Yo nunca habría pensado en hablar de estos flexible y dinámico de estructuras como O(1).Sin embargo, veo que les ofreció como O(1) soluciones sin ningún tipo de identificación de las condiciones que deben mantenerse para que realmente tienen O(1) el acceso seguro (así como tiene que ser constante despreciablemente pequeña).

LA PREGUNTA:Toda esta preparación es realmente una pregunta.¿Cuál es la naturalidad alrededor de O(1) y por qué es aceptada ciegamente?Se reconoció que, incluso, O(1) puede ser indeseable grandes, aunque casi constante?O es O(1) simplemente la apropiación de un computacional-la complejidad de la noción de uso informal?Estoy perplejo.

ACTUALIZACIÓN:Las Respuestas y comentarios donde me fue casual acerca de la definición de O(1) a mí mismo, y he reparado que.Todavía estoy buscando buenas respuestas, y algunas de las cadenas de comentarios son bastante más interesante que la de sus respuestas, en unos pocos casos.

Answer 1

Entiendo que O (1) no es necesariamente constante; más bien, no depende de las variables bajo consideración. Por lo tanto, se puede decir que una búsqueda de 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 van a hash o la proporción de elementos a cubos en el hash.

El otro elemento de confusión es que la notación O grande describe un 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 así sería correcto decir que es O (1) si el límite a medida que N se acerca al infinito es constante con respecto a N.

Answer 2

El problema es que las personas son realmente descuidadas con la terminología. Aquí hay 3 clases importantes pero distintas:

O (1) peor de los casos

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

O (1) amortizado en el peor de los casos

Amortized significa que no todas las operaciones son O(N) en el peor de los casos, pero para cualquier secuencia de N operaciones, el costo total de la secuencia es <=> en el peor de los casos. Esto significa que, aunque no podemos limitar el costo de una sola operación por una constante, siempre habrá suficiente & "; Rápido &"; operaciones para compensar el & "; lento &"; operaciones tales que el tiempo de ejecución de la secuencia de operaciones es lineal en el número de operaciones.

Por ejemplo, el Dynamic Array estándar que duplica su capacidad cuando se llena requiere <= > tiempo amortizado para insertar un elemento al final, aunque algunas inserciones requieren <=> tiempo, siempre hay suficientes <=> inserciones que insertar N elementos siempre requiere <=> tiempo total.

O (1) caso medio

Este es el más complicado. Hay dos definiciones posibles de caso promedio: una para algoritmos aleatorios con entradas fijas y otra para algoritmos deterministas con entradas aleatorias.

Para algoritmos aleatorios con entradas fijas, podemos calcular el tiempo promedio de ejecución de caso para cualquier 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 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 todo N! posibles permutaciones de la entrada igualmente probable. Entonces, el tiempo de ejecución promedio de casos es el tiempo promedio de ejecución de todas las entradas posibles, ponderado por la probabilidad de cada entrada.

Dado que el tema de esta pregunta son las tablas hash, que son deterministas, me centraré en la segunda definición de caso promedio. Ahora, no siempre podemos determinar la distribución de probabilidad de las entradas porque, bueno, podríamos estar troceando 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 las personas simplemente asumen que las entradas se comportan bien y que la función hash se comporta bien de tal manera que el valor hash de cualquier entrada se distribuye esencialmente de manera 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 de caso promedio para las tablas hash proviene de asumir que todos los valores hash están distribuidos uniformemente. Si se viola esta suposición (lo cual generalmente no se hace, pero ciertamente puede suceder y sucede), el tiempo de ejecución ya no es <=> en promedio.

Consulte también Denegación de servicio por complejidad algorítmica . En este artículo, los autores discuten cómo explotaron algunas debilidades en las funciones hash predeterminadas utilizadas 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 estas cadenas que resultaron en el peor comportamiento <=> en las tablas hash utilizadas por los servidores web.

Answer 3

  

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

Solo para aclarar estas son dos declaraciones separadas. Puede 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 prácticamente ENORME y sigue siendo O (1). A menudo se descuida que si 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 a un O (1) si las constantes y los tamaños de los conjuntos de datos son de la escala adecuada.

La notación

O () es una medida de la complejidad, no el tiempo que tomará un algoritmo, o una medida pura de cómo & "; bueno &"; un algoritmo dado es para un propósito dado.

Answer 4

Puedo ver lo que estás diciendo, pero creo que hay un par de suposiciones básicas subyacentes 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 se distribuye de forma bastante aleatoria, o al menos no está diseñado a propósito para que la función hash funcione mal.

La complejidad del peor caso de una búsqueda de tabla Hash es O (n), pero eso es extremadamente improbable dados los 2 supuestos anteriores.

Answer 5

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

Una tabla hash generalmente tiene un par de clave y valor, donde la tecla se usa como parámetro de una función (a 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 de hash donde la función hash devolverá un elemento de una matriz que ya está ocupada. Esto necesitará una resolución de colisión para encontrar otra elemento vacío.

Cuando se produce una colisión hash, no se puede realizar una búsqueda o inserción en el tiempo O (1). Sin embargo, buenos algoritmos de resolución de colisión pueden reducir el número de intentos para encontrar otro lugar vacío que se pueda acomodar o aumentar el tamaño de la tabla hash 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 podría lograr el rendimiento O (1) , ya que esa es la única manera para evitar colisiones hash que aumenten el número de operaciones requeridas. Por lo tanto, para cualquier matriz de tamaño finito en un momento u otro será menor que O (1) debido a colisiones hash.

---

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

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

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

El key se usará para determinar un elemento de la matriz para almacenar el par (value, hash_function). Para determinar el elemento, se utilizará hash_function("Name"):

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

Del resultado anterior, asignaremos los pares ("Pet", "Dog") en 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 puede realizarse en tiempo O (1).

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

Si queremos buscar la clave hash_function("Pet"), realizaremos un "Pet" para averiguar 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 <=>. Sin embargo, hay un problema, ya que <=> devuelve 18 , que es el mismo hash para la tecla <=>.

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

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

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

Este problema también surgirá cuando intentemos buscar la tecla <=>, ya que tratar de encontrar el elemento que contiene la tecla <=> realizando <=> siempre devolverá 18 inicialmente.

Una vez que busquemos el elemento 18, encontraremos la clave <=> en lugar de <=>. Cuando encontremos esta inconsistencia, necesitaremos resolver la colisión en ordener para recuperar el elemento correcto que contiene la clave <=> real. Resolver una colisión de hash es una operación adicional que hace que la tabla de hash no funcione en el momento O (1).

Answer 6

No puedo hablar con las otras discusiones que has visto, pero hay al menos un algoritmo de hash que está garantizado como O (1).

Cuckoo hashing mantiene un invariante para que no haya encadenamiento en la tabla hash. La inserción se amortiza O (1), la recuperación es siempre O (1). Nunca he visto una implementación, 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 supone que el cálculo de hash también es O (1). Se podría argumentar que para las cadenas de longitud K, cualquier hash es mínimamente O (K). En realidad, puede vincular K con bastante facilidad, diga K & Lt; 1000. O (K) ~ = O (1) para K & Lt; 1000.

Answer 7

Puede haber un error conceptual en cuanto a cómo está entendiendo 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 tarda O (n) tiempo, significa que el tiempo de ejecución del peor caso de un algoritmo depende linealmente del tamaño del conjunto de entrada.

Cuando un algoritmo tarda 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 finito fijo.

Ahora, eso no significa de ninguna manera 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) se convierte en O (1).

En este caso, utilizamos una estructura de datos trie como 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 ser consideró O (1) (si defino un campo de caracteres que tiene como máximo k caracteres de longitud, lo que puede ser una suposición razonable para muchos casos).

Para una tabla hash, siempre y cuando suponga que la función hash es buena (distribuida aleatoriamente) y lo suficientemente escasa como para minimizar las colisiones, y el rehashing se realiza cuando la estructura de datos es lo suficientemente densa, puede considerarlo como un O (1) estructura de tiempo de acceso.

En conclusión, el tiempo O (1) puede estar sobrevalorado para muchas cosas. Para estructuras de datos grandes, la complejidad de una función hash adecuada puede no ser trivial, y existen suficientes casos de esquina donde la cantidad de colisiones hacen que se comporte como una estructura de datos O (n), y la repetición puede ser prohibitivamente costosa. En cuyo caso, una estructura O (log (n)) como un AVL o un árbol B puede ser una alternativa superior.

Answer 8

En general, creo que las personas los usan comparativamente sin tener en cuenta la exactitud. Por ejemplo, las estructuras de datos basadas en hash son O (1) (promedio), busque si está bien diseñado y tiene un buen hash. Si todo se convierte en un solo cubo, entonces es O (n). Generalmente, aunque uno usa un buen algoritmo y las claves están distribuidas razonablemente, 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 habla de generalidades, sin las calificaciones. Si, por otro lado, estamos discutiendo implementaciones específicas, entonces probablemente sea más preciso.

Answer 9

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

---

Para responder por qué esto es relevante: el OP preguntó por qué O (1) parecía arrojarse tan casualmente cuando en su mente obviamente no podía aplicarse en muchas circunstancias. Esta respuesta explica que el tiempo O (1) realmente es posible en esas circunstancias.

Answer 10

Tabla Hash implementaciones son en la práctica no "exactamente" O(1) en uso, si prueba que usted va a encontrar que un promedio de alrededor de 1,5 búsquedas para encontrar una clave dada a través de un gran conjunto de datos

( debido a que el hecho de que las colisiones ¿ se producen, y tras la colisión, un lugar diferente debe ser asignado )

También, En la práctica, HashMaps están respaldados por las matrices con un tamaño inicial, que es "crecido" a doble su tamaño cuando se alcanza el 70% plenitud en promedio, lo que da un relativamente buen espacio de direccionamiento.Después de un 70% de la plenitud de la colisión de las tasas de crecer más rápido.

Big O teoría afirma que si usted tiene un O(1) el algoritmo, o incluso una O(2) el algoritmo, el factor crítico es el grado de la relación entre la entrada-establecer el tamaño y pasos para insertar/fetch uno de ellos.O(2) todavía es constante en el tiempo, así que sólo aproximada como O(1), porque significa más o menos lo mismo.

En realidad, sólo hay 1 manera de tener un "perfecto hashtable" con O(1), y que requiere:

1. Un Mundial Perfecto Hash Generador De Claves
2. Un Ilimitado espacio de direccionamiento.

( Caso de excepción:si usted puede calcular por adelantado de todas las permutaciones de las claves para el sistema, y su objetivo respaldo de la dirección de la tienda espacio se define como el tamaño en el que puede contener todas las teclas que se permite, entonces usted puede tener un perfecto hash, pero su "dominio limitado de la" perfección )

Dado un fijo de asignación de memoria, no es plausible en el menos para tener esto, porque es de suponer que de haber alguna forma mágica para empacar una cantidad infinita de datos en una cantidad fija de espacio sin pérdida de datos, y eso es físicamente imposible.

Así, a posteriori, el llegar O(1.5), que todavía es constante en el tiempo, en una cantidad finita de memoria, incluso con una relativamente Ingenuo hash generador de claves, considero bastante maldito impresionante.

Suffixory nota Nota: yo uso S(1.5) y O(2) aquí.En realidad, estas no existen en big-o.Estos son sólo lo que la gente a quien no sabe big-o asumir que es el fundamento.

Si algo tarda 1.5 pasos para encontrar una clave, o 2 pasos para encontrar esa clave o 1 pasos para encontrar esa clave, pero el número de pasos que nunca supera los 2 y si se toma el paso 1 o 2 es completamente aleatoria, entonces es todavía Grande-O de O(1).Esto es porque no importa ¿ muchos elementos para agregar a el tamaño del conjunto de datos, aún mantiene la <2 pasos.Si para todas las tablas de > 500 claves se tarda de 2 pasos, entonces se puede asumir esos 2 pasos son, de hecho, un paso con 2 piezas, ...que aún es O(1).

Si usted no puede hacer esta suposición, entonces su no ser Grande-O pensando en todo, porque entonces usted debe utilizar el número que representa el número de finito computacional pasos necesarios para hacer de todo, y de "un paso" no tiene sentido para usted.Acaba de meterse en la cabeza que hay NO correlación directa entre los Grandes-O y el número de ciclo de ejecución de los involucrados.

Answer 11

O (1) significa, exactamente, que la complejidad temporal 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 supuestos algoritmos de tiempo O (1) en realidad no son O (1) y simplemente van tan lentamente que están limitados por todos los valores de entrada prácticos.

Answer 12

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 utilizado. Por lo general, los recolectores de basura modernos alternan los modos a medida que la memoria se llena para mantener estos costos bajo control. Por ejemplo, un enfoque común es usar un colector de copia de estilo Cheney cuando la presión de la memoria es baja porque paga un costo proporcional al tamaño del conjunto en vivo a cambio de usar más espacio, y cambiar a un colector de marcas y barridos 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 al conjunto completo o conjunto muerto para barrer. Para el momento en que agregue la marca de la tarjeta y otras optimizaciones, etc., el peor de los casos para un recolector de basura práctico puede ser bastante peor, al elegir un factor logarítmico adicional para algunos patrones de uso.

Entonces, si asigna una tabla hash grande, incluso si accede a ella usando O (1) busca todo el tiempo durante su vida útil, si lo hace en un entorno de recolección de basura, ocasionalmente el recolector de basura atravesará toda la matriz , porque es de 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 manera no trivial. El costo tan bajo depende mucho de lo que esté haciendo en el mismo proceso, por lo que el análisis no es compositivo.

Además, más allá del problema de copia vs. compacto vs. marca y barrido, los detalles de implementación pueden afectar drásticamente las complejidades resultantes:

1. Los recolectores de basura incrementales que rastrean trozos sucios, etc., pueden hacer que desaparezcan esos grandes recorridos.
2. 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.
3. Si un algoritmo de estilo de marca y barrido es concurrente o detiene el mundo
4. Si marca las asignaciones frescas en negro si las deja blancas hasta que las deje caer en un contenedor negro.
5. Si su idioma admite modificaciones de punteros puede permitir que algunos recolectores de basura trabajen de una sola pasada.

Finalmente, cuando hablamos de un algoritmo, hablamos de un hombre de paja. Las asintóticas nunca incorporarán completamente todas las variables de su entorno. Rara vez implementa cada detalle de una estructura de datos tal como está diseñada. Toma prestada una característica aquí y allá, coloca una tabla hash porque necesita un acceso rápido a la clave desordenada, usa una búsqueda de unión sobre conjuntos disjuntos con compresión de ruta y unión por rango para fusionar regiones de memoria allí porque no puede darse el lujo de pagar un costo proporcional al tamaño de las regiones cuando las combine o lo que tenga. Estas estructuras son primitivas y las asintóticas lo ayudan a planificar las características generales de rendimiento de la estructura 'en general', pero el conocimiento de cuáles son 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; mapearlo en la memoria desde un archivo y administrarlo usted mismo. Sin embargo, probablemente no te gusten las constantes involucradas.

Answer 13

Creo que cuando muchas personas arrojan el término " O (1) " implícitamente tienen en mente un " small " constante, lo que sea " pequeño " significa en su contexto.

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