WikiDer > Komplexitätsgrad

Complexiteitsgraad

Grundsätze

Computational Complexity Theory

Modelle

Theorien

Das Komplexitätsgrad von einem bestimmten Algorithmus verhält sich der Algorithmus mit zunehmender Größe des zu lösenden Problems.

Prinzipien der Komplexität

Die Basis

Die Untersuchung der Komplexität eines gegebenen Algorithmus ist eine der zentralen Aktivitäten des Zweiges der Mathematik und Informatik was bekannt ist als Komplexitätstheorie. Die Komplexitätstheorie untersucht unter anderem, wie genau ein vorgegebenes mathematisches Problem gelöst wird – wörtlich im Sinne von "Welche Schritte müssen von einer Problemstellung zur Lösung gehen?"

Um diese Frage zu beantworten, werden Berechnungen in der Komplexitätstheorie mit einem Modell beschrieben, wie Berechnungen ablaufen: dem sogenannten Turing Maschine. In diesem Modell – das einen sehr mechanischen Lösungsansatz verfolgt – wird jede Berechnung in sehr kleine Schritte zerlegt. Die Anzahl der Schritte, die erforderlich sind, um zu einer Lösung des Problems zu gelangen, ist die Zeitkomplexität des Problems.

Außer der Zeitkomplexität man studiert manchmal auch die Raumkomplexität. Die Platzkomplexität betrifft die Beziehung zwischen der Problemgröße und der bei der Berechnung verwendeten Speichermenge. Wenn man ohne weitere Angabe von Komplexität spricht, ist meist in erster Linie die Zeitkomplexität gemeint.

Algorithmen

Die Komplexitätstheorie betrachtet jedoch die Komplexität von Problemen in einem allgemeineren Sinne als jedes einzelne Problem. Es wäre auch nicht möglich, jede einzelne Aufgabe zu betrachten: Denken Sie daran, dass alle zwei natürliche Zahlen summieren sich und es gibt endlose Probleme zu lösen. Darüber hinaus ist es auch nicht sehr interessant, (zum Beispiel) jede einzelne Ergänzung zu betrachten.

Die Komplexitätstheorie ist viel mehr daran interessiert, die Komplexität ganzer Klassen von Problemen auf einmal zu bestimmen - nicht "Was ist die Komplexität der Lösung von 2 3", sondern "Was ist die Komplexität einer allgemeinen Methode zur Lösung zweier natürlicher Zahlen? ". Glücklicherweise erlaubt das Modell der Turing-Maschine dies: Es ist möglich, eine Turing-Maschine für a Programm zu schreiben, wieder in Form von ein paar einfachen Schritten, die sich oft wiederholen, die eine ganze Klasse von Problemen lösen. Die Komplexitätstheorie untersucht die Komplexität dieser Art von "Programmen", allgemeinen Roadmaps, die eine ganze Klasse von Problemen lösen. So ein Schritt-für-Schritt-Plan ist übrigens Algorithmus erwähnt.

Relative Komplexität

Natürlich ist es bei der Untersuchung einer ganzen Klasse von Problemen nicht möglich, eine direkte Aussage über die Komplexität zu treffen. Wie auch immer Sie es betrachten, das Produkt ausführen

234456597356 * 976895793565

dauert länger als der Betrieb des Produkts

5 * 6

obwohl die allgemeine Methode dasselbe zu lösen.

Um allgemeinere Aussagen über die Komplexität von Algorithmen treffen zu können, drückt die Komplexitätstheorie die Komplexität eines Algorithmus durch die Anzahl der Schritte aus, die ein gegebener Algorithmus im Verhältnis zur Größe der Eingabe benötigt.

Dies erfordert natürlich, dass es für jede Eingabe ein Konzept der "Größe" gibt. Zum Glück ist das kein Problem – es Turing-Maschinenmodell ist so, dass jeder Eintrag eine Größe hat Muss (die erforderliche Anzahl von Positionen auf dem Band). Die Komplexität eines gegebenen Algorithmus wird nun in der Anzahl der Schritte ausgedrückt, die der Algorithmus im Verhältnis zur Größe der Eingabe ausführen muss, um zu einer Lösung zu gelangen. Zum Beispiel, wenn eine Eingabe die Größe ist

{Displaystil N}

dann könnte man sagen, dass die Komplexität eines gegebenen Algorithmus gleich

