Sea A[1…n] un arreglo de n números distintos. Si i < j y A[i] > A[j], entonces el par (i, j) se llama una inversión de A. ¿Cuál es el número esperado de inversiones en cualquier permutación en n elementos?
(A) n(n-1)/2
(B) n(n-1)/4
(C) n(n+1)/4
(D) 2n[logn]
Respuesta: (B)
Explicación:
Hay n (n-1)/2 pares tales que i < j. Para un par (a i , a j ), la probabilidad de ser inversión es 1/2. Por lo tanto valor esperado de inversiones = 1/2 * (n(n-1)/2) = n(n-1)/4.
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