"Para valores pequeños de n, O (n) se puede tratar como si fuera O (1)"

26

He escuchado varias veces que para valores suficientemente pequeños de n, O (n) puede considerarse / tratarse como si fuera O (1).

Ejemplo :

La motivación para hacerlo se basa en la idea incorrecta de que O (1) siempre es mejor que O (lg n), siempre es mejor que O (n). El orden asintótico de una operación solo es relevante si, en condiciones realistas, el tamaño del problema se vuelve realmente grande. Si n sigue siendo pequeño, entonces todos los problemas son O (1).

¿Qué es suficientemente pequeño? 10? 100? 1,000? ¿En qué momento dice "ya no podemos tratar esto como una operación gratuita"? ¿Hay una regla de oro?

Parece que podría ser de dominio o caso específico, pero ¿hay alguna regla general sobre cómo pensar en esto?

rianjs
fuente
44
La regla general depende del problema que desee resolver. ¿Ser rápido en sistemas embebidos con ? Publicar en teoría de la complejidad? n100
Raphael
3
Pensando más en ello, se siente básicamente imposible llegar a una sola regla general, porque los requisitos de rendimiento están determinados por su dominio y sus requisitos comerciales. En entornos sin recursos limitados, n podría ser bastante grande. En entornos severamente restringidos, puede ser bastante pequeño. Eso parece obvio ahora en retrospectiva.
rianjs
12
@rianjs Parece que te estás confundiendo O(1)de forma gratuita . El razonamiento detrás de las primeras oraciones es que O(1)es constante , lo que a veces puede ser increíblemente lento. Un cálculo que lleva mil millones de años, independientemente de la entrada, es un O(1)cálculo.
Mooing Duck
1
Pregunta relacionada sobre por qué usamos las asíntotas en primer lugar.
Raphael
3
@rianjs: tenga en cuenta los chistes en la línea de "un pentágono es aproximadamente un círculo, para valores suficientemente grandes de 5". La oración sobre la que está preguntando hace un punto, pero dado que le ha causado cierta confusión, puede valer la pena preguntarle a Eric Lippert en qué medida esta elección exacta de fraseo tuvo un efecto humorístico. Podría haber dicho, "si hay un límite superior en entonces cada problema es " y aún así ha sido matemáticamente correcto. "Pequeño" no es parte de las matemáticas. O ( 1 )nO(1)
Steve Jessop

Respuestas:

21

Todos los órdenes de magnitud implican una constante , varios de ellos en realidad. Cuando el número de elementos es lo suficientemente grande, esa constante es irrelevante. La pregunta es si el número de elementos es lo suficientemente pequeño como para que esa constante domine.C

Aquí hay una forma visual de pensarlo.

ingrese la descripción de la imagen aquí

Todos tienen una constante de inicio que determina su punto de partida en el eje Y. Cada uno también tiene una constante crítica domina qué tan rápido aumentarán.C

  • Para , determina el tiempo.CO(1)C
  • C × n CO(n) es realmente , donde determina el ángulo.C×nC
  • ( C × n ) 2 CO(n2) es realmente , donde determina la nitidez de la curva.(C×n)2C

Para determinar qué algoritmo debe usar, necesita estimar el lugar donde se cruzan los tiempos de ejecución. Por ejemplo, una solución con un tiempo de arranque alto o una alta perderá frente a una solución O ( n ) con un tiempo de arranque bajo y una C baja en un número bastante grande de elementos.CO(1)CO(n)C

Aquí hay un ejemplo del mundo real. Tienes que mover un montón de ladrillos a través de un patio. Puede moverlos de a poco con las manos o ir a buscar una retroexcavadora enorme y lenta para levantarlos y conducirlos en un solo viaje. ¿Cuál es su respuesta si hay tres ladrillos? ¿Cuál es su respuesta si hay tres mil?

Aquí hay un ejemplo de CS. Digamos que necesita una lista que siempre está ordenada. Podría usar un árbol que se mantendrá en orden para . O puede usar una lista sin ordenar y volver a ordenar después de cada inserción o eliminación en O ( n log n ) . Debido a que las operaciones de árbol son complicadas (tienen una constante alta) y la clasificación es tan simple (constante baja), es probable que la lista gane a cientos o miles de elementos.O(logn)O(nlogn)

