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

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

¿O algo más que sea menor que O (1)?

Esta pregunta no es tan estúpida como parece. Al menos teóricamente, algo como O (1 / n ) es completamente sensible 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 algunas f .

Con el propósito de estimar el crecimiento asintótico en 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, puede 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 gasta menos tiempo a medida que crece el tamaño de entrada ... al menos hasta cierto límite, impuesto por el hardware (precisión de los números, tiempo mínimo que sleeppuede esperar, tiempo para procesar argumentos, etc.): este límite sería entonces un límite inferior constante, de modo que la función anterior todavía tiene tiempo de ejecución O (1).

Pero , de hecho, existen algoritmos del mundo real en los que el tiempo de ejecución puede disminuir (al menos parcialmente) cuando aumenta el tamaño de entrada. Sin embargo, tenga en cuenta que estos algoritmos no exhibirán un comportamiento de tiempo de ejecución inferior a O (1). 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 duración del patrón de búsqueda (pero aumentar la duración del pajar volverá a aumentar el tiempo de ejecución).

Si.

Precisamente hay 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 de un paso para todos n> n0, debe consistir precisamente en ninguna instrucción para esos n. Dado que verificar 'si n> n0' cuesta al menos 1 instrucción, no debe consistir en ninguna instrucción para todo n.

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

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 artificial y con una respuesta irónica:

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

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

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

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

Entonces, si necesita incluso 1 paso, eso es O (1) ... y dado que su programa al menos necesita 1 paso, lo 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, es O (1), y eso es lo mínimo que puede llegar.

(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) tiempo!
jefe : no hay necesidad de hacerlo, estamos en bancarrota esta mañana.
programador : oh, entonces, se convierte en O (0).

No, esto no es posible:

Como n tiende al infinito en 1 / n, finalmente alcanzamos 1 / (inf), que es efectivamente 0.

Por lo tanto, la clase big-oh del problema sería O (0) con un n masivo, pero más cercano al tiempo constante con un n bajo. Esto no es sensato, ya que lo único que se puede hacer más rápido que el tiempo constante es:

void nothing() {};

¡Y hasta 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 de O (1 / n)!

¿Qué pasa con no ejecutar la función en absoluto (NOOP)? o usando un valor fijo. ¿Eso cuenta?

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

O (1) simplemente significa "tiempo constante".

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

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

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

Para cualquiera 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 |

Creo que los algoritmos cuánticos pueden hacer múltiples cálculos "a la vez" mediante superposición ...

Dudo que esta sea una respuesta útil.

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

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

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

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 sublineales . 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 calcularlo todo.

¿Qué hay de esto?

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

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

O (1 / n) no es menor 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 llenas hasta 10 ¹⁰⁰ elementos si tiene menos de eso y no haces nada si hay más. Este no es O (1 / n), por supuesto, sino algo como O (-n) :) Lástima que la notación O-big no permita valores negativos.

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

Por supuesto, hay algunos algoritmos, como el definido por Konrad, que parece que deberían ser menores que O(1)al menos en cierto 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 "gratuitas" 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 haya mejores ejemplos, ya que el comportamiento asintótico es trivial. De hecho, estoy seguro de que alguien puede encontrar sentidos que dan resultados no triviales.

La mayoría del resto de las respuestas interpretan que big-O es exclusivamente sobre el 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 trata sobre el error.

Muchos algoritmos pueden ser O (h ^ p) u O (n ^ {- p}) dependiendo de si se trata 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 (la derivada de y). Su estimación de y (h) es más precisa cuanto más cerca esté h de 0. Entonces, para encontrar y (x) para alguna x arbitraria, uno toma el intervalo de 0 a x, lo divide hasta n piezas y ejecuta el método de Euler en cada punto, para pasar 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 generalmente se interpreta como un tamaño de paso yn se interpreta como el número de veces que divide un intervalo.

También puede tener O (1 / h) en aplicaciones de análisis numérico real, debido a errores de redondeo de coma flotante . Cuanto más pequeño sea su 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 error, que se propaga a través del algoritmo.

