Kontext der Rechenkomplexität – Wikipedia

In der Theorie der rechnerischen Komplexität und der Analyse von Algorithmen wird eine Reihe von Metriken definiert, die die Ressourcen wie Zeit oder Raum beschreiben, die eine Maschine zur Lösung eines bestimmten Problems benötigt. Die sinnvolle Interpretation dieser Metriken erfordert einen Kontext. Dieser Kontext ist häufig implizit und hängt vom Feld und dem betrachteten Problem ab. Dieser Artikel beschreibt eine Reihe wichtiger Kontextelemente und deren Auswirkungen auf Metriken.

Definitionen von Variablen[edit]

Metriken werden normalerweise in Form von Variablen beschrieben, die eine Funktion der Eingabe sind. Zum Beispiel erfordert die Anweisung, dass die Einfügesortierung O (n²) Vergleiche sind ohne Definition bedeutungslos nDies ist in diesem Fall die Anzahl der Elemente in der Eingabeliste.

Da viele verschiedene Kontexte dieselben Buchstaben für ihre Variablen verwenden, kann es zu Verwirrung kommen. Zum Beispiel kann die Komplexität von Primalitätstests und Multiplikationsalgorithmen auf zwei verschiedene Arten gemessen werden: eine in Bezug auf die getesteten oder multiplizierten Ganzzahlen und eine in Bezug auf die Anzahl der Binärziffern (Bits) in diesen Ganzzahlen. Zum Beispiel wenn n Wenn die Ganzzahl auf Primalität getestet wird, kann die Testabteilung sie in Θ (n) testen^1/2) Rechenoperationen; doch wenn n Ist die Anzahl der Bits in der Ganzzahl, die auf Primalität getestet werden, ist Θ (2) erforderlich^{n / 2}) Zeit. In den Bereichen Kryptographie und rechnergestützte Zahlentheorie ist es typischer, die Variable als die Anzahl der Bits in den Eingabe-Ganzzahlen zu definieren.

Im Bereich der rechnerischen Komplexitätstheorie wird die Eingabe normalerweise als binäre Zeichenfolge (oder als Zeichenfolge in einem festen Alphabet) angegeben, und die Variable ist normalerweise die Anzahl der Bits in dieser Zeichenfolge. Diese Maßnahme hängt von der spezifischen Codierung der Eingabe ab, die angegeben werden muss. Wenn die Eingabe beispielsweise eine Ganzzahl ist, die mit unärer Codierung angegeben wurde, erfordert die Testteilung nur Θ (n^1/2) Rechenoperationen; Wenn jedoch derselbe Eingang binär (oder eine größere Basis) angegeben wird, steigt die Komplexität auf Θ (2)^{n / 2}) Operationen, nicht weil der Algorithmus zusätzliche Zeit benötigt, sondern weil die Anzahl der Bits in der Eingabe n ist exponentiell kleiner geworden. In die andere Richtung prägnante Schaltkreise sind kompakte Darstellungen einer begrenzten Klasse von Graphen, die exponentiell weniger Platz einnehmen als gewöhnliche Darstellungen wie Adjazenzlisten. Viele Graph-Algorithmen auf prägnanten Schaltungen sind EXPTIME-vollständig, während die gleichen Probleme, die mit herkömmlichen Darstellungen ausgedrückt werden, nur P-vollständig sind, da die Eingänge prägnanter Schaltungen kleinere Codierungen aufweisen.

Ausgabesensitive Algorithmen definieren ihre Komplexität nicht nur in Bezug auf ihre Eingabe, sondern auch in Bezug auf ihre Ausgabe. Zum Beispiel kann Chans Algorithmus die konvexe Hülle einer Menge von Punkten in O berechnen (n Log h) Zeit, wo n ist die Anzahl der Punkte in der Eingabe und h ist die Anzahl der Punkte in der resultierenden konvexen Hülle, einer Teilmenge der Eingabepunkte. Weil jeder Eingabepunkt könnte In der konvexen Hülle würde eine Analyse nur hinsichtlich der Eingabe das weniger genaue O ergeben (n Log n) Zeit.

