sheet omega little for examples dummies complexity cheat big theory complexity-theory big-o

theory - omega - ¿Hay algún algoritmo O(1/n)?



little o notation (30)

¿Hay algún algoritmo O (1 / n)?

¿O cualquier otra cosa que sea menor que O (1)?

¿Qué hay de no ejecutar la función en absoluto (NOOP)? o utilizando un valor fijo. ¿Eso cuenta?

¿Qué pasa con esto?

void FindRandomInList(list l) { while(1) { int rand = Random.next(); if (l.contains(rand)) return; } }

a medida que aumenta el tamaño de la lista, el tiempo de ejecución esperado del programa disminuye.

¿Qué problemas se hacen más fáciles a medida que crece la población? Una respuesta es algo como bittorrent donde la velocidad de descarga es una función inversa del número de nodos. Contrariamente a un automóvil, que se ralentiza cuanto más se carga, una red de intercambio de archivos como bittorrent acelera a más nodos conectados.

A menudo utilizo O (1 / n) para describir las probabilidades que se hacen más pequeñas a medida que las entradas aumentan, por ejemplo, la probabilidad de que salga una moneda justa en las tiradas log2 (n) es O (1 / n).

Como se ha señalado, aparte de la posible excepción de la función nula, no puede haber funciones O(1/n) , ya que el tiempo necesario tendrá que acercarse a 0.

Por supuesto, hay algunos algoritmos, como el definido por Konrad, que parecen ser menos que O(1) en al menos algún sentido.

def get_faster(list): how_long = 1/len(list) sleep(how_long)

Si desea investigar estos algoritmos, debe definir su propia medición asintótica o su propia noción del tiempo. Por ejemplo, en el algoritmo anterior, podría permitir el uso de varias operaciones "libres" una cantidad determinada de veces. En el algoritmo anterior, si defino t ''excluyendo el tiempo para todo menos el sueño, entonces t'' = 1 / n, que es O (1 / n). Probablemente hay mejores ejemplos, ya que el comportamiento asintótico es trivial. De hecho, estoy seguro de que alguien puede generar sentidos que den resultados no triviales.

Creo que los algoritmos cuánticos pueden realizar múltiples cálculos "a la vez" a través de la superposición ...

Dudo que esta sea una respuesta útil.

De mi aprendizaje anterior de la notación O grande, incluso si necesita 1 paso (como verificar una variable, hacer una asignación), es O (1).

Tenga en cuenta que O (1) es lo mismo que O (6), porque la "constante" no importa. Por eso decimos que O (n) es lo mismo que O (3n).

Entonces, si necesita incluso 1 paso, eso es O (1) ... y como su programa necesita al menos 1 paso, el mínimo que puede seguir un algoritmo es O (1). A menos que si no lo hacemos, entonces es O (0), creo? Si hacemos algo, entonces es O (1), y eso es lo mínimo que puede ir.

(Si elegimos no hacerlo, entonces puede convertirse en una pregunta Zen o Tao ... en el ámbito de la programación, O (1) sigue siendo el mínimo).

O ¿qué tal esto?

programador : jefe, ¡encontré una manera de hacerlo en O (1) vez!
Jefe : no hay necesidad de hacerlo, estamos en bancarrota esta mañana.
programador : oh entonces, se convierte en O (0).

En el análisis numérico, los algoritmos de aproximación deben tener una complejidad asintótica sub-constante en la tolerancia de aproximación.

