¿Cómo calcular el número "esperado" de inversiones en una matriz semi-aleatoria de enteros? - matrices, algoritmo, matematicas, aleatorias

Considere una matriz de enteros. Un par (i, j) se llama inversión en A si i <j y A [i]> A [j].

Para cada posición "i" en la matriz hay dos posibles candidatos: a [i] con probabilidad p [i] y a [i] + x con probabilidad 1-p [i].

Ahora tengo que calcular el número esperado de inversiones. Dados un [i] yp [i] para cada índice iy un entero x.

Conozco el enfoque O (n ^ 2) (verifique todos los documentos legalesposible par). Además, conozco el enfoque O (nlogn) para calcular el número de inversiones en una matriz en la que todos los elementos están predeterminados con un 100% de probabilidad. Se hace modificando la ordenación de fusión.

Quiero conocer un enfoque mejor que n al cuadrado. Por favor hagamelo saber.

Respuestas

Esto se puede hacer con una simple modificación del algoritmo estándar de combinación de clasificación para contar las inversiones, donde asignamos un peso a cada valor y calculamos la suma de W[i]*W[j] para i<j, A[i]>A[j] (cuando cada peso es 1, obtenemos el recuento normal). En lugar de agregar a la cuenta el número de elementos que quedan en la matriz izquierda, agregamos la suma de los pesos para estos elementos multiplicada por la ponderación del elemento en la matriz derecha que estamos procesando.

Para utilizar este algoritmo para resolver el problema planteado,simplemente cree una matriz del doble del tamaño, donde cada elemento de la matriz original se reemplaza por dos elementos (en orden ordenado), con ponderaciones dadas por las probabilidades.

Dejé un comentario explicando esto, pero puedestenga un cálculo O (1) de esto si solo usa un poco de matemáticas. Le ahorraré el trabajo, pero, según mis cálculos, el número esperado de inversiones en una matriz de n enteros es ((n ^ 2) - (n)) / 4. Disculpe la abundancia de paréntesis, solo quería para asegurarme de que estaba totalmente claro. Puedo publicar el trabajo si lo desea, pero pensé que lo omitiría si solo necesita la respuesta.

Entonces, a pesar de lo que dice mi comentario, lo recordé incorrectamente. No es lg (n).