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

335

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

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

Peter Mortensen
fuente
La mayoría de las preguntas suponen que quiere decir "¿Hay algún algoritmo con una complejidad temporal de O (1 / n)?" ¿Suponemos que este es el caso? Big-O (y Big-Theta, etc.) describen funciones, no algoritmos. (No sé de equivalencia entre funciones y algoritmos.)
jyoungdev
44
Esa es la definición comúnmente entendida de "algoritmo O (X)" en informática: un algoritmo cuya complejidad temporal es O (X) (para alguna expresión X).
David Z
2
He escuchado tal límite en el caso de un algoritmo de cola de prioridad eficiente de E / S usando Buffer Tree. En un Buffer Tree, cada operación toma O (1 / B) I / Os; donde B es el tamaño del bloque. Y las E / S totales para n operaciones son O (n / B.log (base M / B) (n / B)), donde la parte de registro es la altura del árbol de búfer.
CODError
Hay muchos algoritmos con probabilidad de error O (1 / n). Por ejemplo, un filtro de floración con cubos O (n log n).
Thomas Ahle
No puedes poner un huevo más rápido agregando pollos.
Wyck

Respuestas:

310

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

Konrad Rudolph
fuente
22
'Obligado por el hardware' también se aplica a una máquina de Turing. En el caso de O (1 / n) siempre habrá un tamaño de entrada para el cual no se supone que el algoritmo ejecute ninguna operación. Y por lo tanto, pensaría que la complejidad del tiempo O (1 / n) es realmente imposible de lograr.
Roland Ewald
28
Mehrdad, no lo entiendes. La notación O es algo acerca del límite (técnicamente limitado ) como n -> ∞. El tiempo de ejecución de un algoritmo / programa es el número de pasos en alguna máquina y, por lo tanto, es discreto: hay un límite inferior distinto de cero en el tiempo que puede tomar un algoritmo ("un paso"). Se es posible que hasta algunos finito N de un programa realiza una serie de medidas decrecientes con n, pero la única manera de un algoritmo puede ser O (1 / n), o de hecho o (1), es que si se necesita tiempo 0 para todos suficientemente n grande, que no es posible.
ShreevatsaR
28
No estamos en desacuerdo con la existencia de funciones O (1 / n) (en el sentido matemático). Obviamente lo hacen. Pero el cálculo es inherentemente discreto. Algo que tiene un límite inferior, como el tiempo de ejecución de un programa, ya sea en la arquitectura von Neumann o en una máquina de Turing puramente abstracta, no puede ser O (1 / n). De manera equivalente, algo que es O (1 / n) no puede tener un límite inferior. (Se debe invocar la función de "suspensión", o se debe examinar la variable "lista", o se debe examinar la cinta de entrada en una máquina Turing. Por lo tanto, el tiempo necesario cambiaría con n como algunos ε + 1 / n, que no es O (1 / n))
ShreevatsaR
16
Si T (0) = ∞, no se detiene. No existe tal cosa como "T (0) = ∞, pero aún se detiene". Además, incluso si trabaja en R∪ {∞} y define T (0) = ∞, y T (n + 1) = T (n) / 2, entonces T (n) = ∞ para todo n. Permítanme repetir: si una función de valor discreto es O (1 / n), entonces para todo lo suficientemente grande n es 0. [Prueba: T (n) = O (1 / n) significa que existe una constante c tal que para n> N0, T (n) <c (1 / n), lo que significa que para cualquier n> max (N0,1 / c), T (n) <1, lo que significa T (n) = 0.] Ninguna máquina, real o abstracta, puede tomar 0 tiempo: tiene que mirar la entrada. Bueno, además de la máquina que nunca hace nada, y para la cual T (n) = 0 para todo n.
ShreevatsaR
43
Le debe gustar cualquier respuesta que comience "Esta pregunta no es tan estúpida como podría parecer".
Telemachus
138

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.