Die Komplexität einiger Algorithmen hängt nicht nur von den Parametern der Eingabe ab, sondern auch von den Parametern der Maschine, auf der der Algorithmus ausgeführt wird. Wie in #Metric unten erwähnt, ist dies typisch für die Analyse von Algorithmen, die auf Systemen mit festen Cache-Hierarchien ausgeführt werden, wobei die Komplexität von Parametern wie Cache-Größe und Blockgröße abhängen kann.

Abstrakte Maschine[edit]

Um einen Algorithmus genau zu analysieren, muss man annehmen, dass er von einer bestimmten abstrakten Maschine ausgeführt wird. Beispielsweise kann auf einer Direktzugriffsmaschine die binäre Suche verwendet werden, um einen bestimmten Wert in einer sortierten Liste nur in O (Protokoll) schnell zu finden n) Vergleiche, wo n ist die Anzahl der Elemente in der Liste; Auf einer Turing-Maschine ist dies nicht möglich, da sie jeweils nur eine Speicherzelle bewegen kann und daher Ω benötigt (n) Schritte, um sogar einen beliebigen Wert in der Liste zu erreichen.

Darüber hinaus definieren unterschiedliche abstrakte Maschinen unterschiedliche Primitive Operationen, die Operationen sind, die in konstanter Zeit ausgeführt werden können. Einige Maschinen, wie Turing-Maschinen, erlauben jeweils nur das Lesen oder Schreiben eines Bits. Diese werden als Bitoperationen bezeichnet, und die Anzahl der zur Lösung eines Problems erforderlichen Bitoperationen wird als its bezeichnet Bit Komplexität.^[1] Die Bitkomplexität lässt sich auf jede Maschine verallgemeinern, auf der die Speicherzellen eine feste Größe haben, die nicht von der Eingabe abhängt. Aus diesem Grund werden Algorithmen, die Zahlen manipulieren, die viel größer sind als die Register auf normalen PCs, typischerweise hinsichtlich ihrer Bitkomplexität analysiert. Anders ausgedrückt ist die Bitkomplexität die Komplexität, wenn die Wortgröße ein einzelnes Bit ist, wobei die Wortgröße die Größe jeder Speicherzelle und jedes Registers ist.^[2]

Ein anderes häufig verwendetes Modell enthält Wörter mit Protokoll n Bits, wo n ist eine Variable abhängig von der Eingabe. In Graph-Algorithmen wird beispielsweise normalerweise angenommen, dass die Scheitelpunkte von 1 bis 1 nummeriert sind n und dass jede Speicherzelle einen dieser Werte enthalten kann, so dass sie sich auf einen beliebigen Scheitelpunkt beziehen können. Dies ist bei Problemen gerechtfertigt, bei denen der Eingang Ω verwendet (n) Speicherwörter, da auf realen Computern die Speicherzellen- und Registergröße typischerweise ausgewählt wird, um jedes Wort im Speicher indizieren zu können. Es wird angenommen, dass Operationen an diesen Wörtern, wie Kopien und arithmetische Operationen, in konstanter Zeit und nicht in O (log) ausgeführt werden n) Zeit. Die Anzahl der Wortoperationen, die zur Lösung eines Problems in diesem Modell erforderlich sind, wird manchmal als seine bezeichnet Wortkomplexität.

