algorithmus zum finden von zyklischen verschiebungen in sortierten arrays?
Kennt jemand einen Algorithmus, der berechnet, um wie viele Stellen ein sortiertes Array zyklisch verschoben wurde und dabei in logarithmischer Zeit arbeitet?
Der Algorithmus soll z.B. zur Eingabe [23, 25, 36, 1, 4, 8, 12, 15, 18] 3 ausgeben, da die Eingabe dem Array [1, 4, 8, 12, 15, 18, 23, 25, 36], welches um 3 nach links verschoben wurde, entspricht. Wenn das Array sortiert ist soll 0 zurückgegeben werden. Man kann davon ausgehen, dass das Array sortiert ist oder aus einer zyklischen Verschiebung eines sortierten Arrays entstanden ist.
Ich habe versucht, das ganze über eine Abwandlung von binärer Suche zu lösen, bin mir aber nicht sicher, wie ich die intervallgrenzen wählen soll und welche Bedingung man überprüfen muss
4 Antworten
- sei T der letzte Eintrag der Liste...
- ich nehme mal an, dass die Einträge paarweise verschieden sind, weil man sonst zuviel rumprobieren müsste... grins
- man sucht nun also den Eintrag E der Liste, der >T ist, und dem ein Eintrag folgt, der kleiner oder gleich E ist...
- man sucht also erst etwas mit Intervallschachtelung, das größer ist... wenn man auf etwas kleineres trifft, weiß man, dass man in der rechten Hälfte weitersuchen muss...
- und dann wieder mit Intervallschachtelung etwas rechts davon, das kleiner ist...
- also ich käm da auf O(2·log n)=O(log n)... oda?
weil man zweimal suchen muss... oda?
ist vllt auch ne Schnapsidee von mir... :) bin müde... und so...
- erstmal von ganz hinten nach links nach etwas, das größer ist...
- dann von dort nach rechts, bis man genau die Grenze findet...
oder kann man quasi beide Schritte in einem machen?
jetzt code ich es doch: kicher
#include <stdio.h>
#include <stdlib.h>
int tellme(int * L, int l) {
const int E = L[l-1];
if (L[0]<E) return 0;
int a=0, b=l-2;
while (a < b) {
const int m = (a+b) / 2;
const int M = L[m];
if (M<E) b=m-1;
else if (a<m) a=m;
else if (M<L[a+1]) a++;
else b--;
}
return a+1;
}
int main(int argc, char ** argv) {
int lst[argc-1];
for (int i=0; i<argc-1; i++) lst[i]=atoi(argv[i+1]);
printf("yay! %d\n",tellme(lst,argc-1));
return 0;
}
hast recht: es gehen beide Such-Ziele in derselben Schleife... :)
Logarithmische Komplexität kriegst du hin indem du zuerst das Element ganz links mit dem ganz rechts (als Pivotelement) vergleichst, dann mit dem Element in der Mitte (als Pivotelement), und dann wieder mit dem mittleren Element der linken/rechten Hälfte des kleineren Intervalls. Hoffe du verstehst wie ich das meine.
Da die Arrays sortiert sind, funktioniert das, du prüfst jeweils ob das Pivotelement kleiner/größer ist als das Element ganz links, um den Grad der Verschiebung zu ermitteln
Wenn Du weißt, dass das Array eh "sortiert" ist, dann verstehe ich nicht, warum Du auf logarithmischen Aufwand kommen willst. Das geht dann billiger, indem man einfach die Vorbedingung honoriert und sich nur am Minimum im Array orientiert.
Also:
- Array #1 absuchen und Mindestwert darin finden, Feldindex merken.
- Array #2 absuchen und Mindestwert darin finden, Feldindex merken.
- Differenz Feldindizes bilden und rückmelden.
Dann kommst Du auf O(2*n) mit n=Arraygröße. Ist doch viel effizienter.
Das stimmt nicht, logarithmische Laufzeitkomplexität ist besonders für große Datenmenge deutlich besser als lineare... Insofern ist diese Antwort hier nicht richtig
Und woran scheitert es nun?
Ziehe ein Element aus der Quelle (Median z.B.) und führe eine binäre Suche im Ziel durch. Bestimme (errechne) den Offset (Achtung 2 Kandidaten) und wiederhole mit einem geeigneten Element zur (Gegen)prüfung. Wenn gleiches Offsetting muß das Ergebnis ein Shift sein, andernfalls laut Vorbedingung ein sortiertes Array.
Prinzipiell kannst Du auch 4 Proben ziehen, das ist relativ egal, denn Du bleibst in c*log(n).
Nachtrag: Du kannst im Prinzip erstes Element, Median und letztes Element für den Test nehmen, ab dem zweiten Test sollte Richtung und Distanz feststehen.
Wofür brauchst du mehrere Tests? Die Richtung ist irrelevant, da sich ein Rechts- nicht von einem Links-Shift unterscheidet
Daß die Shiftrichtugn egal ist, stimmt wohl. Allerdings kannst Du mit einem einfachen Test eine Sortierung nicht ausschließen.
4,3,2,1-> 1,2,3,4
Was mir generell fehlt: Gibt es eine Nebenbedingung bezüglich der paarweisen Verschiedenheit der Elemente?
Warum 2*log(n)?