Binäre Inversion

[pixsta]

Hallo!

Ich suche einen Algorithmus für folgende Problemstellung:

Binäre Inversionen: Sei A eine Liste von Nullen und Einsen. 
Die Zahl der Inversionen von A ist die Anzahl jener Paare (i,j) von Listenelementen, für die i<j, aber A[i]>A[j] gilt. 
Der Zeitaufwand des Programms soll linear in der Länge von A sein.

Beispiel: Die Liste (1,0,1,1,0) weist 4 Inversionen auf, nämlich (0,1), (0,4), (2,4) und (3,4).

ok. mein problem liegt darin, einen algorithmus zu entwickeln, der log(n) braucht.
Wäre für ein paar tipps dankbar
grüße,

[EDIT]: ein algorithmus für normale inversion (also nicht binär) mit einem zeitaufwand von nlog(n) wäre auch ok.

[SG1]

pixsta schrieb:

ok. mein problem liegt darin, einen algorithmus zu entwickeln, der log(n) braucht.

Gibt's nicht. Du musst ja jede Stelle mindestens einmal angucken, damit bist du aber schon in $\Theta(n)$

[pixsta]

hast du f+r Θ(n) einen algorithmus?

[SG1]

Von links nach rechts durchgehen, die 1en zaehlen, und jedesmal, wenn du auf 'ne 0 triffst, hast du soviele Inversionen wie vorher 1en.