Tobias
fuente
2
Entonces, si alguien pregunta cuál es la complejidad temporal de un algoritmo vacío, respondería con O (1 / n) ??? De alguna manera lo dudo.
phkahler
24
Esta es la única respuesta correcta en este hilo, y (a pesar de mi voto positivo) está en cero votos. Tal es StackOverflow, donde las respuestas de "aspecto correcto" se votan más alto que las respuestas correctas.
ShreevatsaR
55
No, tiene 0 porque es incorrecto. Expresar un valor grande de Oh en relación con N cuando es independiente de N es incorrecto. En segundo lugar, ejecutar cualquier programa, incluso uno que solo existe, requiere al menos una cantidad constante de tiempo, O (1). Incluso si ese no fuera el caso, sería O (0), no O (1 / n).
kenj0418
32
Cualquier función que sea O (0) también es O (1 / n), y también O (n), también O (n ^ 2), también O (2 ^ n). Suspiro, ¿nadie entiende definiciones simples? O () es un límite superior.
ShreevatsaR
16
@ kenj0418 Te las arreglaste para equivocarte en cada oración. "Expresar un valor grande de Oh en relación con N cuando es independiente de N es incorrecto". Una función constante es una función perfectamente tonta. "Segundo, ejecutar cualquier programa, incluso uno que solo existe, requiere al menos una cantidad constante de tiempo, O (1)". La definición de complejidad no dice nada sobre la ejecución real de ningún programa. "sería O (0), no O (1 / n)". Ver el comentario de @ ShreevatsaR.
Alexey Romanov
25

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.

Adrian
fuente
77
366. ¡No te olvides de los años bisiestos!
Nick Johnson
1
Estás en lo correcto. Al igual que las computadoras, ocasionalmente estoy sujeto a errores de redondeo :-)
Adrian
10
+1. Hay una serie de problemas NP-completos que se someten a una "transición de fase" a medida que aumenta n, es decir, rápidamente se vuelven mucho más fáciles o mucho más difíciles a medida que supera un cierto valor umbral de n. Un ejemplo es el problema de partición de números: dado un conjunto de n enteros no negativos, divídalos en dos partes para que la suma de cada parte sea igual. Esto se vuelve dramáticamente más fácil en un cierto valor umbral de n.
j_random_hacker
23

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

dientes afilados
fuente
42
Sospecho que esta respuesta es la "correcta", pero desafortunadamente no tengo el intelecto para entenderla.
espacio libre
12
AFAIK esta condición no tiene que ser verdadera para todos n, sino para todos n> n_0 (es decir, solo cuando el tamaño de la entrada alcanza un umbral específico).
Roland Ewald
30
No veo cómo la definición (incluso corregida) contradice la pregunta del OP. ¡La definición es válida para funciones completamente arbitrarias! 1 / n es una función completamente sensata para B, y de hecho su ecuación no contradice eso (solo haga las matemáticas). Entonces no, a pesar de mucho consenso, esta respuesta es de hecho incorrecta . Lo siento.
Konrad Rudolph
10
¡Incorrecto! No me gusta el voto negativo, pero usted afirma que esto es imposible cuando no hay un consenso claro. En la práctica tiene razón, si construye una función con tiempo de ejecución 1 / n (fácil), eventualmente alcanzará el tiempo mínimo, convirtiéndolo en un algoritmo O (1) cuando se implemente. Sin embargo, no hay nada que impida que el algoritmo sea O (1 / n) en papel.
jheriko
3
@Jason: Sí, ahora que lo dices ... :) @jheriko: Una complejidad de tiempo de O (1 / n) no funciona en papel en mi humilde opinión. Estamos caracterizando la función de crecimiento f (tamaño de entrada) = #ops para una máquina de Turing. Si se detiene para una entrada de longitud n = 1 después de x pasos, entonces elegiré un tamaño de entrada n >> x, es decir, lo suficientemente grande como para que, si el algoritmo está realmente en O (1 / n), no se debe realizar ninguna operación hecho. ¿Cómo debería notar esto una máquina de Turing (no se permite leer una vez de la cinta)?
Roland Ewald
16

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

