¿Cómo determino el tiempo de ejecución de una función recursiva doble?

15

Dada cualquier función arbitrariamente doble recursiva, ¿cómo se calcularía su tiempo de ejecución?

Por ejemplo (en pseudocódigo):

int a(int x){
  if (x < = 0)
    return 1010;
  else
    return b(x-1) + a(x-1);
}
int b(int y){
  if (y <= -5)
    return -2;
  else
    return b(a(y-1));
}

O algo por el estilo.

¿Qué métodos podrían o deberían usarse para determinar algo como esto?

if_zero_equals_one
fuente
2
¿Es esta tarea?
Bernard
55
No, es verano y me gusta aprender. Me imagino adelantarme en lugar de dejar que mi cerebro se vuelva loco.
if_zero_equals_one
11
Ok, lo tengo. Para aquellos que votan para migrar esto a Stack Overflow: esto es sobre el tema aquí y fuera de tema en Stack Overflow. Programmers.SE es para preguntas conceptuales de pizarra blanca; Stack Overflow es para preguntas de implementación, problema mientras estoy codificando.
3
Gracias, esa es la razón por la que lo hice aquí en primer lugar. Además, es mejor saber pescar que recibir un pez.
if_zero_equals_one
1
En este caso particular, todavía es generalmente una recursión infinita porque b (a (0)) invoca infinitamente muchos otros términos b (a (0)). Hubiera sido diferente si fuera una fórmula matemática. Si su configuración hubiera sido diferente, habría funcionado de manera diferente. Al igual que en matemáticas, en cs algunos problemas tienen una solución, otros no, otros tienen una solución fácil, otros no. Hay muchos casos mutuamente recursivos donde la solución existe. A veces, para no volar una pila, uno tendría que usar un patrón de trampolín.
Trabajo

Respuestas:

11

Sigues cambiando tu función. Pero sigue eligiendo los que funcionarán para siempre sin conversión.

La recursión se complica, rápido. El primer paso para analizar una función doblemente recursiva propuesta es tratar de rastrearla en algunos valores de muestra, para ver qué hace. Si su cálculo entra en un bucle infinito, la función no está bien definida. Si su cálculo entra en una espiral que sigue obteniendo números más grandes (lo que sucede muy fácilmente), probablemente no esté bien definido.

Si rastrearlo da una respuesta, intente encontrar algún patrón o relación de recurrencia entre las respuestas. Una vez que tenga eso, puede intentar averiguar su tiempo de ejecución. Resolverlo puede ser muy, muy complicado, pero tenemos resultados como el teorema del Maestro que nos permite descubrir la respuesta en muchos casos.

Tenga en cuenta que incluso con una recursión simple, es fácil encontrar funciones cuyo tiempo de ejecución no sabemos cómo calcular. Por ejemplo, considere lo siguiente:

def recursive (n):
    if 0 == n%2:
        return 1 + recursive(n/2)
    elif 1 == n:
        return 0
    else:
        return recursive(3*n + 1)

Es actualmente se desconoce si siempre está bien definida esta función, por no hablar de lo que su tiempo de ejecución es.

btilly
fuente
5

El tiempo de ejecución de ese par particular de funciones es infinito porque ninguno regresa sin llamar al otro. El valor de retorno de aes siempre dependiente del valor de retorno de una llamada a bla que siempre se llama a... y eso es lo que se conoce como recursión infinita .

jimreed
fuente
No estoy buscando las funciones particulares aquí. Estoy buscando una forma general de encontrar el tiempo de ejecución de las funciones recursivas que se llaman entre sí.
if_zero_equals_one
1
No estoy seguro de que haya una solución en el caso general. Para que Big-O tenga sentido, debe saber si el algoritmo alguna vez se detendrá. Hay algunos algoritmos recursivos en los que debe ejecutar el cálculo antes de saber cuánto tiempo llevará (por ejemplo, determinar si un punto pertenece al conjunto Mandlebrot o no).
jimreed
No siempre, asolo llama bsi el número pasado es> = 0. Pero sí, hay un bucle infinito.
btilly
1
@btilly el ejemplo cambió después de que publiqué mi respuesta.
jimreed
1
@ jimreed: Y se ha cambiado nuevamente. Eliminaría mi comentario si pudiera.
btilly
4

El método obvio es ejecutar la función y medir cuánto tiempo lleva. Sin embargo, esto solo te dice cuánto tiempo lleva una entrada en particular. Y si no sabe de antemano que la función termina, difícil: no hay una forma mecánica de determinar si la función termina, ese es el problema de detención y es indecidible.

Encontrar el tiempo de ejecución de una función es igualmente indecidible, según el teorema de Rice . De hecho, el teorema de Rice muestra que incluso decidir si una función se ejecuta a O(f(n))tiempo es indecidible.

Entonces, lo mejor que puede hacer en general es usar su inteligencia humana (que, hasta donde sabemos, no está limitada por los límites de las máquinas de Turing) e intentar reconocer un patrón o inventar uno. Una forma típica de analizar el tiempo de ejecución de una función es convertir la definición recursiva de la función en una ecuación recursiva en su tiempo de ejecución (o un conjunto de ecuaciones para funciones recursivas mutuas):

T_a(x) = if x ≤ 0 then 1 else T_b(x-1) + T_a(x-1)
T_b(x) = if x ≤ -5 then 1 else T_b(T_a(x-1))

¿Qué sigue? Ahora tiene un problema matemático: necesita resolver estas ecuaciones funcionales. Un enfoque que a menudo funciona es convertir estas ecuaciones en funciones enteras en ecuaciones en funciones analíticas y usar el cálculo para resolverlas, interpretando las funciones T_ay T_bcomo funciones generadoras .

