Encontrar el número de elementos más pequeños para cada elemento en una matriz de manera eficiente

Estoy atrapado en este problema:

Dada una matriz de los primeros números naturales permutados al azar, se construye una matriz , de modo que es el número de elementos de a que son más pequeños que . $A$$n$$B$$B(k)$$A(1)$$A(k-1)$$A(k)$

i) Dado ¿puedes encontrar en tiempo? ii) Dado ¿puedes encontrar en tiempo?$A$$B$$O(n)$
$B$$A$$O(n)$

Aquí, . Para un ejemplo concreto: $B(1) = 0$

$$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \\ \end{vmatrix}$$

¿Alguien puede ayudarme? Gracias.

El algoritmo ingenuo para determinar de :$B$$A$

Para , determine el valor de comparando cada con para y contando los que satisfacen .B ( k ) A ( i ) A ( k ) i = 1 , … , k A ( i ) < A ( k $k=1,\dots,n$$B(k)$$A(i)$$A(k)$$i=1,\dots,k$$A(i)<A(k)$

Este algoritmo compara con todos los demás ( veces), con otros, etc., por lo que el número total de comparaciones es . Pero eso no es lo mejor que podemos hacer. Por ejemplo, mirando , ¡no tenemos que hacer ninguna comparación! porque son los primeros números naturales, y está garantizado (independientemente de la permutación) que los números naturales más bajos estarán allí. ¿Qué pasa con ? En lugar de verificar a , podríamos simplemente verificar . Es decir:$A(1)$$n-1$$A(2)$$n-2$$\frac{(n-1)(n-2)}{2}$$B(n)$$B(n)=A(n)-1$ $n$$n-1$$B(n-1)$$A(1)$$A(n-2)$$A(n)$

Para , use el algoritmo anterior; para use el algoritmo inverso: determine configurándolo inicialmente en y luego restando para cada entrada para que es menor que .$k=1, \dots,\frac{n}{2}$$k=\frac{n}{2},\dots,n$$B(k)$$A(n)-1$$1$$A(i)$$i=k+1,\dots,n$$A(k)$

Esto llevaría pasos, que sigue siendo . Tenga en cuenta también que al construir partir de , si entonces .$2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$$O(n^2)$$A$$B$$B(n)=A(n)-1$$A(n)=B(n)+1$

Pero ahora por más delicadeza. Si se nos permite espacio adicional u ordenar in situ, podemos ordenar los números a medida que los comparamos. Por ejemplo:

$$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & & \\ \end{vmatrix}$$

En lugar de verificarlos todos (o verificarlos en orden), podríamos usar la búsqueda binaria para determinar cada . Sin embargo, la clasificación todavía lleva tiempo .$B(k)$$O(n\log n)$

¡En lugar de determinar cada uno a la vez, podemos mirar hacia adelante y solo revisar cada número en una vez ! Pero usaremos espacio:$B(k)$$A$ $n$

$$\begin{vmatrix} A & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & & B \\ 8 & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{0} & 1 & & 0\\ 4 & & 0 & 0 & 0 & \color{red}{0} & 1 & 1 & 1 & 1 & 2 & & 0\\ 3 & & 0 & 0 & \color{red}{0} & 1 & 2 & 2 & 2 & 2 & 3 & & 0\\ 1 & & \color{red}{0} & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 & & 0\\ 7 & & 0 & 1 & 1 & 2 & 3 & 3 & \color{red}{3} & 4 & 5 & & 3\\ 2 & & 0 & \color{red}{1} & 2 & 3 & 4 & 4 & 4 & 5 & 6 & & 1\\ 9 & & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & \color{red}{6} & & 6\\ 6 & & 0 & 1 & 2 & 3 & 4 & \color{red}{4} & 5 & 6 & 7 & & 4\\ 5 & & 0 & 1 & 2 & 3 & \color{red}{4} & 5 & 6 & 7 & 8 & & 4\\ \end{vmatrix}$$

Podríamos ahorrar aún más tiempo al no actualizar los que ya se han determinado (es decir, no tiene sentido actualizar después del primer paso), pero en el peor de los casos, todavía tenemos que actualizar veces$8$$\frac{(n)(n+2)}{2}$

tanto I como II pueden resolverse usando #next_greater_element que expliqué aquí . pero es un poco más difícil que solo el problema, pero antes de la solución necesitas aprender el siguiente elemento más importante:

1. consideramos que tenemos un vector para cada elemento de nombre que para el elemento . ahora, una vez ejecutado el siguiente algoritmo mayor, comenzando de derecha a izquierda, pero excepto establecer el elemento en su próximo índice de elemento mayor, presione los elementos que es su próximo elemento mayor. Luego, repita el recorrido de izquierda a derecha y luego donde es el tamaño del vector .y su porque cada uno de los siguientes algoritmos mayores es y también iterar es$A$$S_i$$i$$i$$A$$S_i$$i$$B[i]=\sum_{j=0}^x (S_i[j]+1)$$x$$S_i$$\Theta(n)$$\Theta(n)$$\Theta(n)$

la segunda parte también es similar y señala que podemos obtener el valor del elemento más adecuado en EDIT: mi solución es incorrecta, parece que no tiene ninguna solucióno ( n $O(1)$$o(n)$