動靜 能量
fuente
Su broma me recordó algo del Tao de la programación: canonical.org/~kragen/tao-of-programming.html#book8 (8.3)
kenj0418
Un algoritmo que consta de cero pasos es O (0). Ese es un algoritmo muy vago.
finalmente
8

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

Ed James
fuente
7

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

SpliFF
fuente
16
Eso sigue siendo O (1) tiempo de ejecución.
Konrad Rudolph
2
Bien, eso sigue siendo O (1). No veo cómo alguien puede entender esto y, sin embargo, afirmo en otra respuesta que es posible algo menos que NO-OP.
ShreevatsaR
44
ShreevatsaR: no hay absolutamente ninguna contradicción. Parece que no comprende que la notación O grande no tiene nada que ver con el tiempo dedicado a la función; más bien, describe cómo ese tiempo cambia con el cambio de entrada (por encima de un cierto valor). Ver otro hilo de comentarios para más.
Konrad Rudolph
Lo entiendo perfectamente bien, gracias. El punto, como lo hice varias veces en el otro hilo, es que si el tiempo disminuye con la entrada, a una velocidad O (1 / n), finalmente debe disminuir por debajo del tiempo que toma NOOP. Esto muestra que ningún algoritmo puede ser O (1 / n) asintóticamente, aunque ciertamente su tiempo de ejecución puede disminuir hasta un límite.
ShreevatsaR
1
Sí ... como dije en otra parte, cualquier algoritmo que sea O (1 / n) también debería tomar tiempo cero para todas las entradas, por lo tanto, dependiendo de si considera que el algoritmo nulo toma 0 tiempo o no, hay un O (1 / n) algoritmo. Entonces, si considera que NOOP es O (1), entonces no hay algoritmos O (1 / n).
ShreevatsaR
7

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

Dave
fuente
66
Sin embargo, eso no es lo que es el gran O. No puede simplemente redefinirlo para responder la pregunta.
Zifre
11
No es una redefinición, es exactamente la definición de gran O.
ShreevatsaR
10
Soy un informático teórico de oficio. Se trata del orden asintótico de una función.
Dave
44
Big O es una propiedad de una función real arbitraria. La complejidad del tiempo es solo una de sus posibles aplicaciones. La complejidad del espacio (la cantidad de memoria de trabajo que utiliza un algoritmo) es otra. Que la pregunta sea sobre algoritmos O (1 / n) implica que es uno de estos (a menos que haya otro que se aplique a algoritmos que no conozco). Otras aplicaciones incluyen órdenes de crecimiento de la población, por ejemplo, en Conway's Life. Ver también en.wikipedia.org/wiki/Big_O_notation
Stewart
55
@Dave: La pregunta no era si existen funciones O (1 / n), que obviamente existen. Más bien, era si existen O (1 / n) algoritmos, que (con la posible excepción de la función null) no puede existir
Casebash
6

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

LapTop006
fuente
6

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 |
Craig O'Connor
fuente
5

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.

Jeff Meatball Yang
fuente
Eso todavía habría tiempo constante, es decir, O (1), lo que significa que se necesita la misma cantidad de tiempo para correr para los datos de tamaño n como lo hace para los datos de tamaño 1.
freespace
2
Pero, ¿y si el problema fuera una pale ale? (ah. hah. ha.)
Jeff Meatball Yang
77
Sería una excelente posición para estar.
Daniel Earwicker
1
Los algoritmos cuánticos pueden hacer múltiples cálculos, pero solo puede recuperar el resultado de un cálculo, y no puede elegir qué resultado obtener. Afortunadamente, también puede realizar operaciones en un registro cuántico en su conjunto (por ejemplo, QFT), por lo que es mucho más probable que encuentre algo :)
Gracenotes
2
quizás no sea útil, pero tiene la ventaja de ser cierto, lo que lo coloca por encima de algunas de las respuestas más votadas B-)
Brian Postow
4

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.

