Considere una array ordenada de n números. ¿Cuál sería la complejidad temporal del algoritmo más conocido para encontrar un par ‘a’ y ‘b’ tal que |ab| = k , siendo k un entero positivo.
(A) O(n)
(B) O(n log n)
(C) O(n ^ 2)
(D) O(log n)
Respuesta: (A)
Explicación: simplemente mantenga dos punteros al inicio y aumente en consecuencia uno de ellos dependiendo de si la diferencia es menor o mayor que k. Solo se requiere un pase, por lo que la respuesta es O (n).
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