Heute habe ich die neueste Prüfung der örtlichen Informatik-Olympiade gesucht und ich habe ein interessantes Problem gefunden. Kurz gesagt, es wird gebeten, bei einem Integer-Array zu zählen, wie viele Inversionen es hat, wobei eine Inversion ein Indikatorpaar ist i , j , so dass i > j und A[i] < A[j] . Informell ist die Anzahl der Inversionen die Anzahl der Paare, die nicht in Ordnung sind. Anfangs habe ich eine O(n²) Lösung gemacht (ja, die naive), aber da sie nicht mit der Größe der Eingabe übereinstimmt, dachte ich ein bisschen über das Problem nach und dann merkte ich, dass es möglich ist, es innerhalb von% zu tun. co_de% time von einer Variante von merge sort, die die Größe der Eingabe gut behandelt.
Aber nachdem wir die Eingabebeschränkungen gesehen haben ( O(n log n) integers zwischen n und keine Duplikate), habe ich mich gefragt, ob meine Lösung optimal ist, oder weißt du, ob es eine andere Lösung für dieses Problem gibt, die 1 and M schlägt Laufzeit?
Das beste Ergebnis in der Literatur ist ein O (n √ (log n)) Algorithmus aufgrund von Chan und Patrascu . Keine Ahnung von der Konstante.
Wenn wir annehmen, dass die Anzahl der Bits, die zur Darstellung der Ganzzahl verwendet werden, konstant ist (etwa 32 oder 64 Bits), kann dies in O (N) -Zeit gelöst werden.
Hier ist eine Beispiel-Python-Implementierung.
%Vor%
Wir können weniger als O (N x Log (N)) Zeitkomplexität erreichen, da wir die Idee hinter einem nicht vergleichenden Sortieralgorithmus, radix sort, verwenden, um die Anzahl zu erhalten.
Tags und Links algorithm language-agnostic sorting