Puede observar este tipo de cosas, pero al final la evaluación comparativa es lo que lo hará. También debe observar cuántos elementos tendrá normalmente y mitigar el riesgo de recibir más. También querrá documentar su suposición como "el rendimiento se degradará rápidamente sobre elementos" o "asumimos un tamaño máximo establecido de X ".XX

Debido a que estos requisitos están sujetos a cambios, es importante poner este tipo de decisiones detrás de una interfaz. En el ejemplo de árbol / lista anterior, no exponga el árbol o la lista. De esa manera, si sus suposiciones resultan ser incorrectas, o si encuentra un algoritmo mejor, puede cambiar de opinión. Incluso puede hacer un algoritmo híbrido y cambiar dinámicamente a medida que aumenta el número de elementos.

Schwern
fuente
No tiene sentido decir . Lo que realmente quieren decir es que si el tiempo de ejecución es T = O ( 1 ) a continuación (en muchos casos) T C . Si T = O ( n ) , en muchos casos T C n , o más formalmente T = C n + o ( n ) . Y así. Sin embargo, tenga en cuenta que en otros casos la constante C varía conO(1)=O(C)T=O(1)TCT=O(n)TCnT=Cn+o(n)C , dentro de ciertos límites. n
Yuval Filmus
@YuvalFilmus Por eso me gustan los gráficos.
Schwern
Esta es la mejor respuesta, el punto es qué tan rápido crece la función.
Ricardo
1
Bonito gráfico, pero el eje realmente debería etiquetarse "tiempo", no "velocidad". y
Ilmari Karonen
1
¿Es la línea realmente una parábola? Se ve muy plano para pequeñas n y muy empinado para grandes n . O(n2)nn
David Richerby
44

Esto respalda en gran medida las respuestas ya publicadas, pero puede ofrecer una perspectiva diferente.

Es revelador que la pregunta discuta "valores suficientemente pequeños de n ". El objetivo de Big-O es describir cómo crece el procesamiento en función de lo que se está procesando. Si los datos que se procesan siguen siendo pequeños, es irrelevante discutir el Big-O, porque no le interesa el crecimiento (que no está sucediendo).

Dicho de otra manera, si va a una distancia muy corta por la calle, puede ser igual de rápido caminar, usar una bicicleta o conducir. Incluso puede ser más rápido caminar si tomara un tiempo encontrar las llaves de su automóvil, o si su automóvil necesita gasolina, etc.

Para n pequeña , use lo que sea conveniente.

Si está haciendo un viaje a través del país, entonces debe buscar formas de optimizar su manejo, su consumo de combustible, etc.

Eric Hughes
fuente
55
"Para n pequeña, usa lo que sea conveniente". - si ejecuta la operación con frecuencia , elija el más rápido (para su ). Ver también aquí . n
Raphael
44
Gran metáfora!
Evorlor
1
Desde un punto de vista puramente matemático, la complejidad asintótica no te dice nada cuando n < infinity.
Gordon Gustafson
15

La cita es bastante vaga e imprecisa. Hay al menos tres formas relacionadas de interpretarlo.

El punto matemático literal detrás de esto es que, si solo está interesado en instancias de tamaño hasta cierto límite, entonces solo hay finitamente muchas instancias posibles. Por ejemplo, solo hay finitos gráficos en hasta cien vértices. Si solo hay un número finito de instancias, puede, en principio, resolver el problema simplemente construyendo una tabla de búsqueda con todas las respuestas a todas las instancias posibles. Ahora, puede encontrar la respuesta comprobando primero que la entrada no es demasiado grande (lo que lleva tiempo constante: si la entrada es más larga que  k, no es válido) y luego busque la respuesta en la tabla (que lleva tiempo constante: hay un número fijo de entradas en la tabla). Sin embargo, tenga en cuenta que el tamaño real de la tabla es probablemente demasiado grande. Dije que solo hay un número finito de gráficos en cien vértices y es cierto. Es solo que el número finito es mayor que el número de átomos en el universo observable.

