java - resueltos - complejidad de algoritmos recursivos

Complejidades de 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 complejidades en tiempo de ejecución y notación Big-O en mi clase Algorithms, y tengo problemas para analizar 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 la cantidad de llamadas a métodos recursivos dependerá de la cantidad de nodos en DList, pero todavía no me siento cómodo con esta respuesta

No estoy seguro de si debo considerar la adición de d y d.getNext() .

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

Answer 1

A primera vista, esto parece un caso clásico de contras de módulo de recursividad de cola , una generalización de llamada de cola. Es equivalente a un bucle con el número de iteraciones.

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

Answer 2

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 3

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 lleva un tiempo constante C y suponiendo que el caso base no funciona, sería:

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

A continuación, puede resolver el tiempo de ejecución mediante sustitución para encontrar una serie:

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

Por 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 4

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 ejecuta 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.

Answer 5

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 internas se ejecuta a lo sumo una vez y todo excepto el segundo retorno no es O (1)) ejecutado por llamando a StringRec en una lista de n elementos, luego

  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).