Considere el problema de calcular min-max en una array no ordenada donde min y max son elementos mínimos y máximos de la array. El algoritmo A1 puede calcular min-max en comparaciones a1 sin dividir y vencer. El algoritmo A2 puede calcular min-max en comparaciones a2 escaneando la array linealmente. ¿Cuál podría ser la relación entre a1 y a2 considerando los peores escenarios?
(A) a1 < a2
(B) a1 > a2
(C) a1 = a2
(D) Depende de la entrada
Respuesta: (B)
Explicación: cuando se usa Divide and Conquer para encontrar el elemento mínimo-máximo en una array, la relación de recurrencia para el número de comparaciones es
T(n) = 2T(n/2) + 2 donde 2 es para comparar los mínimos y los máximos de los subarreglos izquierdo y derecho
Al resolver, T(n) = 1.5n – 2.
Al realizar un escaneo lineal, se necesitarían 2*(n-1) comparaciones en el peor de los casos para encontrar tanto el mínimo como el máximo en una sola pasada.
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