Un punto más práctico es que, cuando decimos que el tiempo de ejecución de un algoritmo es , eso solo significa que es asintóticamente c n 2  pasos, para algunos C constantes  . Es decir, hay alguna constante n 0 tal que, para todos los n n 0 , el algoritmo toma aproximadamente c n 2 pasos. Pero tal vez n 0 = 100 , 000 , 000Θ(n2) cn2Cn0nn0cn2n0=100,000,000y solo te interesan las instancias de tamaño mucho más pequeño que eso. Es posible que el límite cuadrático asintótico ni siquiera se aplique a sus instancias pequeñas. Es posible que tenga suerte y que sea más rápido con entradas pequeñas (o que tenga mala suerte y que sea más lento). Por ejemplo, para pequeña  , n 2 < 1000 n, por lo que preferiría ejecutar un algoritmo cuadrático con constantes buenas que un algoritmo lineal con constantes malas. Un ejemplo real de esto es que los algoritmos de multiplicación matricial asintóticamente más eficientes (variantes de Coppersmith – Winograd , que se ejecutan en el tiempo O ( n 2.3729 ) ) rara vez se usan en la práctica porque el O de Strassennn2<1000nO(n2.3729) algoritmo es más rápido a menos que sus matrices sean realmente grandes.O(n2.8074)

Un tercer punto es que, si  es pequeño, n 2 e incluso n 3  son pequeños. Por ejemplo, si necesita ordenar algunos miles de elementos de datos y solo necesita ordenarlos una vez, cualquier algoritmo de clasificación es lo suficientemente bueno: a Θ ( n 2 )nn2n3Θ(n2)El algoritmo solo necesitará quizás unas pocas decenas de millones de instrucciones para ordenar sus datos, lo que no es mucho tiempo en una CPU que puede realizar miles de millones de instrucciones por segundo. OK, también hay accesos a la memoria, pero incluso un algoritmo lento tomará menos de un segundo, por lo que probablemente sea mejor usar un algoritmo simple y lento y hacerlo bien que usar un algoritmo complejo y rápido y descubrir que es muy rápido pero tiene errores y en realidad no ordena los datos correctamente.

David Richerby
fuente
44
Si bien puntos perfectamente correctos y válidos, creo que te perdiste el punto. Parece que significaban que a veces el algoritmo con funciona mejor que un algoritmo con O ( 1 ) , para n s lo suficientemente pequeños . Esto sucede, por ejemplo, cuando el primero tiene un tiempo de ejecución de 10 n + 50 , mientras que el segundo tiene una duración de 100000 . Entonces, para n lo suficientemente pequeño, en realidad es más rápido usar el protocolo O ( n ) . O(n)O(1)n10n+50100000nO(n)
Ran G.
@Sonó. ¿No viene eso bajo mi segundo caso? (¿Especialmente si lo edito para decir algo más como "Un algoritmo lineal con constantes buenas podría vencer a un algoritmo constante / logarítmico con constantes malas"?)
David Richerby
1
Sería bueno mencionar explícitamente la importancia de las constantes cuando n es pequeño. Es algo que probablemente no se le ocurriría a alguien que no lo ha escuchado antes.
Rob Watts
9

f(n)=O(n2)n0f(n)<cn2n>n0

cn2n2+1018

Por otro lado, si solo encuentra los valores n = 1, 2 y 3, entonces en la práctica no hace una diferencia lo que hace f (n) para n ≥ 4, por lo que podría considerar que f ( n) = O (1), con c = max (f (1), f (2), f (3)). Y eso es lo que significa suficientemente pequeño: si la afirmación de que f (n) = O (1) no lo engaña si los únicos valores de f (n) que encuentra son "suficientemente pequeños".

gnasher729
fuente
5

Si no crece, es O (1)

La declaración del autor es un poco axiomática.

Las órdenes de crecimiento describen lo que sucede con la cantidad de trabajo que debe hacer a medida que Naumenta. Si sabe que eso Nno aumenta, su problema es efectivo O(1).

Recuerde que eso O(1)no significa "rápido". Un algoritmo que siempre requiere 1 billón de pasos para completar es O(1). Un algoritmo que lleva de 1 a 200 pasos, pero nunca más, lo es O(1). [1]

