Complejidades en tiempo de ejecución para algoritmos recursivos

Question

He buscado alto y bajo y no puedo encontrar mucho material relacionado con complejidades de tiempo de ejecución, recursividad y java.

Actualmente estoy aprendiendo las complejidades del tiempo de ejecución y la notación de Big-O en mi clase de Algoritmos, y tengo problemas para analizar los algoritmos recursivos.

private String toStringRec(DNode d) 
{ 
    if (d == trailer) 
     return ""; 
    else 
     return d.getElement() + toStringRec(d.getNext()); 
} 

Este es un método recursivo que simplemente iterará a través de una lista doblemente enlazada e imprimirá los elementos.

Lo único que se me ocurre es que tiene una complejidad en el tiempo de ejecución de O (n), ya que el número de llamadas a métodos recursivos dependerá de la cantidad de nodos en el DList, pero todavía no lo hago Me siento cómodo con esta respuesta.

No estoy seguro de si debería dar cuenta de la adición de d y d.getNext().

¿O estoy completamente desviado y la complejidad del tiempo de ejecución es constante, ya que todo lo que hace es recuperar elementos del DNodes en el DList?

Answer 1

El algoritmo tiene una complejidad de tiempo de ejecución de O (n) como usted sugiere. Su lista contiene n elementos, y el algoritmo hará una cantidad de trabajo casi fija para cada elemento (el trabajo será Elemento y Acceso siguiente, más una nueva llamada aStringRec). Recuperar un Elemento de un DNode toma tiempo constante, y los tiempos constantes se descartan en notación de O grande.

Lo interesante de los métodos recursivos (en la mayoría de los casos) es que también son O (n) en la complejidad del espacio. Se crea una nueva entrada de pila (para almacenar los parámetros pasados ​​al método) para cada llamada a toStringRec, que se llama n veces.

Answer 2

A primera vista, esto parece un caso clásico de tail recursion modulo cons, una generalización de la llamada de cola. Es equivalente a un bucle con el número de iteraciones.

Sin embargo, no es así de simple: lo difícil aquí es la adición de d.getElement() a una cadena en crecimiento: esto es en sí misma una operación lineal , y se repite N veces. Por lo tanto, la complejidad de su función es O(N^2).

Answer 3

Si T (n) es el número de operaciones elementales (en este caso, cuando ingresamos al cuerpo de la función, cualquiera de las líneas adentro se ejecuta a lo sumo y el segundo retorno no es O (1))) ejecutado por llamar toStringRec en una lista de n elementos, entonces

T(0) = 1 - as the only things that happen is the branch instruction and a 
       return 
    T(n) = n + T(n-1) for n > 0 - as the stuff which is being done in the 
       function besides calling toStringRec is some constant time stuff and 
       concatenating strings that takes O(n) time; and we also run 
       toStringRec(d.getNet()) which takes T(n-1) time 

en este punto hemos descrito la complejidad del algoritmo. Ahora podemos calcular la forma cerrada para T, T (n) = O (n ** 2).

Answer 4

Este es un ejemplo bastante simple, pero el truco es definir una relación de recurrencia, que es una función del tiempo de ejecución de un tamaño de entrada dado en términos de tamaños de entrada más pequeños.Para este ejemplo, suponiendo que el trabajo realizado en cada paso de toma constante de tiempo C y suponiendo que el caso base no realiza trabajo, sería:

T(0) = 0 
T(n) = C + T(n-1) 

Luego, puede resolver el tiempo de funcionamiento mediante la sustitución de encontrar una serie :

T(n) = C + T(n-1) = 2C + T(n-2) = 3C + T(n-3) = ... = nC + T(n-n) = nC + 0 = nC 

Según la definición de O, esta ecuación es O (n). Este ejemplo no es particularmente interesante, pero si observa algo como el tiempo de ejecución de mergesort u otro algoritmo de dividir y conquistar, puede obtener una mejor idea de las relaciones recurrentes.

Answer 5

Para tales algoritmos recursivos, generalmente es posible escribir una ecuación recursiva para calcular el orden. Es habitual mostrar la cantidad de instrucciones ejecutadas con T (n). En este ejemplo, tenemos:

T (n) = T (n - 1) + O (1)

(Suponiendo que la función getElement carreras en tiempo constante.) La solución de esta ecuación es trivialmente T (n) = O (n).

Ese fue el caso general. Sin embargo, a veces puede analizar el algoritmo sin escribir dicha ecuación. En este ejemplo, puede argumentar fácilmente que cada elemento se accede como máximo una vez, y cada vez que se realiza un trabajo de tiempo constante; por lo tanto, se necesita O (n) en general para hacer el trabajo.