Esta es una pregunta de la entrevista. Dado un conjunto entero ordenado y un número z, encuentre todos los pares (x, y) en el conjunto de modo que x + y < z. ¿Se puede hacer mejor que O (n^2)?Encuentra todos los pares (x, y) en una matriz ordenada para que x + y <z
P.S. Sé que podemos encontrar todos los pares (x, y | x + y == z) en O (N).
No necesariamente se puede encontrar todos los pares en un tiempo O (n 2 ), porque puede haber O (n 2 ) pares de valores que tienen esta propiedad. En general, un algoritmo no puede tomar menos tiempo para ejecutarse que el número de valores que produce.
Espero que esto ayude!
En generar, no, no puede. Considere el caso donde x + y < z para todos x, y en la matriz. Debe tocar (por ejemplo, mostrar) todos los pares posibles n(n - 1)/2 en el conjunto. Esto es fundamentalmente O (n^2).
Puede encontrar en O (N), si agrega la restricción adicional de que cada elemento es único.
Después de encontrar todos los pares x + y == z, sabe que por cada xey que satisfaga esa condición, cada x o y (elija una) que tenga un índice menor que su par satisface la x + y < z condición.
En realidad, seleccionarlos y darles salida tomaría O (n^2), pero en cierto sentido, los pares x + y == z son una forma comprimida de la respuesta, junto con la entrada.
(Puede preprocesar la entrada a un formulario donde cada elemento es único, junto con un contador para el número de ocurrencias. Esto tomaría O (N) tiempo. Puede generalizar esta solución a matrices sin clasificar, aumentando el tiempo hasta O (nlogn).)
La justificación para decir que encontrar los pares en un tiempo linealmente proporcional al tamaño de la solución: Supongamos que la pregunta es "¿cuáles son los enteros que están entre 0 y la entrada K dada?" ?
Si le piden que muestre todos los pares que satisfacen esa propiedad, no creo que haya nada mejor que O (N^2) ya que puede haber O (N^2) pares en la salida.
Pero esto también es cierto para x + y = z, por lo que usted afirma que hay una solución O (N), por lo que podría estar perdiendo algo.
Sospecho que la pregunta original pidió el número de pares. En ese caso, se puede hacer en O (N log (N)). Para cada elemento x averigua y = z - x y haz una búsqueda binaria para y en la matriz. La posición de y proporciona la cantidad de pares que se pueden formar con ese valor particular de x. Sumar esto sobre todos los valores en la matriz le da la respuesta. Hay N valores y encuentra el número si los pares para cada uno toman O (log (N)) (búsqueda binaria), entonces todo es O (N log (N)).
Debido a que es un vector de enteros ordenados , se puede utilizar el algoritmo de búsqueda binaria , así que lo mejor es O(N), y lo peor es O(N*logN), un caso medio es también O(N*logN).
Puede ordenar la matriz y para cada elemento que sea menor que z, use la búsqueda binaria - total O (NlogN).
Total tiempo de ejecución: O (| P | + NlogN), donde P es el resultado de los pares.
En realidad existe una solución O (nlogn) para esta pregunta. Lo que haría (después de verificar primero si se me permite hacer eso) es definir el formato de salida de mi algoritmo/función.
Lo definiría como una secuencia de elementos (S, T). S - Posición del elemento en la matriz (o su valor). T - Posición de la matriz secundaria [0, T]. Entonces, por ejemplo, si T = 3, significa que el elemento S combinado con los elementos 0,1,2 y 3 satisface la condición deseada.
El resultado total de esto es O (nlogn) tiempo de ejecución y O (n) memoria.
Aunque estoy completamente de acuerdo con su observación, vea mi comentario sobre nuestra capacidad para definir el "formato" de salida. – ZeDuS