K = bal (LOPT,LMF) = Anzahl der Inversionen (Vertauschungen) in LMF bzgl. LOPT
Wenn (x,y) eine Inversion von LMF bzgl. LOPT , so ist auch (y,x) eine Inversion in LOPT bzgl. LMF. Daher ist bal (LOPT,LMF) = bal (LMF,LOPT).
Der Kontostand bal (LOPT,LMF) misst, wie viele Elemente in LMF "falsch" stehen, wenn man die Reihenfolge der Elemente in LOPT als "richtig" ansieht.
=> Man kann die Elemente in LOPT auch so umnummerieren und umbenennen, dass in LOPT gerade1,2,...,N in dieser Reihenfolge auftreten und trotzdem die Inversionszahl unverändert bleibt.
Zum Verständnis hier noch ein kleines Beispiel:
Sei:
|
LOPT:
|
4
|
3
|
5
|
1
|
7
|
2
|
6
|
|
LMF:
|
3
|
6
|
2
|
5
|
1
|
4
|
7
|
Wie im Beispiel 1 zu Inversionen ermittelt ergibt sich ein Kontostand von12.
Wenn man LOPT und LMF nun umnummeriert erhält man folgendes,
|
LOPT:
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
LMF:
|
2
|
7
|
6
|
3
|
4
|
1
|
5
|
da das Element was an
|
Position i in LOPT stand |
an Position j in LMF stand. |
=> i steht unter j
|
|
1 |
6 |
1 unter 6
|
|
2 |
1 |
2 unter 1
|
|
3 |
4 |
3 unter 4
|
|
4 |
5 |
4 unter 5
|
|
5 |
7 |
5 unter 7
|
|
6 |
3 |
6 unter 3
|
|
7 |
2 |
7 unter 2
|
Auch hier ist der Kontostand 12 (siehe Inversionen Beispiel 2)