Considere una lista de algoritmos recursivos y una lista de relaciones de recurrencia como se muestra a continuación. Cada relación de recurrencia corresponde exactamente a un algoritmo y se utiliza para derivar la complejidad temporal del algoritmo.
| Algoritmo recursivo | Relación de recurrencia | ||
|---|---|---|---|
| PAGS. | Búsqueda binaria | YO. | T(n) = T(nk) + T(k) + cn |
| q | Ordenar por fusión | II. | T(n) = 2T(n-1) + 1 |
| r | Ordenación rápida | tercero | T(n) = 2T(n/2) + cn |
| S. | Torre de Hanoi | IV. | T(n) = T(n/2) + 1 |
(A) P-II, Q-III, R-IV, SI
(B) P-IV, Q-III, RI, S-II
(C) P-III, Q-II, R-IV, SI
(D ) P-IV, Q-II, RI, S-III
Respuesta: (B)
Explicación: Estos son ejemplos de algunos algoritmos estándar cuyo
Merge Sort : T(n) = 2T(n/2) + Θ(n). Cae en el caso 2 ya que c es 1 y Log b a] también es 1 y la solución es Θ(n Logn) //la complejidad del tiempo se puede evaluar usando el método maestro
Búsqueda binaria : T(n) = T(n/2) + Θ(1). También cae en el caso 2 ya que c es 0 y Log b a también es 0 y la solución es Θ(Logn) //la complejidad del tiempo se puede evaluar usando el método maestro
Clasificación rápida : el tiempo que tarda QuickSort en general se puede escribir como T (n) = T (k) + T (nk-1) + 
(n)
Torre de Hanoi : T(n) = 2T(n-1) + 1
Lea más en: https://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solution-recurrences/
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA