Frage nach Inversion

Question

Ich habe etwas in der Website gelesen, dass Inversionsmittel, wenn i<j dann A[i]>A[j] und es einige Übungen darüber hat, habe ich eine Menge Fragen, aber ich möchte nur eine von ihnen zunächst fragen, und dann werde ich die anderen Übungen von mir, wenn ich kann !!

Übung: Was Permutation Array (1,2, ..., n) die höchste Anzahl von Inversion? Was sind diese? Dank

Answer 1

Klar N, ..., 2, 1 hat die höchste Zahl von Inversionen. Jedes Paar ist eine Umkehrung. Zum Beispiel für N = 6 haben wir 6 5 4 3 2 1. Die Umkehrungen sind 6-5, 6-4, 6-3, 6-2, 6-1, 5-4, 5-3 und so weiter. Ihre Zahl ist N * (N - 1) / 2.

Answer 2

Nun, die Identität Permutation (1,2, ..., n) hat keine Inversionen. Da eine Umkehrung ein Paar von Elementen, die als ihre Indizes in umgekehrter Reihenfolge sind, beinhaltet die Antwort wahrscheinlich eine gewisse Umkehrung dieser Permutation.

Answer 3

Ich habe noch nie den Begriff Umkehrung verwendet in dieser Art und Weise zu hören.

Eine abnehmende Array der Länge N, für n> 0 ist, hat 1/2 * N * (N-1) Paare i A [j]. Dies ist die maximal mögliche.