Diese Frage kommt von einer Diskussion, die zu dieser anderen Frage geführt wurde: Algorithmus zur Linearisierung bereits linearisieren . Es ist nicht Hausaufgabe.
Sie erhalten ein Array von N numbers und eine Maschine mit P Prozessoren und einem gemeinsamen CREW Speicher (Concurrent Read, Exclusive Write Speicher).
Was ist die engste obere Grenze im schnellsten Algorithmus, um die größte Nummer im Array zu finden? [Offensichtlich auch: Was ist der Algorithmus selbst?]
Ich beziehe mich nicht auf die Gesamtmenge der geleisteten Arbeit [die nie weniger als O (N)] sein kann.
Ich denke, es ist O(N/P') + O(Log2(P')) , wo P'=min{N,P} . P' Prozessoren suchen nach max von N/P' Elementen, gefolgt von Log2 paarweisen Zusammenführungen, die parallel ausgeführt werden. Die ersten P'/2 Merges werden von geradzahligen Prozessoren erledigt, die nächsten 'P' / 4 '- von Prozessoren an Stellen, die durch 8 teilbar sind, dann durch 16 und so weiter.
Bearbeiten P' wird eingeführt, um den Fall abzudecken, wenn Sie wesentlich mehr Prozessorknoten als die Elemente haben, die Sie durchsuchen müssen.
Cook, Dwork und Reischuk zeigten, dass jeder CREW-Algorithmus zum Finden des Maximums von n Elementen in Omega (lg n) -Zeit laufen muss, sogar mit einer unbegrenzten Anzahl von Prozessoren und unbegrenztem Speicher. Wenn ich mich richtig erinnere, erscheint ein Algorithmus mit einer passenden oberen Grenze in ihrem Papier:
Stephen Cook, Cynthia Dwork und Rüdiger Reischuk. Obere und untere Zeitgrenzen für parallele Maschinen mit wahlfreiem Zugriff ohne gleichzeitige Schreibvorgänge. SIAM Journal on Computing, 15 (1): 87-97, 1986.
Folgendes ist optimal gebunden:
Wenn p & lt; = n / log n, können Sie es in O (n / p) -Zeit tun; andernfalls ist es O (log n), d. h. wenn p & gt; n / log n ist, erhält man nichts im Vergleich zu p = n / log n.
Beweis - untere Grenze:
Anspruch 1: Sie können niemals schneller als Ω (n / p) arbeiten, weil p-Prozessoren nur eine Beschleunigung von p
bewirken könnenAnspruch 2: Sie können niemals schneller als Ω (log n), wegen des CREW-Modells (siehe das Dokument von unforgiven); Wenn Sie überprüfen möchten, ob ein 0-1-Array mindestens eine 1 hat, benötigen Sie O (log n) time.
Beweis - obere Grenze:
Anspruch 3: Sie können Maximum mit n / log n Prozessoren und in O (log n) Zeit
findenBeweis: Es ist einfach, maximale Verwendung von n Prozessoren und log n Zeit zu finden; Tatsächlich aber sind bei diesem Algorithmus die meisten Prozessoren die meiste Zeit ruhend; durch geeignete Verzahnung (siehe z. B. Papadimitrious Komplexitätsbuch) kann ihre Anzahl auf n / log n verringert werden.
Wenn Sie jetzt weniger als n / log n-Prozessoren angeben, können Sie K-Prozessoren zugewiesene Aufgaben einem Prozessor zuweisen, dies teilt die Prozessoranforderung durch K und multipliziert die erforderliche Zeit mit K.
Sei K = (n / log n) / p; der vorherige Algorithmus läuft in der Zeit O (K log n) = O (n / p) und benötigt n / (log n * K) = p Prozessoren.
Bearbeitet: Ich habe gerade festgestellt, dass der Algorithmus von dasblinkenlight bei p & lt; = n / log n dieselbe asymptotische Laufzeit hat:
n / p + log p & lt; = n / p + log (n / log n) & lt; = n / p + log n & lt; = n / p + n / p & lt; = 2n / p = O (n / p)
Sie können also diesen Algorithmus verwenden, der die Komplexität 0 (n / p) hat, wenn p & lt; = n / log n und O (log n) sonst.
Ich vermute, dass dies O (N / P) + O (P)
istMein naive Algorithmus wäre zu
Für P = N ^ 2 ist es O (1).
Alle initialisieren boolesches Array CannotBeMax [i] = FALSE
Proc (i, j) setzt CannotBeMax [i] = A [i] & lt; A [j]
Max ist A [CannotBeMax [i] == FALSCH]
Beachten Sie, dass alle gleichzeitigen Schreibvorgänge versuchen, identische Informationen zu schreiben, so dass die Antwort konsistent ist, egal, welche erfolgreich ist.
Tags und Links algorithm complexity-theory