Si su algoritmo sigue exactamente los N ^ 3pasos, y sabe que Nno puede ser más de 5, nunca puede tomar más de 125 pasos, por lo que es efectivo O(1).

Pero de nuevo, O(1)no necesariamente significa "lo suficientemente rápido". Esa es una pregunta separada que depende de su contexto. Si lleva una semana terminar algo, probablemente no te importe si es técnicamente O(1).


[1] Por ejemplo, la búsqueda en un hash es O(1), a pesar de que las colisiones de hash significan que es posible que tenga que mirar a través de varios elementos en un cubo, siempre que haya un límite estricto sobre cuántos elementos puede haber en ese cubo.

Nathan Long
fuente
1
Todo eso suena válido, excepto por esto: "Si su algoritmo toma exactamente N ^ 3 pasos, y sabe que N no puede ser más de 5, nunca puede tomar más de 125 pasos, entonces es O (1)". . Nuevamente, si un algoritmo toma un número entero, y mi soporte máximo de números enteros es 32767, ¿es O (1)? Obviamente no. Big-O no cambia según los límites de los parámetros. Es O (n) incluso si sabe que 0 <n <3 porque n = 2 toma el doble de tiempo que n = 1.
JSobell
3
@JSobell Pero es O (1). Si hay una limitación que limita su n para f (n), significa que no puede crecer indefinidamente. Si su n está limitado por 2 ^ 15, su gran función n ^ 2 está en realidad g(n) = min(f(2^15), f(n)), que está en O (1). Dicho esto, en la práctica las constantes son muy importantes y claramente n puede llegar a ser lo suficientemente grande como para que un análisis asintótico sea útil.
Voo
2
@JSobell Esto es similar a la pregunta de si las computadoras son realmente "completas o no", dado que técnicamente no pueden tener espacio de almacenamiento infinito. Técnicamente, matemáticamente, una computadora no es una máquina de Turing "verdadera". En la práctica, no existe la "cinta infinita", pero los discos duros se acercan lo suficiente.
Kyle Strand
Hace varios años escribí un sistema de riesgo financiero que involucraba n ^ 5 manipulaciones de matriz, por lo que tenía un límite práctico de n = 20 antes de que los recursos se convirtieran en un problema.
JSobell
Lo sentimos, presioné Enter demasiado pronto. Hace varios años escribí un sistema de riesgo financiero que involucraba n ^ 5 manipulaciones de matriz, por lo que tenía un límite práctico de n = 20 antes de que los recursos se convirtieran en un problema. De acuerdo con esta lógica defectuosa, la función creada es O (1) porque tengo un límite de 20. Cuando el cliente dice "Hmm, quizás deberíamos moverlo a 40 como límite ... Sí, el algoritmo es O (1) ) así que no hay problema "... Es por eso que los límites en una entrada no tienen sentido. La función era O (n ^ 5), no O (1), y este es un ejemplo práctico de por qué Big-O es independiente de los límites.
JSobell
2

Ahora, puedo usar una tabla hash y tener búsquedas O (1) (dejando de lado la implementación específica de la tabla hash), pero si tuviera, por ejemplo, una lista, tendría búsquedas O (n). Dado este axioma, estos dos son iguales si las colecciones son lo suficientemente pequeñas. Pero en algún momento divergen ... ¿cuál es ese punto?

Prácticamente, es el punto donde construir la tabla hash requiere más que el beneficio que obtienes de las búsquedas mejoradas. Esto variará mucho según la frecuencia con la que esté haciendo la búsqueda, en comparación con la frecuencia con la que está haciendo otras cosas. O (1) vs O (10) no es gran cosa si lo haces una vez. Si lo hace miles de veces por segundo, incluso eso es importante (aunque al menos es importante a un ritmo que aumenta linealmente).

Telastyn
fuente
Si quiere estar seguro, haga algunos experimentos para ver qué estructura de datos es mejor para sus parámetros.
Yuval Filmus
@Telastyn Yuval Filmus tiene razón, si realmente quieres estar seguro. Conozco a una persona que se llama Jim, sus parámetros están bien. Pero no escuchó consejos como el de Yuval. Realmente deberías escuchar a Yuval para estar seguro y seguro.
InformadoA
2

