computer science - traduccion - ¿Qué implica "en tiempo constante"?
definition of hardware (8)
Trabajo como programador, pero no tengo experiencia en informática, por lo que recientemente he estado siguiendo la excelente introducción de MIT OpenCourseWare a Informática y Programación. En el curso de lo cual, se hace la pregunta: "¿se ejecutará algún programa escrito utilizando solo definiciones de funciones y llamadas, los operadores aritméticos básicos, la asignación y los condicionales en tiempo constante?
Pensé que la respuesta era sí, ya que todas estas operaciones parecen bastante simples. Pero como probablemente ya sabían, las personas inteligentes ya sabían que la respuesta correcta era no, aparentemente debido a la posibilidad de una recursión indefinida.
Parece que simplemente no entiendo las implicaciones de "en tiempo constante". La forma en que imaginé el significado, parecía que solo significaba que una simple operación tomaría una cantidad de tiempo conocida para completar. Acepto que la recursión puede hacer que su programa se ejecute para siempre, pero ¿no están las operaciones individuales tomando una cantidad de tiempo finita y mensurable cada ... incluso si ahora hay un número infinito de ellas? ¿O simplemente la respuesta significa que no se puede decir válidamente que dos programas infinitamente recursivos tardan la misma cantidad de tiempo en ejecutarse?
Si alguien me puede dar una definición autorizada de "en tiempo constante" y sus implicaciones, ¡estaría muy agradecido!
"En tiempo constante" significa que no importa cuál sea la entrada, el programa no se ejecutará por más de una cantidad de tiempo conocida.
Considere la función factorial como un contraejemplo. El factorial de, digamos, 5 se calcula como:
5! = 5 * 4 * 3 * 2 * 1 = 120
Esto obviamente tomará menos tiempo para calcular que el factorial de 10 porque para hacer esto último, el programa tiene que hacer cinco multiplicaciones más:
10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
Por lo tanto, "tiempo constante" no significa que sepamos cuánto tiempo se ejecutará el programa en cada caso, sino que nunca se ejecutará más tiempo que una cantidad de tiempo conocida (el límite superior).
"Tiempo constante" significa que la operación se ejecutará en una cantidad de tiempo (o espacio de memoria, que es otra cosa que se mide a menudo) independientemente del tamaño de entrada. Por lo general, se elige una variable (usemos n ) para indicar el tamaño de entrada.
O(1) - tiempo constante - el tiempo de ejecución no depende de n
O(n) : tiempo lineal: el tiempo de ejecución es linealmente proporcional a n
O(n^2) - tiempo cuadrático - el tiempo de ejecución es proporcional al cuadrado de n
Estos son solo algunos ejemplos; Las posibilidades son infinitas. Ver el artículo wiki sobre la complexity
Aquí hay algunas formas específicas en que un programa compuesto solo por las operaciones que usted menciona puede tomar varias cantidades de tiempo:
int n = // some value
doSomething
doSomething
doSomething
Tenga en cuenta cómo es de tres a lo largo de la longitud, independientemente de lo que n es. O(1)
int n = // some value
def f(n):
if n == 0 return
doSomething
f(n-1)
f(n)
Ahora ejecutamos algo para cada valor 0..n (tiempo lineal, O(n) )
Y podemos divertirnos un poco -
int n = //some value
def f(n):
if n == 0 return
doSomething
f(n-1)
f(n-1)
¿Cuál es el tiempo de ejecución aquí? (Es decir, ¿cuántos años ejecutamos?) :)
"Tiempo constante" tiene el mismo significado que "O (1)", lo que no significa que un algoritmo se ejecute en una cantidad de tiempo fija, simplemente significa que no es proporcional a la longitud / tamaño / magnitud de la entrada. es decir, para cualquier entrada, se puede calcular en la misma cantidad de tiempo (incluso si esa cantidad de tiempo es realmente larga).
El tiempo constante aquí significa que no depende del número de entradas (no de la entrada en sí), y si no está permitido para o ir a, la única manera de hacerlo dependerá de la cantidad de entradas es por condicionales y recursión. Aunque se podría argumentar que la recursión no es necesaria con algunas soluciones discutibles. P.ej. (Cía)
if(ReadInput()) DoSomeThing();
if(ReadInput()) DoSomeThing();
if(ReadInput()) DoSomeThing();
if(ReadInput()) DoSomeThing();
El tiempo constante de manera efectiva significa que puede dar un límite superior constante al tiempo que tardará en ejecutarse el programa, lo que no se verá afectado por ninguno de los parámetros de entrada.
Compare eso con, digamos, el tiempo lineal (para algunas entradas n , que a menudo será el tamaño de los datos de entrada en lugar de un valor directo), lo que significa que el límite superior del tiempo tomado se puede expresar como mn + k para Algunos valores de m k .
Tenga en cuenta que no significa que un programa tomará la misma cantidad de tiempo para los datos de entrada simplemente porque se ejecuta en tiempo constante. Por ejemplo, considere este método:
int foo(int n)
{
if (n == 0)
{
return 0;
}
int j = n + 1;
int k = j * 2;
return k;
}
Eso es hacer más trabajo en el caso de que n sea distinto de cero que en el caso de que sea cero. Sin embargo, aún es tiempo constante; a lo sumo , va a hacer una comparación, una suma y una multiplicación.
Ahora compare eso con una función recursiva:
public int foo(int n)
{
if (n <= 1)
{
return 1;
}
return n * foo(n - 1);
}
Esto se repetirá n veces, por lo que es lineal en n . Sin embargo, puede ser mucho peor que lineal. Considere este método para calcular un número de Fibonacci:
public int fib(int n)
{
if (n == 0)
{
return 0;
}
if (n == 1)
{
return 1;
}
return fib(n - 2) + fib(n - 1);
}
Eso no se ve mucho peor que la versión anterior, pero ahora es exponencial (el límite superior se expresa más fácilmente en términos de O (2 n ). Sin embargo, solo usa comparaciones simples, sumas y llamadas a funciones.
En "tiempo constante" generalmente significa que el tiempo que tomará calcular el resultado es independiente del tamaño de la entrada.
Por ejemplo. El cálculo de la longitud de una lista / vector en la mayoría de los idiomas administrados se realiza en un tiempo constante sin importar qué tan grande sea la lista. El tamaño se almacena como un campo separado y se actualiza a medida que la lista crece y se reduce. Pero calcular el conteo es tan simple como leer el campo.
El cálculo del tamaño de una lista doblemente vinculada no suele ser un tiempo constante. La lista a menudo se puede mutar en ambos extremos y, por lo tanto, no hay un lugar central para almacenar un recuento. Por lo tanto, determinar la longitud de la lista requiere visitarla y determinar cuántos elementos hay allí. Entonces, a medida que la lista crece, también lo hace el tiempo que lleva calcular la respuesta.
Lo realmente importante a considerar es cómo el tiempo se escala en función del número de elementos. En tiempo constante significa que el tiempo sigue siendo el mismo sin importar cuántos elementos estén involucrados (explicación del laico).
Si el programa se ejecuta para siempre, entonces no se completa en una cantidad de tiempo conocida, porque no se completa. Estamos aplicando el concepto de "tiempo constante" a la ejecución de todo el programa, no a cada paso individual.
"tiempo constante" significa "tiempo que no depende de la cantidad de entrada".