¿Cuál es la complejidad temporal en el peor de los casos de ordenación por inserción en la que la posición de los datos que se insertarán se calcula mediante la búsqueda binaria?
(A) N
(B) NlogN
(C) N^2
(D) N(logN)^2
Respuesta: (C)
Explicación: aplicar la búsqueda binaria para calcular la posición de los datos que se insertarán no reduce la complejidad del tiempo de tipo de inserción. Esto se debe a que la inserción de datos en una posición adecuada implica dos pasos:
1. Calcular la posición.
2. Mueva los datos desde la posición calculada en el paso #1 un paso hacia la derecha para crear un espacio donde se insertarán los datos.
El uso de la búsqueda binaria reduce la complejidad del tiempo en el paso n.° 1 de O(N) a O(logN). Pero, la complejidad del tiempo en el paso #2 sigue siendo O(N). Entonces, la complejidad general sigue siendo O (N ^ 2).
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