{Displaystil N^{2}-3N 7}

Komplexität und Größenordnungen

Größenordnungen

Wie oben beschrieben, wird die Komplexität eines gegebenen Algorithmus durch die Größe der Eingabe in diesen Algorithmus ausgedrückt. Für jeden Algorithmus A führt dies zu einem Ausdruck, der die Komplexität C(A) von A repräsentiert. Die Existenz solcher Ausdrücke ermöglicht es, Algorithmen hinsichtlich ihrer Komplexität miteinander zu vergleichen.

Neben dem direkten Vergleich bietet die Komplexitätstheorie Aber auch die Verwendung einer etwas gröberen Klassifikation von Algorithmen nach Komplexität, der sogenannten Größenordnungen. Wie wir sehen werden, sind Größenordnungen nicht sehr genau. Sie haben aber den Vorteil, dass man Algorithmen grob in eine klare Hierarchie von Klassen von Algorithmen. Und Mathematiker mögen das, weil eine solche Hierarchie es ermöglicht, in einem abstrakteren Sinne über all die unendlich vielen Algorithmen zu denken, die man sich vorstellen könnte.

In der Größenordnung eines Algorithmus A wird nur der Teil des Ausdrucks C(A) berücksichtigt, der die Größe von C(A) am meisten bestimmt. Früher hatten wir das Beispiel, dass die exakte Komplexität eines Algorithmus gleich

{Displaystil N^{2}-3N 7}

dann ist die Größenordnung dieses Algorithmus einfach gleich ${Displaystil N^{2}}$ . Wir sagen dann, dass der Algorithmus quadratisch ist in der Größenordnung. Das gleiche gilt für linear Algorithmen (Größenordnung ${Displaystil N}$ ), kubisch ( ${Displaystil N^{3}}$ ), vierte Potenz ( ${Displaystil N^{4}}$ ) sogar exponentiell (beispielsweise ${Displaystil 2^{N}}$ ).

Bestellbezeichnungen

Es gibt mehrere Möglichkeiten, Größenordnungen von Algorithmen darzustellen, die alle a Polynom Ausdruck. Diese Notationen haben jedoch alle ihre eigene Bedeutung, ihre eigene Idee, die zum Ausdruck kommt.

Die verwendeten Notationen der Hauptordnung weisen darauf hin, dass ein gegebener Algorithmus maximal hat eine gewisse Komplexität, mindestens hat eine gewisse Komplexität und genau hat eine gewisse Komplexität.

Begrenzung von oben

sehen Big-O-Notation für den Hauptartikel zu diesem Thema.

Die Begrenzung von oben drückt aus, dass ein gegebener Algorithmus A maximal hat eine gewisse Komplexität. Diese Grenze von A wird oft durch eine Notation angegeben, die im Mathematik die Notation "großes O" heißt (aber eigentlich ist es kein O, sondern ein großes Omikron, der griechische Buchstabe).

Die Groß-O-Notation hat die folgende Form:

{Anzeigestil A=O(f(N))}

was bedeutet die Komplexität von A ist höchstens ein Ausdruck f(N); dieser Ausdruck ist ein Polynom in N, wobei N der Betrag der Eingabe ist.

Formal ist die Bedeutung der Big-O-Notation wie folgt definiert:

{displaystyle A=O(g(n))Linksrechtspfeil existiert _{c>0}existiert _{Nin mathbb {N} }fürall_{ngeq N}:0leq A(n)leq ccdot g(n)}

Obiges bedeutet: ab einer bestimmten Eingabegröße N wird A von oben nach oben begrenzt durch die Funktion g, mal einen konstanten Faktor c. Mit anderen Worten: Ab Problemgröße N ist der Wert g(n) immer größer als die Anzahl der Schritte, die A benötigt, um ein Problem mit Eingangsgröße n zu lösen. Somit ist g eine obere Schranke für die Komplexität von A.

Gemeinsame O-Funktionen sind

O(1); (Zeit unabhängig von der Größe des Problems; genauer: die Zeit überschreitet nie eine bestimmte Obergrenze, egal wie groß das Problem ist)
O(log n), (proportional zum Logarithmus von nein, wenn nein um eine Größenordnung erhöht sich die Zeit um eine Konstante)
Auf), (Zeit proportional zu nein)
O(n log n), (Produkt der beiden vorherigen - das ist die Komplexität der Besten Sortieralgorithmen die sind bekannt)
Auf²) (die Zeit wächst quadratisch mit der Größe des Problems)
O(2^nein) (die Zeit nimmt exponentiell mit der Größe des Problems zu)

