question sur l'inversion

Question

J'ai lu quelque chose sur le site que les moyens d'inversion si i<j puis A[i]>A[j] et il a quelques exercices à ce sujet, j'ai beaucoup de questions, mais je veux poser une d'entre eux d'abord, puis je vais faire les autres exercices par moi-même si je peux !!

Exercice: Quelle gamme permutation (1,2, ..., n) a le plus grand nombre d'inversion? Quelles sont ces? merci

Answer 1

Il est clair que N, ..., 2, 1 a le plus grand nombre de renversements. Chaque paire est une inversion. Par exemple, pour N = 6, nous avons 6 5 4 3 2 1. Les inversions sont 6-5, 6-4, 6-3, 6-2, 6-1, 5-4, 5-3 et ainsi de suite. Leur nombre est N * (N - 1) / 2.

Answer 2

Eh bien, la permutation d'identité (1,2, ..., n) n'a pas inversions. Depuis une inversion est une paire d'éléments qui sont dans l'ordre inverse de leurs indices, la réponse implique probablement une inversion de cette permutation.

Answer 3

Je n'ai jamais entendu le terme inversion utilisé de cette façon.

A décroissant tableau de longueur N, pour N> 0, a 1/2 * N * (N-1) paires i A [j]. Ceci est le maximum possible.