Encuentra todas las diferencias en una serie de O (n)

Question

Pregunta: Dada una matriz ordenada Un encontrar toda posible diferencia de los elementos de A.

Mi solución:

for (int i=0; i<n-1; ++i) { 
    for (int j=i+1; j<n; ++j) { 
    System.out.println(Math.abs(ai-aj)); 
    } 
} 

Claro, es O (n^2), pero no cuento demasiado las cosas. Miré en línea y encontré esto: http://www.careercup.com/question?id=9111881. Dice que no puedes hacerlo mejor, pero en una entrevista me dijeron que puedes hacer O (n). ¿Lo cual está bien?

Answer 1

Una primera idea es que no está utilizando el hecho de que la matriz está ordenada. Supongamos que está en orden creciente (la disminución se puede manejar de manera análoga).

También podemos utilizar el hecho de que el telescopio diferencias (i> j):

a_i - a_j = (a_i - a_(i-1)) + (a_(i-1) - a_(i-2)) + ... + (a_(j+1) - a_j) 

Ahora construir una nueva secuencia, lo llaman s, que tiene la simple diferencia, lo que significa (a_i - a_(i-1)). Esto solo requiere una pasada (O(n)) y también puede omitir repeticiones, lo que significa omitir a_i si a_i = a_(i+1).

Todas las diferencias posibles a_i-a_j con i>j son de la forma s_i + s_(i+1) + ... + s_(j+1). Entonces, tal vez si cuentas que como los encontraste, entonces lo hiciste en el tiempo O(n). Sin embargo, imprimirlos puede tomar hasta n(n-1)/2 llamadas, y definitivamente es O(n^2).

Answer 2

Por ejemplo, para una matriz con los elementos {2 , 2 , ..., 2 ⁿ} hay n ⋅ (n-1)/2 posibles diferencias, y no hay dos de ellos iguales. Entonces hay O (n) diferencias.

Ya que tienes que enumerar todos ellos, también es necesario al menos O (n 2 ) tiempo.

Answer 3

ordenada o desordenada, no importa, si usted tiene que calcular cada diferencia que no hay manera de hacerlo en menos de 2^n,

la pregunta se hizo mal, o simplemente hacer O (n) y luego imprima 42 las otras N veces: D

Answer 4

Puede obtener otro contraejemplo suponiendo que los contenidos de la matriz son enteros aleatorios antes de ordenar. Entonces la posibilidad de que dos diferencias, Ai - Aj vs Ak - Al, o incluso Ai - Aj vs Aj - Ak, sean las mismas es demasiado pequeña para que haya solamente O (n) diferencias distintas Ai - Aj.

Dado que, la pregunta para su entrevistador es explicar las circunstancias especiales que permiten una solución O (n). Una posibilidad es que los valores de matriz sean todos números en el rango 0..n, porque en este caso la diferencia absoluta máxima es solo n.

Puedo hacer esto en O (n lg n) pero no en O (n). Represente los contenidos de la matriz por una matriz de tamaño n + 1 con el elemento i puesto a 1 donde hay un valor i en la matriz. Luego use FFT para convolucionar la matriz consigo misma - hay una diferencia Ai - Aj = k donde el k-ésimo elemento de la convolución es distinto de cero.

Answer 5

Si el entrevistador es aficionado a los juegos teóricos, ¿quizás estaba pensando en usar una tabla de entradas y resultados? Cualquier problema de con un límite en el tamaño de la entrada, y que tiene una solución conocida, puede resolverse mediante la búsqueda de tabla. Dado que primero ha creado y almacenado esa tabla, que podría ser grande.

Por lo tanto, si el tamaño de la matriz es limitado, el problema puede resolverse mediante la búsqueda de tabla, que (con algunas suposiciones) incluso se puede realizar en tiempo constante. De acuerdo, incluso para un tamaño de matriz máximo de dos (suponiendo enteros de 32 bits), la tabla no cabe en la memoria de una computadora normal o en los discos. Para tamaños máximos más grandes de la matriz, está en el tamaño "no encajará en el universo conocido". Pero, teóricamente, se puede hacer.

(Pero, en realidad, creo que el comentario de Jens Gustedt es más probable.)