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 %code% numbers und eine Maschine mit %code% Prozessoren und einem gemeinsamen %code% 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.
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.
Ich denke, es ist %code% , wo %code% . %code% Prozessoren suchen nach %code% von %code% Elementen, gefolgt von %code% paarweisen Zusammenführungen, die parallel ausgeführt werden. Die ersten %code% 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 %code% 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.