Para el método de Euler, si está utilizando puntos flotantes, utilice un paso y una 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 algoritmos que calculan la derivada restando 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) resultando en una gran cancelación y una estimación para la derivada 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 límite).

OK, lo pensé un poco, y tal vez exista un algoritmo que pueda seguir esta forma general:

Debe calcular el problema del vendedor ambulante 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 no visitables se hace más grande, el problema se vuelve más fácil de resolver.

Veo un algoritmo que es O (1 / n) ciertamente en 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 ser algún otro núcleo en el procesador que lo haga) y debe seleccionar una aleatoria pero válida.

Ahora, si no cambiara, simplemente haría una lista de elementos, elija uno al azar y obtenga O (1) tiempo. Sin embargo, la naturaleza dinámica de los datos impide hacer una lista, simplemente tiene que sondear aleatoriamente 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 para una unidad en un juego. Podría disparar a un objetivo que se perdió de vista mientras estaba apretando el gatillo)

Esto tiene un rendimiento de infinito en el peor de los casos, pero un rendimiento promedio de caso que disminuye a medida que se llena el espacio de datos.

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
    }
}

Supongo que menos de O (1) no es posible. Cualquier tiempo que tome algo se denomina O (1). Pero para O (1 / n), ¿qué tal la función a continuación? (Sé que hay muchas variantes ya presentadas en esta solución, pero supongo que todas tienen algunas fallas (no importantes, explican bien el concepto). Así que aquí hay una, solo por el argumento:

def 1_by_n(n, C = 10):   #n could be float. C could be any positive number
  if n <= 0.0:           #If input is actually 0, infinite loop.
    while True:
      sleep(1)           #or pass
    return               #This line is not needed and is unreachable
  delta = 0.0001
  itr = delta
  while delta < C/n:
    itr += delta

Así, a medida que n aumenta, la función tomará cada vez menos tiempo. También se garantiza que si la entrada en realidad es 0, la función tardará una eternidad en volver.

Se podría argumentar que estará limitado por la precisión de la máquina. así, porque tiene un límite superior es O (1). Pero también podemos omitir eso, tomando entradas de n y C en cadena. Y la suma y comparación se realiza en cadena. La idea es que con esto podemos reducir n arbitrariamente pequeño. Por lo tanto, el límite superior de la función no está limitado, incluso cuando ignoramos n = 0.

También creo que no podemos decir que el tiempo de ejecución es O (1 / n). Pero deberíamos decir algo como O (1 + 1 / n)

Es 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 alguna 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 es 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 un algoritmo de este tipo, sin embargo, en mi opinión, tal función podría existir, pero el algoritmo resultante no tendría otro propósito que demostrar la posibilidad de un algoritmo con O (1 / n).

No sé sobre algoritmos, pero las complejidades menores que O (1) aparecen en algoritmos aleatorios. En realidad, o (1) (pequeña o) es menor que O (1). Este tipo de complejidad generalmente aparece en algoritmos aleatorios. Por ejemplo, como dijiste, 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).

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)

La notación Big-O representa el peor de los casos para un algoritmo que no es lo mismo que su tiempo de ejecución típico. Es simple demostrar 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 inferiores no importan aquí en absoluto porque como n -> Inf, n ^ 2 será irrelevante en comparación con n ^ 3

Del mismo modo que n -> Inf, O (1 / n) será irrelevante en comparación con O (1), por lo tanto 3 + O (1 / n) será lo mismo que O (1), lo que hace que O (1) sea el cálculo computacional más pequeño posible complejidad

inline void O0Algorithm() {}

Aquí hay un algoritmo simple de 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 tamaño creciente de la entrada. Si estamos utilizando la función 1 / n para describir el número de instrucciones que ejecuta una función, entonces no hay 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 sea 0, y la constante sea positiva, entonces no hay razón por la cual la función se vea obligada a tomar 0 o menos instrucciones.