class Function { public double[] ApproximateSolution(double tolerance) { // if this isn''t sub-constant on the parameter, it''s rather useless } }

Eso no es posible. La definición de Big-O no es mayor que la desigualdad:

A(n) = O(B(n)) <=> exists constants C and n0, C > 0, n0 > 0 such that for all n > n0, A(n) <= C * B(n)

Entonces, B (n) es de hecho el valor máximo, por lo tanto, si disminuye a medida que n aumenta, la estimación no cambiará.

Esta pregunta no es tan estúpida como podría parecer. Al menos en teoría, algo como O (1 / n ) es completamente sensato cuando tomamos la definición matemática de la notación Big O :

Ahora puede sustituir fácilmente g ( x ) por 1 / x ... es obvio que la definición anterior sigue siendo válida para algunos f .

Para el propósito de estimar el crecimiento asintótico del tiempo de ejecución, esto es menos viable ... un algoritmo significativo no puede ser más rápido a medida que crece la entrada. Claro, puedes construir un algoritmo arbitrario para cumplir esto, por ejemplo, el siguiente:

def get_faster(list): how_long = (1 / len(list)) * 100000 sleep(how_long)

Claramente, esta función pasa menos tiempo a medida que aumenta el tamaño de la entrada ... al menos hasta cierto límite, impuesto por el hardware (precisión de los números, tiempo mínimo que la sleep puede esperar, tiempo para procesar argumentos, etc.): este límite sería entonces un límite inferior constante, de hecho, la función anterior aún tiene tiempo de ejecución O (1).

Pero , de hecho, hay algoritmos del mundo real donde el tiempo de ejecución puede disminuir (al menos parcialmente) cuando aumenta el tamaño de entrada. Tenga en cuenta que estos algoritmos no mostrarán un comportamiento de tiempo de ejecución inferior a O (1), sin embargo. Aún así, son interesantes. Por ejemplo, tome el algoritmo de búsqueda de texto muy simple de Horspool . Aquí, el tiempo de ejecución esperado disminuirá a medida que aumente la longitud del patrón de búsqueda (pero el aumento de la duración del pajar aumentará nuevamente el tiempo de ejecución).

La mayoría de las demás respuestas interpretan que big-O se refiere exclusivamente al tiempo de ejecución de un algoritmo. Pero como la pregunta no lo mencionó, pensé que vale la pena mencionar la otra aplicación de big-O en el análisis numérico, que es sobre el error.

Muchos algoritmos pueden ser O (h ^ p) u O (n ^ {- p}) dependiendo de si estamos hablando de tamaño de paso (h) o número de divisiones (n). Por ejemplo, en el método de Euler , busca una estimación de y (h) dado que conoce y (0) y dy / dx (el derivado de y). Tu estimación de y (h) es más precisa cuanto más cerca está h de 0. Entonces, para encontrar y (x) para un x arbitrario, uno toma el intervalo de 0 a x, lo divide hasta n pedazos y ejecuta el método de Euler. en cada punto, para ir de y (0) a y (x / n) a y (2x / n), y así sucesivamente.

Entonces, el método de Euler es un algoritmo O (h) u O (1 / n), donde h se interpreta normalmente como un tamaño de paso y n se interpreta como el número de veces que se divide un intervalo.

También puede tener O (1 / h) en aplicaciones de análisis numérico real, debido a errores de redondeo de punto flotante . Cuanto más pequeño sea el intervalo, mayor será la cancelación para la implementación de ciertos algoritmos, más pérdida de dígitos significativos y, por lo tanto, más errores, que se propagan a través del algoritmo.

Para el método de Euler, si está usando puntos flotantes, use un paso y cancelación lo suficientemente pequeños y está agregando un número pequeño a un número grande, dejando el número grande sin cambios. Para los algoritmos que calculan la derivada y restan entre sí dos números de una función evaluada en dos posiciones muy cercanas, aproximando y ''(x) con (y (x + h) - y (x) / h), en funciones suaves y (x + h) se acerca a y (x) dando como resultado una gran cancelación y una estimación del derivado con menos cifras significativas. Esto a su vez se propagará a cualquier algoritmo para el que requiera la derivada (por ejemplo, un problema de valor de límite).

La notación Big-O representa el peor escenario para un algoritmo que no es lo mismo que su tiempo de ejecución típico. Es sencillo probar que un algoritmo O (1 / n) es un algoritmo O (1). Por definición,
O (1 / n) -> T (n) <= 1 / n, para todos n> = C> 0
O (1 / n) -> T (n) <= 1 / C, ya que 1 / n <= 1 / C para todos n> = C
O (1 / n) -> O (1), ya que la notación Big-O ignora las constantes (es decir, el valor de C no importa)

Nada es más pequeño que O (1) La notación Big-O implica el mayor orden de complejidad para un algoritmo

Si un algoritmo tiene un tiempo de ejecución de n ^ 3 + n ^ 2 + n + 5, entonces es O (n ^ 3) Las potencias más bajas no importan aquí porque n -> Inf, n ^ 2 será irrelevante en comparación con n ^ 3

Del mismo modo, como n -> Inf, O (1 / n) será irrelevante en comparación con O (1), por lo que 3 + O (1 / n) será igual que O (1), lo que hace que O (1) sea el menor valor computacional posible. complejidad

No puede ir por debajo de O (1), sin embargo, O (k) donde k es menor que N es posible. Los llamamos algoritmos de tiempo sublineal . En algunos problemas, el algoritmo de tiempo sublineal solo puede dar soluciones aproximadas a un problema particular. Sin embargo, a veces, una solución aproximada está bien, probablemente porque el conjunto de datos es demasiado grande, o porque es demasiado costoso computacionalmente para computarlo todo.

No sé acerca de los algoritmos, pero las complejidades menores que O (1) aparecen en los algoritmos aleatorios. En realidad, o (1) (poco o) es menor que O (1). Este tipo de complejidad usualmente aparece en algoritmos aleatorios. Por ejemplo, como usted dijo, cuando la probabilidad de algún evento es de orden 1 / n, lo denotan con o (1). O cuando quieren decir que algo sucede con alta probabilidad (por ejemplo, 1 - 1 / n) lo denotan con 1 - o (1).

No, esto no es posible:

Como n tiende a infinito en 1 / n, eventualmente logramos 1 / (inf), que es efectivamente 0.

Por lo tanto, la clase grande-oh del problema sería O (0) con una n masiva, pero más cerca del tiempo constante con una n baja. Esto no es sensato, ya que lo único que se puede hacer más rápido que el tiempo constante es:

void nothing() {};

¡E incluso esto es discutible!

Tan pronto como ejecutas un comando, estás en al menos O (1), así que no, ¡no podemos tener una clase grande oh de O (1 / n)!

O (1 / n) no es menos que O (1), básicamente significa que cuantos más datos tenga, más rápido será el algoritmo. Digamos que obtienes una matriz y siempre la rellenas con un máximo de 10 100 elementos si tiene menos que eso y no haces nada si hay más. Este no es O (1 / n), por supuesto, sino algo como O (-n) :) Una notación O-big demasiado mala no permite valores negativos.

O (1) simplemente significa "tiempo constante".

Cuando agrega una salida temprana a un bucle [1], (en notación de gran O) está convirtiendo un algoritmo O (1) en O (n), pero haciéndolo más rápido.

El truco es que, en general, el algoritmo de tiempo constante es el mejor, y lineal es mejor que exponencial, pero para pequeñas cantidades de n, el algoritmo exponencial podría ser más rápido.

1: Suponiendo una longitud de lista estática para este ejemplo

OK, lo pensé un poco, y quizás exista un algoritmo que podría seguir esta forma general:

Debe calcular el problema del vendedor viajero para un gráfico de 1000 nodos, sin embargo, también se le proporciona una lista de nodos que no puede visitar. A medida que la lista de nodos invisibles crece, el problema se vuelve más fácil de resolver.

Para cualquier persona que lea esta pregunta y quiera entender de qué se trata la conversación, esto podría ayudar:

| |constant |logarithmic |linear| N-log-N |quadratic| cubic | exponential | | n | O(1) | O(log n) | O(n) |O(n log n)| O(n^2) | O(n^3) | O(2^n) | | 1 | 1 | 1 | 1| 1| 1| 1 | 2 | | 2 | 1 | 1 | 2| 2| 4| 8 | 4 | | 4 | 1 | 2 | 4| 8| 16| 64 | 16 | | 8 | 1 | 3 | 8| 24| 64| 512 | 256 | | 16 | 1 | 4 | 16| 64| 256| 4,096 | 65536 | | 32 | 1 | 5 | 32| 160| 1,024| 32,768 | 4,294,967,296 | | 64 | 1 | 6 | 64| 384| 4,069| 262,144 | 1.8 x 10^19 |

Puede ser posible construir un algoritmo que sea O (1 / n). Un ejemplo sería un bucle que itera algunos múltiplos de f (n) -n veces donde f (n) es una función cuyo valor se garantiza que es mayor que n y el límite de f (n) -n cuando n se acerca al infinito cero. El cálculo de f (n) también debería ser constante para todos los n. No sé de antemano cómo se vería f (n) o qué aplicación tendría tal algoritmo, en mi opinión, sin embargo, tal función podría existir, pero el algoritmo resultante no tendría otro propósito que probar la posibilidad de un algoritmo con O (1 / n).

Sí.

Existe precisamente un algoritmo con tiempo de ejecución O (1 / n), el algoritmo "vacío".

Para que un algoritmo sea O (1 / n) significa que se ejecuta asintóticamente en menos pasos que el algoritmo que consiste en una sola instrucción. Si se ejecuta en menos pasos que un paso para todos n> n0, debe consistir precisamente en ninguna instrucción en absoluto para esos n. Dado que verificar ''si n> n0'' cuesta al menos 1 instrucción, no debe contener ninguna instrucción para todo n.

Resumiendo: El único algoritmo que es O (1 / n) es el algoritmo vacío, que consiste en ninguna instrucción.

Si existe una solución, puede prepararse y accederse en tiempo constante = inmediatamente. Por ejemplo, utilizando una estructura de datos LIFO si sabe que la consulta de clasificación es para orden inverso. Entonces los datos ya están ordenados, dado que se eligió el modelo apropiado (LIFO).

Si la respuesta es la misma independientemente de los datos de entrada, entonces tiene un algoritmo O (0).

o en otras palabras, la respuesta se conoce antes de enviar los datos de entrada, la función podría optimizarse, por lo que O (0)

Veo un algoritmo que es O (1 / n) admitidamente a un límite superior:

Tiene una gran serie de entradas que están cambiando debido a algo externo a la rutina (tal vez reflejan hardware o incluso podría haber algún otro núcleo en el procesador que lo haga) y debe seleccionar uno aleatorio pero válido.

Ahora, si no estuviera cambiando, simplemente haría una lista de elementos, elija uno al azar y obtenga O (1) vez. Sin embargo, la naturaleza dinámica de los datos impide hacer una lista, simplemente debe realizar una prueba aleatoria y probar la validez de la sonda. (Y tenga en cuenta que, inherentemente, no hay garantía de que la respuesta siga siendo válida cuando se devuelva. Esto todavía podría tener usos, por ejemplo, la IA de una unidad en un juego. Podría disparar a un objetivo que se perdió de vista mientras estaba apretando el gatillo)

Esto tiene el peor desempeño de infinito, pero el rendimiento promedio de un caso disminuye a medida que el espacio de datos se llena.

muchas personas han tenido la respuesta correcta (No). Esta es otra forma de demostrarlo: para tener una función, debe llamar a la función y debe responderla. Esto lleva una cierta cantidad constante de tiempo. Incluso si el resto del procesamiento tomó menos tiempo para las entradas más grandes, la impresión de la respuesta (que podemos suponer que es un solo bit) toma al menos un tiempo constante.

sharptooth es correcto, O (1) es el mejor rendimiento posible. Sin embargo, no implica una solución rápida, solo una solución de tiempo fijo.

Una variante interesante, y quizás lo que realmente se sugiere, es qué problemas se vuelven más fáciles a medida que la población crece. Puedo pensar en 1, aunque sea una respuesta falsa y falsa:

¿Alguna de las dos personas en un set tiene el mismo cumpleaños? Cuando n supera 365, devuelve verdadero. Aunque por menos de 365, esto es O (n ln n). Quizás no sea una buena respuesta ya que el problema no se vuelve más fácil sino que se convierte en O (1) para n> 365.

Aquí hay un algoritmo simple O (1 / n). ¡Y hasta hace algo interesante!

function foo(list input) { int m; double output; m = (1/ input.size) * max_value; output = 0; for (int i = 0; i < m; i++) output+= random(0,1); return output; }

O (1 / n) es posible ya que describe cómo cambia la salida de una función dado el aumento en el tamaño de la entrada. Si estamos utilizando la función 1 / n para describir el número de instrucciones que una función ejecuta, no hay ningún requisito de que la función tome cero instrucciones para cualquier tamaño de entrada. Más bien, es que para cada tamaño de entrada, n por encima de algún umbral, el número de instrucciones requeridas está limitado por una constante positiva multiplicada por 1 / n. Como no hay un número real para el cual 1 / n es 0, y la constante es positiva, entonces no hay razón por la cual la función se vea obligada a tomar 0 o menos instrucciones.

inline void O0Algorithm() {}