¿Existe algún algoritmo O (1/n)?
¿Existe algún algoritmo O (1/n)?
¿O cualquier otra cosa que sea menor que O(1)?
Esta pregunta no es tan tonta como podría parecerles a algunos. Al menos teóricamente, algo como O (1/ n ) es completamente sensato cuando tomamos la definición matemática de la notación O grande :
Ahora puedes sustituir fácilmente g ( x ) por 1/ x ... es obvio que la definición anterior todavía es válida para algunas f .
A los efectos de estimar el crecimiento asintótico en tiempo de ejecución, esto es menos viable... un algoritmo significativo no puede volverse 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 emplea menos tiempo a medida que crece el tamaño de la entrada... al menos hasta algún 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, por lo que, de hecho, 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 mostrarán un comportamiento de tiempo de ejecución inferior a O (1). Aun así, son interesantes. Por ejemplo, tomemos 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 longitud del pajar aumentará una vez más el tiempo de ejecución).
Sí.
Existe precisamente un algoritmo con tiempo de ejecución O(1/n), el algoritmo "vacío".
Que un algoritmo sea O(1/n) significa que se ejecuta asintóticamente en menos pasos que el algoritmo que consta de una sola instrucción. Si se ejecuta en menos pasos que un paso para todo n > n0, no 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 todos los n.
Resumiendo: El único algoritmo que es O(1/n) es el algoritmo vacío, que no consta de ninguna instrucción.
Jun 11 '2009 17:06
Sharptooth es correcto, O (1) es el mejor rendimiento posible. Sin embargo, no implica una solución rápida, sólo una solución en un tiempo fijo.
Una variante interesante, y quizás la que realmente se sugiere, es qué problemas se vuelven más fáciles a medida que crece la población. Se me ocurre una respuesta, aunque artificial e irónica:
¿Dos personas en un set tienen el mismo cumpleaños? Cuando n excede 365, devuelve verdadero. Aunque para 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 simplemente se convierte en O(1) para n > 365.
