Sea s una array ordenada de n enteros. Sea t(n) el tiempo que tarda el algoritmo más eficiente en determinar si hay dos elementos con una suma menor que 1000 en s. ¿Cuál de las siguientes afirmaciones es verdadera? (GATE CS 2000)
a) t (n) es 0 (1)
b) n < t (n) < n 
c) n log 2 n < t (n) < 
d) t (n) =
(A) a
(B) b
(C) c
(D) d
Respuesta: (A)
Explicación: Deje que la array se ordene en orden ascendente, si la suma de los dos primeros elementos es menor que 1000, entonces hay dos elementos con suma menor que 1000 de lo contrario no. Para una array ordenada en orden descendente, debemos verificar los dos últimos elementos. Para una estructura de datos de array, el número de operaciones es fijo en ambos casos y no depende de n, la complejidad es O (1)
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