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?

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.

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.$O(1)$$C$
• C × n $O(n)$ es realmente , donde determina el ángulo.$C \times n$$C$
• ( C × n ) 2$O(n^2)$ es realmente , donde determina la nitidez de la curva.$(C \times n)^2$$C$

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.$O(1)$$C$$O(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(\log{n})$$O(n \log{n})$

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 ".$X$$X$

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.

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.

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 , $\Theta(n^2)$ $cn^2$$C$$n_0$$n\geq n_0$$cn^2$$n_0=100,000,000$y 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 Strassen$n$$n^2 < 1000n$$O(n^{2.3729})$ algoritmo es más rápido a menos que sus matrices sean realmente grandes.$O(n^{2.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$n$$n^2$$n^3$$\Theta(n^2)$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.

$f (n) = O (n^2)$$n_0$$f (n) < c n^2$$n > n_0$

$c n^2$$n^2 + 10^{18}$

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".

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.

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).

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.

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).

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).

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(n^2)$

$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. $1n^2$

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

1. $200$
2. $11 \times 10 = 110$
3. $4 \times 10 \times 3.32 \approx 134$
4. $1 \times 100 = 100$

$O(n^2)$$O(1), O(n)$$O(nlog(n))$$O(n^2)$$O(1)$$O(n^2)$$O(1)$