Big O of Recursive Methods

Question

Tengo dificultades para determinar la gran O de los métodos recursivos simples. No puedo entender lo que ocurre cuando se llama un método varias veces. Sería más específico acerca de mis áreas de confusión, pero en este momento estoy tratando de responder algunas preguntas, y en lugar de no querer hacer trampa, pido que cualquiera que responda a esta publicación presente un método recursivo simple y proporcionar una explicación simple de la gran O de dicho método. (Preferiblemente en Java ... un idioma que estoy aprendiendo.)

Gracias.

Answer 1

También puede definir el pedido recursivamente. Por ejemplo, digamos que tienes una función f. Para calcular f (n) se dan k pasos. Ahora quiere calcular f (n + 1). Digamos que f (n + 1) llama f (n) una vez, luego f (n + 1) toma k + algunos pasos constantes. Cada invocación dará algunos pasos constantes adicionales, por lo que este método es O (n).

Ahora mira otro ejemplo. Digamos que se implementa de Fibonacci ingenuamente mediante la adición de los dos resultados anteriores:

fib(n) = { return fib(n-1) + fib(n-2) } 

Ahora digamos que se puede calcular fib (n-2) y fib (n-1) tanto en aproximadamente k pasos. Para calcular fib (n) necesita k + k = 2 * k pasos. Ahora digamos que quiere calcular fib (n + 1). Entonces, necesitas el doble de pasos que para fib (n-1). Así que esto parece ser O (2^N)

Es cierto que esto no es muy formal, pero espero que de esta manera pueda sentirse un poco.

Answer 2

Es posible que desee consultar el teorema maestro para encontrar la gran O de métodos recursivos. Aquí está el artículo de Wikipedia: http://en.wikipedia.org/wiki/Master_theorem

Quiere pensar en un problema recursivo como en un árbol. Luego, considere cada nivel del árbol y la cantidad de trabajo requerido. Los problemas generalmente se clasificarán en 3 categorías, raíz pesada (primera iteración >> resto del árbol), equilibrada (cada nivel tiene la misma cantidad de trabajo), hoja pesada (última iteración >> resto del árbol).

Tomando ordenamiento por mezcla como un ejemplo:

define mergeSort(list toSort): 
    if(length of toSort <= 1): 
     return toSort 
    list left = toSort from [0, length of toSort/2) 
    list right = toSort from [length of toSort/2, length of toSort) 
    merge(mergeSort(left), mergeSort(right)) 

se puede ver que cada llamada de mergesort a su vez llama más mergeSorts 2 de 1/2 de la longitud original. Sabemos que el procedimiento de fusión llevará tiempo proporcional a la cantidad de valores fusionados.

La relación de recurrencia es entonces T (n) = 2 * T (n/2) + O (n). Los dos provienen de las 2 llamadas y el n/2 es de cada llamada que tiene solo la mitad del número de elementos. Sin embargo, en cada nivel hay la misma cantidad de elementos n que deben fusionarse, por lo que el trabajo constante en cada nivel es O (n).

Sabemos que el trabajo está distribuido uniformemente (O (n) cada profundidad) y el árbol es log_2 (n) profundo, por lo que la gran O de la función recursiva es O (n * log (n)).