Sobre la generación de funciones y otros temas de matemática discreta, recomiendo el libro Matemáticas concretas , de Ronald Graham, Donald Knuth y Oren Patashnik.

Gilles 'SO- deja de ser malvado'
fuente
1

Como otros señalaron, analizar la recursividad puede ser muy difícil muy rápido. Aquí hay otro ejemplo de tal cosa: http://rosettacode.org/wiki/Mutual_recursion http://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences es difícil calcular una respuesta y un tiempo de ejecución para estos. Esto se debe a que estas funciones mutuamente recursivas tienen una "forma difícil".

De todos modos, veamos este sencillo ejemplo:

http://pramode.net/clojure/2010/05/08/clojure-trampoline/

(declare funa funb)
(defn funa [n]
  (if (= n 0)
    0
    (funb (dec n))))
(defn funb [n]
  (if (= n 0)
    0
    (funa (dec n))))

Comencemos tratando de calcular funa(m), m > 0:

funa(m) = funb(m - 1) = funa(m - 2) = ... funa(0) or funb(0) = 0 either way.

El tiempo de ejecución es:

R(funa(m)) = 1 + R(funb(m - 1)) = 2 + R(funa(m - 2)) = ... m + R(funa(0)) or m + R(funb(0)) = m + 1 steps either way

Ahora escojamos otro ejemplo un poco más complicado:

Inspirado por http://planetmath.org/encyclopedia/MutualRecursion.html , que es una buena lectura en sí misma, echemos un vistazo a: "" "Los números de Fibonacci se pueden interpretar mediante recursión mutua: F (0) = 1 y G (0 ) = 1, con F (n + 1) = F (n) + G (n) y G (n + 1) = F (n). "" "

Entonces, ¿cuál es el tiempo de ejecución de F? Nosotros iremos por el otro lado.
Bueno, R (F (0)) = 1 = F (0); R (G (0)) = 1 = G (0)
Ahora R (F (1)) = R (F (0)) + R (G (0)) = F (0) + G (0) = F (1)
...
No es difícil ver que R (F (m)) = F (m), por ejemplo, el número de llamadas a funciones necesarias para calcular un número de Fibonacci en el índice i es igual al valor de un número de Fibonacci en el índice i. Esto supone que sumar dos números juntos es mucho más rápido que una llamada a función. Si este no fuera el caso, entonces esto sería cierto: R (F (1)) = R (F (0)) + 1 + R (G (0)), y el análisis de esto habría sido más complicado, posiblemente sin una solución fácil de forma cerrada.

La forma cerrada para la secuencia de Fibonacci no es necesariamente fácil de reinventar, sin mencionar algunos ejemplos más complicados.

Trabajo
fuente
0

Lo primero que debe hacer es mostrar que las funciones que ha definido terminan y para qué valores exactamente. En el ejemplo que has definido

int a(int x){
  if (x < = 0)
    return 1010;
  else
    return b(x-1) + a(x-1);
}
int b(int y){
  if (y <= -5)
    return -2;
  else
    return b(a(y-1));
}

bsolo termina y <= -5porque si inserta cualquier otro valor, tendrá un término del formulario b(a(y-1)). Si se expande un poco más, verá que un término del formulario b(a(y-1))eventualmente conduce al término b(1010)que conduce a un término b(a(1009))que nuevamente conduce al término b(1010). Esto significa que no puede conectar ningún valor aque no satisfaga x <= -4porque si lo hace, terminará con un bucle infinito en el que el valor a calcular depende del valor a calcular. Entonces, esencialmente este ejemplo tiene un tiempo de ejecución constante.

Entonces, la respuesta simple es que no existe un método general para determinar el tiempo de ejecución de las funciones recursivas porque no existe un procedimiento general que determine si una función definida recursivamente termina.

davidk01
fuente
-5

Tiempo de ejecución como en Big-O?

Eso es fácil: O (N) , suponiendo que hay una condición de terminación.

La recursión es solo un bucle, y un bucle simple es O (N) sin importar cuántas cosas haga en ese bucle (y llamar a otro método es solo otro paso en el bucle).

Lo interesante sería si tienes un bucle dentro de uno o más de los métodos recursivos. En ese caso, terminaría con algún tipo de rendimiento exponencial (multiplicando por O (N) en cada pasada a través del método).

Luego
fuente
2
Usted determina el rendimiento de Big-O tomando el orden más alto de cualquier método llamado y multiplicándolo por el orden del método de llamada. Sin embargo, una vez que comience a hablar sobre el rendimiento exponencial y factorial, puede ignorar el rendimiento polinómico. Yo creo que lo mismo cuando se comparan exponenciales y factoriales: victorias factorial. Nunca he tenido que analizar un sistema que era tanto exponencial y factorial.
Anon
55
Esto es incorrecto. Las formas recursivas de calcular el enésimo número de Fibonacci y la clasificación rápida son O(2^n)y O(n*log(n)), respectivamente.
antipático el
1
Sin hacer una prueba sofisticada, me gustaría dirigirlo a amazon.com/Introduction-Algorithms-Second-Thomas-Cormen/dp/… e intente visitar este sitio de SE cstheory.stackexchange.com .
Bryan Harrington
44
¿Por qué la gente votó esta respuesta horriblemente incorrecta? Llamar a un método lleva un tiempo proporcional al tiempo que lleva ese método. En este caso, el método allama by bllama, apor lo que no puede simplemente asumir que cualquiera de los métodos lleva tiempo O(1).
btilly
2
@Anon: el póster pedía una función arbitrariamente doble recursiva, no solo la que se muestra arriba. Di dos ejemplos de recursión simple que no se ajustan a su explicación. Es trivial convertir los viejos estándares en una forma "doble recursiva", una que fue exponencial (que se ajusta a su advertencia) y otra que no está (no cubierta).
antipático el