Si bien la cita es cierta (pero vaga), también hay peligros. Imo, debe observar la complejidad en cualquier etapa de su aplicación.

Es demasiado fácil decir: oye, solo tengo una pequeña lista, si quiero verificar si el elemento A está en la lista, simplemente escribiré un bucle fácil para recorrer la lista y comparar los elementos.

Luego, su programador de amigos necesita usar la lista, ve su función y dice: oye, no quiero ningún duplicado en la lista, por lo que usa la función para cada elemento agregado a la lista.

(Eso sí, todavía es una pequeña lista de escenarios).

3 años después, llegué y mi jefe acaba de hacer una gran venta: nuestro software será utilizado por un gran minorista nacional. Antes solo atendíamos pequeñas tiendas. Y ahora mi jefe viene a mí jurando y gritando, por qué el software, que siempre "funcionó bien" ahora es tan terriblemente lento.

Resulta que esa lista era una lista de clientes, y nuestros clientes solo tenían unos 100 clientes, por lo que nadie se dio cuenta. La operación de llenar la lista era básicamente una operación O (1), porque tomó menos de un milisegundo. Bueno, no tanto cuando hay que agregarle 10.000 clientes.

Y años después de la mala decisión original de O (1), la compañía casi perdió un gran cliente. Todo debido a un pequeño error de diseño / suposición años antes.

Pieter B
fuente
Pero también ilustra una característica importante de muchos sistemas del mundo real: los "algoritmos" que aprende como estudiante universitario son en realidad piezas de las que se hacen "algoritmos" reales. Esto generalmente se insinúa; por ejemplo, la mayoría de las personas saben que la clasificación rápida a menudo se escribe para retroceder al orden de inserción cuando las particiones se vuelven lo suficientemente pequeñas, y que la búsqueda binaria a menudo se escribe para retroceder a la búsqueda lineal. Pero no mucha gente se da cuenta de que el tipo de fusión puede beneficiarse de alguna búsqueda binaria.
Seudónimo
1

La motivación para hacerlo se basa en la idea incorrecta de que O (1) siempre es mejor que O (lg n), siempre es mejor que O (n). El orden asintótico de una operación solo es relevante si, en condiciones realistas, el tamaño del problema se vuelve realmente grande.

Si tengo dos algoritmos con estos tiempos:

  • log (n) +10000
  • n + 1

Entonces existe algún punto donde se cruzan. Para nmás pequeño que eso, el algoritmo "lineal" es más rápido, y para nmás grande que eso, el algoritmo "logarítmico" es más rápido. Muchas personas cometen el error de suponer que el algoritmo logarítmico es más rápido, pero para los pequeños n, no lo es.

Si n sigue siendo pequeño, entonces todos los problemas son O (1).

Me especular lo que se quiere decir aquí es que si nse limita, entonces todos los problemas es O (1). Por ejemplo, si estamos ordenando enteros, podemos optar por usar el ordenamiento rápido. O(n*log(n))obviamente. Pero si decidimos que no puede haber más que 2^64=1.8446744e+19enteros, entonces sabemos que n*log(n)<= 1.8446744e+19*log(1.8446744e+19)<= 1.1805916e+21. Por lo tanto, el algoritmo siempre tomará menos de 1.1805916e+21"unidades de tiempo". Como es un tiempo constante, podemos decir que el algoritmo siempre se puede hacer en ese tiempo constante -> O(1). (Tenga en cuenta que incluso si esas unidades de tiempo son nanosegundos, eso es un total de más de 37411 años). Pero aun así O(1).

Pato mugido
fuente
0

Sospecho que a muchas de estas respuestas les falta un concepto fundamental. O (1): O (n) no es lo mismo que f (1): f (n) donde f es la misma función, porque O no representa una sola función. Incluso el bonito gráfico de Schwern no es válido porque tiene el mismo eje Y para todas las líneas. Para utilizar todos el mismo eje, las líneas tendrían que ser fn1, fn2 y fn3, donde cada una era una función cuyo rendimiento podía compararse directamente con los demás.

