Gibt es einen O (n) -Algorithmus, um ein Array ohne Präfix für ein positives Integer-Array zu erzeugen?

Für Array [4,3,5,1,2], rufen wir Präfix von 4 ist NULL, Prefix-weniger von 4 ist 0; Präfix von 3 ist [4], Präfix-less von 3 ist 0, weil kein Präfix kleiner als 3 ist; Präfix von 5 ist [4,3], Präfix-weniger von 5 ist 2, weil 4 und 3 beide weniger als 5 sind; Präfix von 1 ist [4,3,5], Präfix-less von 1 ist 0, weil kein Präfix kleiner als 1 ist; Präfix von 2 ist [4,3,5,1], Präfix-weniger von 2 ist 1, denn nur 1 ist weniger als 2Gibt es einen O (n) -Algorithmus, um ein Array ohne Präfix für ein positives Integer-Array zu erzeugen?

Also für Array [4, 3, 5, 1, 2], wir get prefix-less arrary von [0,0, 2,0,1], Können wir einen O (n) Algorithmus erhalten, um ein Array ohne Präfix zu erhalten?

Quelle

2012-03-28 Weida

Ich fragte dies, weil ich ein O (n) ernten möchte, um die Inversion eines gegebenen Arrays zu zählen, sogar dieses Array kommt in den Stream. – Weida

Wahrscheinlich nicht. Es sieht so aus, als hätte ein Array ohne Präfix die Möglichkeit, das ursprüngliche Array in O (n) -Zeit zu sortieren. –

@ n.m .: Wie sortieren wir das Original in linearer Zeit mit dem Array ohne Präfix? Der Ansatz, den ich beim Sortieren unter Verwendung des Präfix-less-Arrays sehe, besteht darin, jedes Element an der Position p [i] einzufügen, aber es ist nicht klar, wie dies in linearer Zeit durchgeführt werden kann. – Nabb

Ich denke, das sollte funktionieren, aber überprüfen Sie die Details. Lassen Sie uns ein Element im ursprünglichen Array a [i] und eins im Präfix-Array als p [i] bezeichnen, wobei i das i-te Element der jeweiligen Arrays ist.

Also sagen wir, wir sind bei a [i] und wir haben bereits den Wert von p [i] berechnet. Es gibt drei mögliche Fälle. Wenn a [i] == a [i + 1], dann ist p [i] == p [i + 1]. Wenn a [i] < a [i + 1], dann p [i + 1]> = p [i] + 1. Dies lässt uns den Fall, in dem a [i]> a [i + 1]. In dieser Situation wissen wir, dass p [i + 1]> = p [i].

Im naiven Fall gehen wir zurück durch das Präfix und fangen an, weniger als a [i] zu zählen. Aber wir können es besser machen. Zuerst erkenne, dass der Minimalwert für p [i] 0 ist und das Maximum i ist. Als nächstes betrachten wir den Fall eines Index j, wobei i> j. Wenn a [i]> = a [j], dann ist p [i]> = p [j]. Wenn ein [i] < a [j], dann p [i] < = p [j] + j. Also können wir rückwärts durch p gehen und die Werte für p [i] _min und p [i] _max aktualisieren. Wenn p [i] _min gleich p [i] _max ist, dann haben wir unsere Lösung.

Wenn Sie die Hüllkurvenanalyse des Algorithmus ausführen, hat er die beste Fallleistung (0). Dies ist der Fall, wenn die Liste bereits sortiert ist. Der schlimmste Fall ist, wo es umgekehrt sortiert wird. Dann ist die Leistung O (n^2). Die durchschnittliche Leistung wird O (k * n) sein, wobei k angibt, wie viel zurückgespult werden muss. Meine Schätzung ist für zufällig verteilte ganze Zahlen, k wird klein sein.

Ich bin auch ziemlich sicher, es gäbe Möglichkeiten, diesen Algorithmus für Fälle von teilweise sortierten Daten zu optimieren. Ich würde auf Timsort für einige Inspiration schauen, wie man das macht. Es verwendet Lauferkennung, um teilweise sortierte Daten zu erkennen. Die Grundidee des Algorithmus wäre also, einmal durch die Liste zu gehen und nach Datenläufen zu suchen. Für aufsteigende Datenläufe haben Sie den Fall, dass p [i + 1] = p [i] +1 ist. Für absteigende Läufe gilt p [i] = p_run [0] wobei p_run das erste Element im Lauf ist.

Quelle

2012-08-15 17:31:04

Es ist nicht wahr, dass "Wenn a [i] xan

Guter Fang. Ich habe es geändert, um p [i + 1]> = p [i] +1 zu lesen. –

Es kann kein comparison sort benötigt O(n log n) Vergleiche in O(n) aus den gleichen Gründen erfolgen. Die Anzahl der möglichen Arrays ohne Präfix ist n!, so dass Sie mindestens log2(n!) Bits an Informationen benötigen, um das korrekte Feld ohne Präfix zu identifizieren. log2(n!) ist O(n log n), von Stirling's approximation.

Quelle

2012-08-18 02:19:30 xan

Nicht genau richtig. Vergleichssortierungen erfordern O (n log n), aber es gibt keinen Grund für eine Vergleichssortierung. Als ein Beispiel können Sie Radix-Sortierung verwenden, um Integer-Arrays zu sortieren. Dies ist O (k * n) -Komplexität. –

@ShawnH Ich sage nicht genau, dass Sie eine Vergleichssortierung verwenden müssen (oder irgendeine Art für diese Angelegenheit) - nur dass die gleiche informationstheoretische Logik gilt. In Radix-Sortierung, ist nicht k normalerweise die Anzahl der Stellen, die etwa log10 (n) ist, so dass es O (n log n)? – xan

@xan: Sie können diese Implikation nur machen, wenn Sie die Einschränkung hinzufügen, dass die Elemente unterschiedlich sein müssen. Zum Beispiel kann ich ein Eingabearray von 1 Milliarde 1-stelligen Elementen haben. –

Unter der Annahme, dass die Eingangselemente sind immer feste Breite ganze Zahlen können Sie eine Technik, die auf Radixsort verwenden Basis lineare Zeit zu erreichen:

L ist das Eingabearray
X ist die Liste des Indizes L im Fokus für Stromdurchgang
n die Bit wir gerade arbeiten
Zahl ist die Anzahl von 0-Bits bei Bit n links der aktuellen Position
Y die Liste von indexs einer Subsequenz o ist f L für die Rekursion
P ist ein Null initialisiert Array, das die Ausgabe (die prefixless Array)

In Pseudo-Code ...

Def PrefixLess(L, X, n) 
    if (n == 0) 
     return; 

    // setup prefix less for bit n 
    Count = 0 

    For I in 1 to |X| 
     P(I) += Count 
     If (L(X(I))[n] == 0) 
      Count++; 

    // go through subsequence with bit n-1 with bit(n) = 1 
    Y = [] 
    For I in 1 to |X| 
     If (L(X(I))[n] == 1) 
      Y.append(X(I)) 

    PrefixLess(L, Y, n-1) 

    // go through subsequence on bit n-1 where bit(n) = 0 
    Y = [] 
    For I in 1 to |X| 
     If (L(X(I))[n] == 0) 
      Y.append(X(I)) 

    PrefixLess(L, Y, n-1) 

    return P

und dann auszuführen:

PrefixLess(L, 1..|L|, 32)

Quelle

2012-08-18 02:44:16

Gibt es einen O (n) -Algorithmus, um ein Array ohne Präfix für ein positives Integer-Array zu erzeugen?

Antwort

Verwandte Themen