Ich vergleiche zwei Algorithmen, die bestimmen, ob eine Zahl eine Primzahl ist. Ich betrachte die Obergrenze für die Zeitkomplexität, kann aber den Zeitkomplexitätsunterschied zwischen beiden nicht verstehen, obwohl in der Praxis ein Algorithmus schneller als der andere ist.

Dieser Pseudocode läuft in der Exponentialzeit O (2 ^ n):

Prime(n):
    for i in range(2, n-1)
        if n % i == 0
            return False
    return True

Dieser Pseudocode läuft in der Hälfte der Zeit wie im vorherigen Beispiel, aber ich habe Schwierigkeiten zu verstehen, ob die Zeitkomplexität immer noch O (2 ^ n) ist oder nicht:

Prime(n):
    for i in range(2, (n/2+1))
        if n % i == 0
            return False
    return True
0
Justin 19 Jän. 2019 im 01:59

3 Antworten

Beste Antwort

Als einfache Vorstellung davon, worum es bei Big-O (Big-O) und Big-Θ (Big-Theta) geht, geht es darum, wie sich die Anzahl der Operationen ändert, die Sie ausführen müssen, wenn Sie das Problem erheblich vergrößern (z Beispiel um den Faktor 2).

Die lineare Zeitkomplexität bedeutet, dass Sie die Größe um den Faktor 2 erhöhen. Die Anzahl der Schritte, die Sie ausführen müssen, erhöht sich ebenfalls um das Zweifache. Dies wird als Θ(n) bezeichnet und ist oft austauschbar, aber nicht genau O(n) (der Unterschied zwischen O und Θ besteht darin, dass O nur eine Obergrenze liefert, aber {{ X5}} garantiert sowohl obere als auch untere Schranken).

Die logarithmische Zeitkomplexität (Θ(log(N))) bedeutet, dass sich die Anzahl der Schritte, die Sie ausführen müssen, um eine feste Anzahl von Operationen erhöht, wenn Sie die Größe um den Faktor 2 erhöhen. Mit der binären Suche können Sie beispielsweise ein bestimmtes Element in einer doppelt so langen Liste mit nur einer Erzschleifeniteration finden.

In ähnlicher Weise bedeutet die exponentielle Zeitkomplexität (Θ(a^N) für eine Konstante a > 1), dass Sie a mal mehr Operationen benötigen, wenn Sie diese Größe des Problems nur um 1 erhöhen. (Beachten Sie, dass es einen subtilen Unterschied zwischen Θ(2^N) und 2^Θ(N) gibt und der zweite allgemeiner ist. Beide liegen innerhalb der Exponentialzeit, aber keiner von beiden deckt alles ab, siehe wiki für weitere Details)

Beachten Sie, dass diese Definition wesentlich davon abhängt, wie Sie "die Größe der Aufgabe" definieren.

Wie @DavidEisenstat richtig hervorhob, gibt es zwei mögliche Zusammenhänge, in denen Ihr Algorithmus gesehen werden kann:

  1. Einige Zahlen mit fester Breite (zum Beispiel 32-Bit-Zahlen). In einem solchen Kontext ist der Wert, der selbst getestet wird, ein offensichtliches Maß für die Komplexität des Primetest-Algorithmus. In diesem Fall ist Ihr Algorithmus linear.

  2. In der Praxis gibt es viele Kontexte, in denen Primärtestalgorithmen für wirklich große Zahlen funktionieren sollten. Zum Beispiel viele heute verwendete Krypto-Algorithmen (wie Diffie-Hellman-Schlüsselaustausch oder RSA) basieren auf sehr großen Primzahlen wie 512-Bit, 1024 -Bits und so weiter. Auch in diesem Zusammenhang wird die Sicherheit eher an der Anzahl dieser Bits als an einem bestimmten Primwert gemessen. In solchen Kontexten ist die Anzahl der Bits ein natürlicher Weg, um die Größe der Aufgabe zu messen. Und jetzt stellt sich die Frage: Wie viele Operationen müssen wir ausführen, um einen Wert bekannter Größe in Bits mit Ihrem Algorithmus zu überprüfen? Wenn der Wert N m Bits hat, handelt es sich offensichtlich um N ≈ 2^m. Ihr Algorithmus aus linearem Θ(N) wird also in exponentielles 2^Θ(m) konvertiert. Mit anderen Worten, um das Problem für einen Wert zu lösen, der nur 1 Bit länger ist, müssen Sie ungefähr zweimal mehr arbeiten.

3
SergGr 19 Jän. 2019 im 00:05

Exponentiell versus linear ist eine Frage der Darstellung der Eingabe und des Maschinenmodells. Wenn die Eingabe unär dargestellt wird (z. B. wird 7 als 1111111 gesendet) und die Maschine eine konstante Zeitteilung auf Zahlen durchführen kann, dann ist der Algorithmus eine lineare Zeit. Eine binäre Darstellung von n verwendet jedoch ungefähr lg n Bits, und die Größe n hat eine exponentielle Beziehung zu lg n (n = 2 ^ (lg n)).

Da die Anzahl der Schleifeniterationen für beide Lösungen innerhalb eines konstanten Faktors liegt, gehören sie zur gleichen großen O-Klasse, Theta (n). Dies ist exponentiell, wenn der Eingang lg n Bits hat, und linear, wenn er n hat.

1
David Eisenstat 18 Jän. 2019 im 23:21

Ich hoffe, das wird Ihnen erklären, warum sie tatsächlich linear sind.

Angenommen, Sie rufen function auf und sehen, wie oft sie ausgeführt werden

Prime(n): # 1 time 
    for i in range(2, n-1) #n-1-1 times
        if n % i == 0  # 1 time 
            return False # 1 time

    return True # 1 time


# overall -> n

Prime(n): # Time
    for i in range(2, (n/2+1)) # n//(2+1) -1-1 time
        if n % i == 0 # 1 time
            return False # 1 time
    return True # 1 time

# overall -> n/2 times -> n times

Dies zeigt, dass Primzahl eine lineare Funktion ist

O (n ^ 2) kann an einem Codeblock liegen, in dem diese Funktion aufgerufen wird.

0
sahasrara62 18 Jän. 2019 im 23:18