In der rechnergestützten Komplexitätstheorie definieren Forscher Komplexitätsklassen absichtlich so, dass sie maschinenunabhängig sind – das heißt, wenn ein Problem in einer bestimmten Klasse relativ zu einer bestimmten “vernünftigen” Maschine liegt, liegt es in dieser Klasse relativ zu einer beliebigen “vernünftige” Maschine. Wie oben erwähnt, hängt die zeitliche Komplexität der binären Suche beispielsweise davon ab, ob eine Turing-Maschine oder eine Direktzugriffsmaschine verwendet wird. aber unabhängig von der Maschinenwahl liegt es in P., die Klasse der Polynom-Zeit-Algorithmen. Im Allgemeinen, P. wird als maschinenunabhängige Klasse angesehen, da angenommen werden kann, dass jede Operation, die in Polynomzeit simuliert werden kann, eine konstante Zeit erfordert, da sie als Unterprogramm behandelt werden kann, ohne die gebundene Polynomzeit zu überschreiten.

Oracle-Maschinen sind Maschinen mit einer bestimmten Operation, die sie in konstanter Zeit ausführen können. Diese Operation kann beliebig komplex sein und die Komplexität der auf der Maschine ausgeführten Algorithmen dramatisch beeinflussen. Wenn man zum Beispiel ein Orakel hat, um ein NP-vollständiges Problem zu lösen, dann ist jedes Problem in NP kann in Polynomzeit gelöst werden (während ohne das Orakel für viele dieser Probleme kein Polynomzeitalgorithmus bekannt ist). Oracle-Maschinen sind unpraktisch zu konstruieren, aber theoretisch nützlich, um zu bestimmen, welche Proof-Techniken effektiv sind.

Metrik wird gemessen[edit]

Es ist typisch, ohne Einschränkung zu sagen, dass für die Einfügesortierung O erforderlich ist (n²) Zeit; Es ist jedoch nicht sinnvoll zu sagen, dass die Bitkomplexität der Einfügesortierung O ist (n²), es sei denn, die zu sortierenden Elemente haben eine konstante Größe. Wenn angenommen wird, dass die Elemente ganze Zahlen zwischen 1 und 1 sind n, dann die Wortkomplexität, bei der Wörter log haben n Bits wären O (n²), aber es ist vorzuziehen, ein Modell zu haben, das das Sortieren anderer Listen als Listen kleiner Ganzzahlen ermöglicht, z. B. Listen von Zeichenfolgen. In diesem Fall ist es vorzuziehen, anstelle der Anzahl der Zeitschritte, die die abstrakte Maschine ausführt, eine bestimmte Metrik zu definieren, die für das jeweilige Problem geeignet ist. Bei Vergleichssortieralgorithmen, bei denen die Eingabe nur anhand von Vergleichen untersucht und nur anhand von Austauschen (Swaps) geändert wird, ist die typische Metrik entweder die Anzahl der durchgeführten Elementvergleiche, die Anzahl der durchgeführten Elementaustausche oder die Summe dieser. Mithilfe dieser Metriken können verschiedene Vergleichssortieralgorithmen verglichen werden. Für einen nützlichen Vergleich mit Nichtvergleichssortieralgorithmen wie der Radix-Sortierung muss jedoch eine andere Metrik verwendet und der Satz von Elementen eingeschränkt werden.

Da Festplattenoperationen um Größenordnungen langsamer sind als der Zugriff auf den Hauptspeicher, ist die typische Metrik, die in festplattenbasierten Algorithmen verwendet wird, die Anzahl der Festplattensuchen oder die Anzahl der von der Festplatte gelesenen Blöcke, die sowohl von der Eingabe als auch von den Parametern der Festplatte abhängen Scheibe. RAM-Zugriffe und CPU-Operationen sind “kostenlos”. In ähnlicher Weise werden in vielen Modellen, die zum Studieren von Datenstrukturen verwendet werden, wie z. B. dem Cache-Vergessen-Modell, Operationen an zwischengespeicherten Daten als “frei” angesehen, da sie in der Praxis typischerweise um Größenordnungen schneller sind als der Zugriff auf den Hauptspeicher. Folglich wird als typische Metrik die Anzahl der Cache-Fehler verwendet, die sowohl von der Eingabe als auch von den Parametern des Caches abhängt.

Verweise[edit]