Funciones recursivas Establecer la ecuación de recurrencia: Complejidad en el caso base Complejidad en el caso recursivo Expandir la complejidad en el caso base en función del número de llamadas recursivas hechas Encontrar el número de llamadas necesarias para estar en el caso base
Ejemplo: Factorial Ecuación de recurrencia: T(n) = a, n = 0 T(n) = b + T(n-1), n > 0 Expandir en el caso recursivo:
Ejemplo: Factorial T(n) = kb + T(n-k) Para eliminar la dependencia de T(), escoger k tal que estamos en el caso base Si k=n, T(n-k) = T(0) = a Si substituimos k=n en la expresión, obtenemos T(n) = bn + a ¿Notación asintótica?
Ejemplo: Búsqueda binaria funcion BB(V:vector; i,d,k:natural) devuelve booleano si (i = d) entonces devuelve (V[i] = k); sino si (V[(i+d)/2] < k) entonces devuelve BB(V, (i+d)/2 + 1, d, k); sino devuelve BB(V, i, (i+d)/2, k); fsi ffuncion
Ejemplo: Búsqueda binaria Ecuación de recurrencia (medida n=d – i): T(n) = a, n = 0 T(n) = b + T(n/2), n > 0 Expandir en el caso recursivo:
Ejemplo: Búsqueda binaria T(n) = kb + T(n/2k) Para eliminar la dependencia de T(), escoger k tal que estamos en el caso base Problema: n/2k = 0 => 2k = ? Idea: escoger n/2k = 1 ? k = log(n) T(n) = b*log(n) + T(1) = b*log(n) + b + a ¿Notación asintótica?
Ejemplo: Mergesort Medida: n = D – E Depende de la complejidad de Combina Los bucles de Combina se repiten un número de veces igual al número total de elementos de V1 y V2 Ecuación de recurrencia: T(n) = a, n = 0 T(n) = b + c*n + 2T(n/2)
Ejemplo: Mergesort
n/2k = 1 ? k = log(n) T(n) = bn + cnlog(n) + an ¿Notación asintótica?
Un experimento Ordenar mil millones de elementos Procesador con frecuencia 1GHz Tiempo de ejecución aproximado Bubble (Insertion, Selection) Sort: O(n2) Mergesort: O(nlog(n)) log(109) ? 30 109 segundos ? ¡32 años!
Ejemplo: Quicksort Caso mejor: como Mergesort Caso peor: ¡como Bubble Sort! Caso promedio: como Mergesort
| Página siguiente |