He escuchado varias veces que para valores suficientemente pequeños de n, O (n) puede considerarse / tratarse como si fuera O (1)

Bueno, si n = 1 ¿son exactamente iguales? No. Una función que permite un número variable de iteraciones no tiene nada en común con una que no, a la notación big-O no le importa, y nosotros tampoco deberíamos.

La notación Big-O simplemente está ahí para expresar lo que sucede cuando tenemos un proceso iterativo, y cómo se degrada el rendimiento (tiempo o recursos) a medida que aumenta 'n'.

Entonces, para responder la pregunta real ... Diría que aquellos que hacen esa afirmación no entienden la notación Big-O correctamente, porque es una comparación ilógica.

Aquí hay una pregunta similar: si recorro una cadena de caracteres y sé que, en general, mis cadenas serán de menos de 10 caracteres, ¿puedo decir que es el equivalente de O (1), pero si mis cadenas son más largas, entonces yo diría que fue O (n)?

No, porque una cadena de 10 caracteres tarda 10 veces más que una cadena de 1 carácter, ¡pero 100 veces menos que una cadena de 1000 caracteres! Esta encendido).

JSobell
fuente
O(1)f(i)imax{f(0),,f(10)}O(1)
Sí, y este es un ejemplo de donde la notación Big-O es comúnmente mal entendida. Según su argumento, si sé que el valor máximo de n es 1,000,000, entonces mi función es O (1). De hecho, mi función podría ser, en el mejor de los casos, O (1) y, en el peor, O (n). Esta notación se usa para describir la complejidad algorítmica, no una implementación concreta, y siempre usamos la más costosa para describir un escenario, no la mejor. De hecho, según su argumento, ¡cada función que permite n <2 es O (1)! :)
JSobell
n<2O(1)f(n)f(10)nO(1)
Lo sentimos, pero si dice que conocer los límites superiores de n hace una función O (1), entonces está diciendo que la representación de notación está directamente relacionada con el valor de n, y no lo es. Todo lo demás que menciona es correcto, pero sugiere que debido a que n tiene límites, O (1) no es correcto. En la práctica, hay lugares donde lo que usted describe puede ser observable, pero estamos viendo la notación Big-O aquí, no la codificación funcional. Entonces, de nuevo, ¿por qué sugeriría que n tener un máximo de 10 lo convertiría en O (1)? ¿Por qué 10? ¿Por qué no 65535 o 2 ^ 64?
JSobell
Una vez dicho esto, si escribe una función que rellena una cadena a 10 caracteres, siempre se repite sobre la cadena, entonces es O (1) porque n siempre es 10 :)
JSobell
0

Creo que el texto que citó es bastante impreciso (el uso de la palabra "mejor" generalmente no tiene sentido a menos que proporcione el contexto: en términos de tiempo, espacio, etc.) De todos modos, creo que la explicación más simple sería:

O(1)O(1)

Ahora, tomemos un conjunto relativamente pequeño de 10 elementos y tengamos algunos algoritmos para ordenarlo (solo un ejemplo). Supongamos que mantenemos los elementos en una estructura que también nos proporciona un algoritmo capaz de ordenar los elementos en tiempo constante. Digamos que nuestros algoritmos de clasificación pueden tener las siguientes complejidades (con notación big-O):

  1. O(1)
  2. O(n)
  3. O(nlog(n))
  4. O(n2)

O(1)

Ahora, "revelemos" las verdaderas complejidades de los algoritmos de clasificación mencionados anteriormente (donde "verdadero" significa no ocultar la constante), representados por la cantidad de pasos necesarios para finalizar (y supongamos que todos los pasos toman la misma cantidad de tiempo):

  1. 200
  2. 11n
  3. 4nlog(n)
  4. 1n2

Si nuestra entrada es de tamaño 10, estas son cantidades exactas de pasos para cada algoritmo mencionado anteriormente:

  1. 200
  2. 11×10=110
  3. 4×10×3.32134
  4. 1×100=100

O(n2)O(1),O(n)O(nlog(n))O(n2)O(1)O(n2)O(1)

3yakuya
fuente