Grenze von unten

Analog zur Big-O-Notation für die Grenze von oben haben wir auch eine Notation, die angibt, dass ein Algorithmus mindestens hat eine gewisse Komplexität: die Large-Omega-Notation. Es hat eine ähnliche Form wie die Big-O-Notation:

{Anzeigestil A=Omega (f(N))}

Die formale Definition dieser Notation lautet wie folgt:

{displaystyle A=Omega (g(n))Linksrechtspfeil existiert _{c>0}existiert _{Nin mathbb {N} }forall _{ngeq N}:0leq ccdot g(n)leq A(n)}

Mit anderen Worten, ab einer bestimmten Eingangsgröße N wird A nach unten durch die Funktion g, mal einen konstanten Faktor c, begrenzt.

Die bekannten Größenordnungen, die wir bei der Large-O-Notation gesehen haben, sind auch in der Large-Omega-Notation üblich.

Genaue Bestellung

Schließlich gibt es die genaue Grenze (innerhalb einer bestimmten, konstanten Intervall Abweichung). Dazu wird ein großes Theta verwendet, und eine Grenze großer Theta-Ordnung ist eigentlich sowohl eine Grenze von oben als auch von unten.

Die formale Definition dieser Grenze lautet:

{displaystyle A=Theta (g(n))Leftrightarrow existiert _{c_{1},c_{2}>0}existiert _{Nin mathbb {N} }forall _{ngeq N}:0leq c_{1}cdot g (n)leq A(n)leq c_{2}cdot g(n)}

Mit anderen Worten, ab einer bestimmten Eingangsgröße N wird A von oben und von unten begrenzt durch die Funktion g, mit einem "Bewegungsraum" bestimmt durch ${displaystyle c_{1}}$ und ${displaystyle c_{2}}$ .

P und NP

Neben der obigen Einteilung in eine Komplexitätshierarchie gibt es in der Komplexitätstheorie eine weitere Einteilung: einfach und schwer Probleme.

Die einfachen Probleme sind diejenigen, für die ein Algorithmus mit einer Zeitkomplexität bekannt ist, die ein polynomischer Ausdruck in der Größe der Eingabe ist. Diese Probleme bilden zusammen die Sammlung P von Polynomialzeit lösbare Probleme.

Die schwierigen Probleme sind die Probleme, für die ein solcher Algorithmus nicht ist bekannt.

Für viele Probleme ist kein schneller Algorithmus bekannt; Einiges davon ist bewiesen, dass ein solcher Algorithmus nicht existieren kann. Für eine Vielzahl dieser „rechentechnisch schwierigen“ Probleme, die nicht mit Sicherheit bestimmt werden können, sind jedoch Algorithmen bekannt Beste, aber a gut Lösung geben, sogenannte heuristisch Methoden.

Eine besondere Klasse bilden die NP Probleme. Obwohl für viele dieser Probleme kein polynomialer Algorithmus bekannt ist, kann für alle NP-Probleme eine gegebene Kandidatenlösung in polynomieller Zeit auf Korrektheit überprüft werden (NP steht für 'nicht-deterministisches Polynom').

Innerhalb von NP ist die NP-voll Probleme einer bestimmten Gruppe. Es wurde bewiesen, dass jedes Problem aus der Menge der NP-Probleme in polynomieller Zeit in a NP-vollständig Problem. Das heißt, wenn Sie einen Algorithmus haben, um ein einzelnes NP-vollständiges Problem zu lösen, können Sie diesen Algorithmus verwenden, um jeder um das Problem in NP zu lösen. Wenn also jemals ein polynomialer Algorithmus für ein NP-vollständiges Problem gefunden wird, könnte dieser alle NP-Probleme in polynomieller Zeit lösen, woraus folgen würde, dass die Menge NP gleich der Menge P ist. Dies ist eine der schwierigeren Forschungsgebiete der Komplexitätstheorie.

Beispiele für NP-vollständige Probleme sind die Probleme mit dem Handelsreisenden und der Erfüllungsproblem.

Siehe auch

Navigation