Algorithmus Komplexität mit Eingabe ist Fix-Größe

Question

Ich fand einige Hinweise über große O-Notation, aber soweit ich verstehen kann Algorithmus Komplexität ist eine Funktion der Größe der Eingabedaten. Wenn die Komplexität der Blasensortierung beispielsweise O(n^2) ist, ist n die Größe des Eingangsarrays. Recht?

Aber, wie kann ich die Komplexität des Algorithmus bestimmen, der feste Eingabegröße hat und von den Werten der Eingabe abhängt. Zum Beispiel würde das Finden des größten gemeinsamen Teilers (GCD) wie folgt aussehen:

def GCD(x, y): 
    while x != y: 
     if x < y: 
      x, y = y - x, x 
     else: 
      x, y = x - y, x 
    return x 

Was ist die Komplexität dieses Algorithmus? Und wie ist es bestimmt?

Edit: Geänderter Name der Funktion und korrigierter Name des Algorithmus. ShreevatsaR, danke für das Aufzeigen.

Answer 1

Die Leute spielen ein bisschen schnell und locker mit Big-O-Notation. Im Fall von GCD tun sie dies im Allgemeinen auf zwei Arten:

1) Sie haben Recht, algorithmische Komplexität und daher große O-Notation, sollte in Bezug auf die Größe in Bits des Eingangs angegeben werden , nicht in Bezug auf die Werte der Eingabe. So sind P, NP und so weiter definiert. Unter der Annahme einer binären Eingabe und beliebig großen Zahlen (wie eine BigNum-Darstellung) und N der Anzahl der Bits der Eingabe benötigt Ihr GCD höchstens 2^N Subtraktionen, von denen jeder Zeit O (N) benötigt, um über jede Ziffer des zu laufen Zahlen werden subtrahiert. Also ist es O (N * 2^N). GCD kann natürlich viel schneller durchgeführt werden, wenn Sie Division statt Subtraktion verwenden: O (N^2).

Also, wenn wir das testing primality was proved in 2002 to be done in polynomial time sagen, das ist die technische Definition der Komplexität, und wir bedeuten Polynom in der Anzahl der Ziffern (was der schwierige Teil ist), nicht Polynom in der Eingangsnummer selbst (was trivial ist einfach zu tun in "sub-linearer Zeit" mit Trial Division.

Aber in der Praxis ist es für Algorithmen, die eine feste Anzahl ganzzahliger Eingaben benötigen, bequemer, über Komplexität zu sprechen, als wäre N die Eingabe selbst, nicht die Größe der Eingabe. Es ist nicht schädlich, solange Sie klar sind, was Sie in mehrdeutigen Fällen meinen.

2) In der Praxis sind Integer-Eingaben oft feste Größe, 32 Bit oder was auch immer, und Operationen auf ihnen wie Addition, Multiplikation und Division sind O (1) Zeit. Wir verwenden diese Fakten selektiv in unserer Bestellanalyse. Wenn Ihr GCD-Programm nur Eingänge bis zu (2^32-1) akzeptiert, dann ist es technisch O (1). Es hat eine feste Obergrenze für die Laufzeit. Ende der Analyse.

Obwohl technisch korrekt, das ist keine sehr nützliche Analyse. Fast alles, was Sie auf einem echten Computer tun, ist O (1) auf der gleichen Basis, dass die Größe des Problems durch die Hardware eingeschränkt ist.

Es ist normalerweise bequemer zu akzeptieren, dass die Addition O (1) ist, da die Zahlen feste Größe sind, aber ignorieren, dass GCD auch O (1) ist, so tun sein Verhalten im Bereich [1, 2^32) erstreckt sich bis ins Unendliche und analysiert es auf dieser Grundlage. Dann, wenn N das Maximum der zwei Eingaben ist, kommt es zu O (N): O (N) Subtraktionen, wobei jede eine konstante Zeit benötigt.

Noch einmal, das ist nicht mehrdeutig, wenn Sie wissen, was die Terms of Reference sind, aber hüte dich davor, die erste Analyse von Euklid Algorithmus mit Division, O (N^2), gegen diese Analyse des Algorithmus mit falsch zu vergleichen Subtraktion, O (N). N ist nicht gleich in jedem, und die Subtraktion ist nicht schneller ;-)

Answer 2

die Eingangsgröße ist die Summe der Größen der Zahlen x und y (z, wie viele Stellen in der Zahl sind)

Answer 3

Big O Komplexität der schlimmste Fall asymptotisch Laufzeitverhalten ist. Es hängt nicht unbedingt von der Eingabegröße (Anzahl der Eingaben) für einen bestimmten Algorithmus ab - obwohl das oft der Fall ist. Mit anderen Worten, es ist die begrenzende Funktion, die die Laufzeit beschreibt, wenn die Eingänge in die Unendlichkeit gebracht werden.

In Ihrem Fall, wenn x oder y unbegrenzt sind, ist auch die asymptotische Laufzeit. Wenn nicht, denke an die Laufzeit, wenn x = 1 und y = Int32.Max?

Answer 4

Die Big-O-Notation sollte angeben, was gemessen wird.

Zum Beispiel misst Big-O-Notation für Sortieralgorithmen in der Regel die Anzahl der Vergleiche.

Ihr GCD-Beispiel kann gemessen werden, indem die Werte von x und y mit der Anzahl der ausgeführten Anweisungen verglichen werden. Lassen Sie uns genauer hinsehen:

def GCD(x, y): 
    while x != y:    # 1 
     if x < y:    # 2 
      x, y = y - x, x  # 3 
     else:     # 4 
      x, y = x - y, x  # 5 
    return x     # 6 

Arbeiten von innen nach außen.

Unabhängig von den Werten x und y werden die Schritte 3 und 5 immer eine Anweisung enthalten. Daher wird die Anweisung if von Schritt 2 immer zwei Anweisungen enthalten. Die schwierigere Frage ist Schritt 1. Bei jeder Iteration wird entweder x oder y um den kleineren Wert verringert. Nehmen wir an, dass x > y. Einer von zwei Dingen passieren:

• Wenn es beginnt, dass x % y == 0, dann wird die Schleife (x/y) - 1 Zeiten und das Programm wird beendet ausgeführt werden.

• Andernfalls wird x(x/y) Zeiten reduziert werden, bevor sie kleiner als y ist, und das Programm wird fortgesetzt.

Sie können ganz einfach die Anzahl von Befehlen für jede gegebene x und y messen.Sie können leicht zeigen, dass Sie für eine gegebene Zahl z nie mehr als z - 1 Subtraktions- oder 2 * (z-1) Anweisungen benötigen. (Denken Sie an gcd(z, 1).)