¿Existe una prueba matemática para demostrar que no se pueden ejecutar algoritmos en [matemática] O \ left (\ frac {1} {n} \ right) [/ math]?

Answer 1

Tendemos a usar estos términos de manera flexible en la ingeniería del mundo real, pero hay un significado formal de n : el tamaño del parámetro de entrada del problema cuando se escribe en un alfabeto específico (a menudo, bits). La complejidad del tiempo debe medirse en relación con un modelo de cálculo (típicamente, una máquina de Turing). En el caso de la máquina de Turing, n sería el tamaño de la cuerda más pequeña que cubre las ranuras no nulas de la cinta y el punto de partida de la cabeza.

Para problemas no triviales, en realidad no puede ser más rápido que lineal (es decir, [matemática] O (n) [/ matemática]) en una máquina Turing, porque debe moverse por la cinta y leer toda la entrada, a menos que asuma que los movimientos inactivos (sin escribir o leer) son gratuitos. Entonces, cuando ve una complejidad de tiempo más rápida que la lineal, como [math] O (\ log n) [/ math] para, por ejemplo, acceder a una estructura de datos en forma de árbol, eso en realidad es asumir una máquina de Turing con acceso aleatorio a la cinta, lo que permite que la cabeza se mueva a la dirección de un puntero en tiempo [matemático] O (1) [/ matemático], que el modelo TM típico no permite. Estoy ignorando los problemas de caché y similares, y también, por supuesto, que las máquinas de Turing tienen una cinta infinita y ninguna máquina del mundo real.

Para ser justos con la Máquina de Turing, aunque parece que este movimiento [matemático] O (n) [/ matemático] lo hace “más débil” que una computadora del mundo real que tiene acceso aleatorio a toda su memoria; Si hablamos de comportamiento asintótico, necesitamos manejar tamaños arbitrarios, y los sistemas del mundo real solo tienen ese acceso aleatorio a una cantidad finita de cosas. Tratamos el acceso a la memoria como [math] O (1) [/ math] en una máquina del mundo real bajo el supuesto de que no nos toparemos con sus limitaciones.

Sin embargo, para responder a la pregunta: [matemática] O (\ frac1n) [/ matemática] significa que un problema tomaría pasos de tiempo cero (inicio detenido) para n suficientemente grande. En ese caso, no tendría tiempo para leer nada de la cinta, lo que significa que no sabría que n es grande, por lo que tiene que hacer eso (comenzar detenido) sin importar qué n sea. Eso significa que es el programa trivial de no hacer nada.

Answer 2

El comportamiento de las clases de complejidad asintótica es bastante patológico para funciones subconstantes. Si puede calcular cualquier cosa en el tiempo O (1 / n) depende de alguna manera del modelo: si asume, como lo hace Kevin Lin (y este es el caso con la mayoría de los modelos que conozco), cualquier algoritmo requiere al menos un paso para completar, entonces claramente no hay lenguaje en DTIME (1 / n) *. Por otro lado (y no he comprobado si esto tiene sentido en un contexto más amplio), si nuestro modelo dice que hay máquinas que se ejecutan en cero pasos (por ejemplo, una que comienza en un estado de aceptación), entonces hay idiomas en DTIME (0) (como el lenguaje universal, es decir, el lenguaje de todas las cadenas).

Tenga en cuenta que esto también depende de la definición precisa de DTIME: algunos autores introducen una constante en las restricciones de tiempo, es decir, DTIME (f (n)) es la clase de lenguajes que puede decidir una máquina de Turing determinista en el tiempo [matemáticas] c \ cdot f (n) + c [/ math] para alguna constante c. En esta definición, DTIME (1 / n) = DTIME (1).

En resumen: para todos los propósitos prácticos, la prueba de Kevin Lin es correcta, ¡pero si la afirmación original es verdadera o no depende de su modelo de cálculo!

* Según la definición más común, DTIME (f (n)) es la clase de lenguajes que puede decidir una máquina de Turing determinista en el tiempo O (f (n)).

Answer 3

Es fácil ver que es imposible que un algoritmo tenga una complejidad de tiempo O (1 / n) si suponemos que cualquier algoritmo debe tomar al menos un paso (inicialización, por ejemplo) que requiere un tiempo constante finito fijo, digamos k, para completar . Ser O (1 / n) complejidad de tiempo significa que hay una constante C tal que para un tamaño de entrada grande n, el tiempo de ejecución es C / n.