Brian Postow
fuente
2

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

Larsson
fuente
2

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

Niklas R.
fuente
Sí, pero la cantidad de nodos bittorrent es más parecida a la cantidad de procesadores en una computadora paralela. La "N" en este caso sería el tamaño del archivo que intenta descargarse. Del mismo modo que podría encontrar un elemento en una matriz no clasificada de longitud N en tiempo constante si tuviera N computadoras, podría descargar un archivo de Tamaño N en tiempo constante si tuviera N computadoras tratando de enviarle los datos.
Kibbee
2

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.

Hao Wooi Lim
fuente
1
No estoy seguro si entiendo. Log (N) es menor que N. ¿Eso significa que Log (N) es un algoritmo sublineal? Y existen muchos algoritmos Log (N). Un ejemplo de esto es encontrar un valor en un árbol binario. Sin embargo, estos siguen siendo diferentes de 1 / N, ya que Log (N) siempre aumenta, mientras que 1 / n es una función decreciente.
Kibbee
En cuanto a la definición, el algoritmo de tiempo sublineal es cualquier algoritmo cuyo tiempo crece más lento que el tamaño N. De modo que incluye el algoritmo de tiempo logarítmico, que es Log (N).
Hao Wooi Lim
2
Uh, los algoritmos de tiempo sublineales pueden dar respuestas exactas, por ejemplo, búsqueda binaria en una matriz ordenada en una máquina RAM.
A. Rex
@UNA. Rex: Hao Wooi Lim dijo "En algunos problemas".
LarsH
1

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

Shalmanese
fuente
creo que no entiendes el significado de O (n)
Markus Lausberg
Sin embargo, no con la lista, con la matriz o el hash donde constainsestá O (1)
vava
ok, la función aleatoria puede considerarse como una matriz diferida, por lo que básicamente está buscando cada elemento en la "lista aleatoria diferida" y verificando si está contenido en la lista de entrada. Creo que esto es peor que lineal, no mejor.
hasen
Tiene algún punto si notas que int tiene un conjunto limitado de valores. Entonces, cuando contenga 2 valores <sup> 64 </sup>, será instantáneo todo el tiempo. Lo que lo hace peor que O (1) de todos modos :)
vava
1

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

vava
fuente
1
"O (1 / n) no es menor que O (1)" - si una función f es O (1 / n), también es O (1). Y big-oh se parece mucho a una relación "menor que": es reflexiva, es transitiva, y si tenemos simetría entre f y g, los dos son equivalentes, donde big-theta es nuestra relación de equivalencia. Sin embargo, las relaciones de pedido "reales" de ISTR que requieren a <= by b <= a implican a = b, y netcraft ^ W wikipedia lo confirma. Entonces, en cierto sentido, es justo decir que de hecho O (1 / n) es "menor que" O (1).
Jonas Kölker
1

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.

Casebash
fuente
1

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

Andrew Lei
fuente
0

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.

Shalmanese
fuente
44
Es diferente tipo de n en el O (n) entonces. Con este truco, se podría decir que cada algoritmo tiene O (q) donde q es el número de personas que viven en China, por ejemplo.
vava
2
Boyer-Moore es de un tipo similar (O (n / m)), pero eso no es realmente "mejor que O (1)", porque n> = m. Creo que lo mismo es cierto para su "TSP invisible".
Niki
Incluso en este caso, el tiempo de ejecución del TSP es NP-Complete, simplemente está eliminando nodos del gráfico y, por lo tanto, disminuyendo efectivamente n.
Ed James
0

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.

