complexity-theory

___ qstntxt ___

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.

    
___ answer8621059 ___

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önnen

Anspruch 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

finden

Beweis: 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.

    
___ qstnhdr ___ Wie schnell kann 'das Finden des Maximums in einem Array' möglicherweise kommen? ___ answer8615628 ___

Ich vermute, dass dies O (N / P) + O (P)

ist
  • Das Teilen der Arbeit zwischen P-Prozessoren kostet O (P)
  • kombiniert die Arbeit von P-Prozessoren hat auch Kosten von O (P)
  • Eine perfekte parallele Suche von N Elementen nach P Prozessoren hat Zeitkosten von O (N / P)

Mein naive Algorithmus wäre zu

  • schreibe Element 0 in eine CREW-Zelle mit der Bezeichnung "result"
  • starten P völlig unabhängige Suchen, jeweils durch 1 / P th der N Items
  • Verwenden Sie nach Abschluss jeder Suche CAS-Spinloop, um "Ergebnis" durch das Ergebnis der Teilsuche zu ersetzen, falls es größer ist. (Abhängig von Ihrer Definition von CREW benötigen Sie den Spinloop möglicherweise nicht)
___ tag123algorithm ___ Ein Algorithmus ist eine Folge wohldefinierter Schritte, die eine abstrakte Lösung für ein Problem definieren. Verwenden Sie dieses Tag, wenn sich Ihr Problem auf den Algorithmusentwurf bezieht. ___ answer11656639 ___

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.

    
___ tag123Komplexitätstheorie ___ Die Computational Complexity Theory ist ein Zweig der Computertheorie in der theoretischen Informatik und Mathematik, der sich darauf konzentriert, Rechenprobleme nach ihren inhärenten Schwierigkeiten zu klassifizieren. Besonders häufig in der Programmierung ist * amortisierte Analyse * für Zeit oder Raum ___ answer8615631 ___

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.

    
___ answer8617822 ___

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.

    
___
1
Antwort

Gibt es Online-Algorithmen für den Planaritätstest?

Ich weiß, dass Planaritätstest in O (v) durchgeführt werden kann (äquivalent zu O (e), seit planaren Graphen) habe O (v) Kanten) Zeit. Ich frage mich, ob es online in O (1) amortisierten Zeit getan werden kann, wenn jede Kante hinzugefügt w...
22.10.2009, 04:19
2
Antworten

Rekursion schneller als Iteration

Ich habe einen Quadtree in C # implementiert und bin auf ein merkwürdiges Vorkommnis gestoßen, bei dem die Rekursion besser abläuft als die Iteration, obwohl es aussieht, als müsste das Gegenteil der Fall sein. Meine Knoten sehen so aus: %V...
17.09.2013, 06:59
3
Antworten

ist es möglich, ein Programm zu schreiben, das seinen eigenen Quellcode unter Verwendung einer "Sequenzerzeugungsfunktion" druckt

ist es möglich, ein Programm zu schreiben, das seinen eigenen Quellcode mit Hilfe einer "sequenzerzeugenden Funktion" ausgibt? Was ich eine Sequenzerzeugungsfunktion nenne, ist einfach eine Funktion, die einen Wert außerhalb eines bestimmten...
17.05.2010, 14:11
1
Antwort

Schätzung der tatsächlichen (nicht theoretischen) Laufzeitkomplexität einer Implementierung

Jeder in der Informatik weiß, dass HeapSort in der Theorie der theoretisch schlimmste Fall ist, während QuickSort im schlimmsten Fall O(n log n) ist. In der Praxis wird jedoch ein gut implementiertes QuickSort (mit guten Heuristiken) HeapSort...
05.07.2013, 16:52
14
Antworten

Wie bekämpfen Sie die Komplexität des Designs? [geschlossen]

Ich kämpfe oft mit Overengineering - die für die Entwicklung der Software verantwortliche Person hat eine Architektur, die viel zu kompliziert ist. Es ist alles gut und schön, all die esoterischen Features zu haben, von denen die Benutzer nie...
02.03.2009, 16:31
10
Antworten

Kann ich die rechnerische Komplexität reduzieren?

Nun, ich habe diesen Code, der das Programm enorm verlangsamt, weil es eine lineare Komplexität ist, aber oft aufgerufen wird, was das Programm quadratisch kompliziert macht. Wenn es mir möglich ist, möchte ich seine Rechenkomplexität reduzieren...
20.12.2008, 20:51
2
Antworten

Wie ist das Einfügen von O (log (n)) in Data.Set?

Beim Durchsehen der Dokumente von Data.Set habe ich gesehen, dass Das Einfügen eines Elements in den Baum wird als O (log (n)) bezeichnet. Ich würde jedoch intuitiv erwarten, dass es O (n * log (n)) (oder vielleicht O (n)?) Ist, da referenz...
04.01.2013, 22:23
7
Antworten

Unit Testing ist gleich und Hashcode - eine Komplexität Geschichte

Ich habe ein moralisches Dilemma. Ich habe einige Wertobjekte in meiner Anwendung, die unveränderlich und extrem einfach sind. Ich habe den equals und den hashcode mit einer IDE generiert (intellij in meinem Fall), aber das hat dazu geführt, das...
23.04.2011, 13:18
9
Antworten

Berechne den Kosinus einer Sequenz

Ich muss folgendes berechnen: %Vor% totalN ist eine große Zahl, also möchte ich das effizienter machen. Gibt es eine Möglichkeit, dies zu verbessern? Ich vermute, dass es da ist, denn schließlich wissen wir, was das Ergebnis von cos (n) ist,...
01.03.2010, 18:10
3
Antworten

Was ist die Komplexität dieses Codes, dessen verschachtelte for-Schleife seinen Zähler wiederholt verdoppelt?

In dem Buch Programming Interviews Exposed heißt es, dass die Komplexität des unten stehenden Programms O (N) ist, aber ich verstehe nicht, wie das möglich ist. Kann jemand erklären, warum das so ist? %Vor%     
05.09.2012, 17:19