Loren Pechtel
fuente
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
    }
}
Sam Harwell
fuente
¿de verdad te refieres sub-constante o sublineal? ¿Por qué los algoritmos de aproximación deben ser sub-constantes? ¿Y qué significa eso?
LarsH
@LarsH, el error de los algoritmos de aproximación es proporcional al tamaño del paso (oa una potencia positiva del mismo), por lo que cuanto menor sea el tamaño de su paso, menor será el error. Pero otra forma común de examinar un problema de aproximación es el error en comparación con cuántas veces se divide un intervalo. El número de particiones de un intervalo es inversamente proporcional al tamaño del paso, por lo que el error es inversamente proporcional a alguna potencia positiva del número de particiones: a medida que aumenta el número de particiones, su error disminuye.
Andrew Lei
@AndrewLei: ¡Guau, una respuesta casi 7 años después! Entiendo la respuesta de Sam ahora mejor que yo entonces. Gracias por responder.
LarsH
0

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)

usuario1953366
fuente
-1

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

Greg
fuente
Su ciclo requiere una verificación que tome al menos un tiempo constante, por lo que el algoritmo resultante tiene al menos complejidad O (1).
Stefan Reich
-1

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

A. Mashreghi
fuente
-2

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)

pro
fuente
De Verdad? Aún necesitaría devolver un valor, ¿entonces no sería O (1)?
Joachim Sauer
77
no, O (0) implicaría que lleva tiempo cero para todas las entradas. O (1) es tiempo constante.
Pete Kirkham
-2

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)

Lawrence Barsanti
fuente
No: la notación Big O también se usa para hablar sobre el caso promedio y el tiempo esperado (e incluso el mejor de los casos). El resto sigue.
Konrad Rudolph
La notación 'O' ciertamente define un límite superior (en términos de complejidad algorítmica, este sería el peor de los casos). Omega y Theta se usan para denotar el mejor y el caso promedio, respectivamente.
Roland Ewald
2
Roland: Eso es un error; el límite superior no es lo mismo que en el peor de los casos, los dos son conceptos independientes. Considere el tiempo de ejecución esperado (y promedio) del hashtable-containsalgoritmo que se puede denotar como O (1), ¡y el peor de los casos se puede dar con mucha precisión como Theta (n)! Omega y Theta simplemente se pueden usar para denotar otros límites, pero para decirlo de nuevo : no tienen nada que ver con el promedio o el mejor caso.
Konrad Rudolph
Konrad: cierto. Aún así, Omega, Theata y O generalmente se usan para expresar límites, y si se consideran todas las entradas posibles, O representa el límite superior, etc.
Roland Ewald
1
El hecho de que O (1 / n) sea un subconjunto de O (1) es trivial y se deduce directamente de la definición. De hecho, si una función g es O (h), entonces cualquier función f que sea O (g) también es O (h).
Tobias
-2

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

usuario112831
fuente
-2
inline void O0Algorithm() {}
algo
fuente
1
Eso sería un algoritmo O (1).
Lasse V. Karlsen
2
Eso también, pero el punto es que no es Ω (1). ¿Y por qué mi respuesta ha sido rebajada? Si crees que estoy equivocado, ¿qué tal si lo explicas?
Stewart
Pregunté en otra parte si, básicamente, esta respuesta es correcta o no, y parece estar en disputa: stackoverflow.com/questions/3209139/…
jyoungdev
Bueno, está en línea, por lo que puede considerarlo O (0). Sin embargo, todos los algoritmos O (0) son triviales (no hacen nada), así que ... no es una respuesta muy interesante.
Stefan Reich
@StefanReich Cierto, no es una respuesta muy interesante, pero es una respuesta.
Stewart
-2

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.

ejspencer
fuente
1
Dado que O (1 / n) caerá debajo de la línea horizontal = 1, y cuando n llega al infinito, su código seguirá ejecutando un número dado de pasos, este algoritmo es un algoritmo O (1). La notación Big-O es una función de todas las diferentes partes del algoritmo, y elige la más grande. Dado que el método siempre ejecutará algunas de las instrucciones, cuando n llega al infinito, te quedarán esas mismas instrucciones ejecutándose cada vez, y así el método se ejecutará en tiempo constante. Por supuesto, no pasará mucho tiempo, pero eso no es relevante para la notación Big-O.
Lasse V. Karlsen