Wie können wir annehmen, dass grundlegende Operationen mit Zahlen eine konstante Zeit benötigen?

73

Normalerweise kümmern wir uns in Algorithmen nicht um Vergleich, Addition oder Subtraktion von Zahlen - wir gehen davon aus, dass sie in der Zeit ablaufen . Wir nehmen dies beispielsweise an, wenn wir sagen, dass die vergleichsbasierte Sortierung ist. Wenn Zahlen jedoch zu groß sind, um in Register zu passen, stellen wir sie normalerweise als Arrays dar, sodass grundlegende Operationen zusätzliche Berechnungen pro Element erfordern. $O(1)$ $O(n\log n)$

Gibt es einen Beweis dafür, dass der Vergleich zweier Zahlen (oder anderer primitiver arithmetischer Funktionen) in ? Wenn nicht, warum sagen wir dann, dass die vergleichsbasierte Sortierung ? $O(1)$ $O(n\log n)$

Ich dieses Problem auftreten , wenn ich eine SO Frage beantwortet , und ich erkennen , dass mein Algorithmus nicht ist , da früher oder später ich mit Big-int umgehen sollte, auch war es nicht Pseudopolynomiell Algorithmus, es war . $O(n)$ $P$

algorithms complexity-theory algorithm-analysis time-complexity reference-question Raphael
quelle

3

Wenn Sie die Komplexität beim Vergleichen von Zahlen zählen möchten, sollten Sie auch Ihre Komplexitätsgrenzen in Bezug auf die Bitgröße der Eingabe schreiben. So gegebenen

Bit - Zahlen, die Bitgröße des Eingangs ist

und Sortierung kann erfolgen in Zeit.

N

$N$

w

$w$

n = N w

$n=Nw$

O (N w \log N) = O (n \log n)

$O(Nw \log N) = O(n \log n)$

Sasho Nikolov

2

Grundsätzlich gibt es zwei "Bereiche" oder "Regime" der Komplexitätsforschung. Im Allgemeinen werden -Operationen für Operationen mit "fester Breite" angenommen, was eine vernünftige Annäherung für die meisten Computersprachen ist, die Zahlenrepräsentationen mit fester Breite aufweisen, einschließlich für Gleitkommazahlen, z. B. 2-4 Bytes (siehe z. B. IEEE-Standards). dann gibt es "Arithmetik mit willkürlicher Genauigkeit", bei der Zahlen eine willkürliche Größe haben und die Komplexität von Operationen sorgfältiger / genauer untersucht werden. Der erstere Kontext ist mehr in der angewandten Analyse und der letztere ist mehr in der theoretischen / abstrakten Analyse.

O (1)

$O(1)$

vzn

75

Für Leute wie mich, die Algorithmen für ihren Lebensunterhalt studieren, ist das Standardrechenmodell des 21. Jahrhunderts der Integer-RAM . Das Modell soll das Verhalten realer Computer genauer widerspiegeln als das Modell der Turing-Maschine. Reale Computer verarbeiten Mehrbit-Ganzzahlen mit paralleler Hardware in konstanter Zeit. keine willkürlichen ganzen Zahlen, aber (weil die Wortgröße im Laufe der Zeit stetig wächst) auch keine ganzen Zahlen mit fester Größe .

Das Modell hängt von einem einzelnen Parameter , der als Wortgröße bezeichnet wird . Jede Speicheradresse enthält eine einzelne Bit-Ganzzahl oder ein einzelnes Wort . In diesem Modell ist die Eingabegröße die Anzahl der Wörter in der Eingabe, und die Laufzeit eines Algorithmus ist die Anzahl der Operationen an Wörtern . Standard arithmetische Operationen (Addition, Subtraktion, Multiplikation, Division der ganzen Zahl, Rest, Vergleich) und boolesche Operationen (bitweise AND-, OR-, XOR-, Shift, drehen) auf Wörtern benötigen Zeit , nach Definition . $w$ $w$ $n$ $O(1)$

Formal ist die Wortgröße $w$ für die Analyse von Algorithmen in diesem Modell KEINE Konstante . Um das Modell mit der Intuition in Einklang zu bringen, benötigen wir , da wir sonst nicht einmal die ganze Zahl in einem einzigen Wort speichern können . Bei den meisten nichtnumerischen Algorithmen ist die Laufzeit jedoch unabhängig von , da diese Algorithmen die zugrunde liegende binäre Darstellung ihrer Eingabe nicht berücksichtigen. Mergesort und Heapsort werden beide in . Median-of-3-Quicksort läuft in $w \ge \log_2 n$ $n$ $w$ $O(n\log n)$ Zeit im schlimmsten Fall. Eine bemerkenswerte Ausnahme ist die binäre Radix-Sortierung, die in der -Zeit ausgeführt wird. $O(n^2)$ $O(nw)$

Wenn Sie einstellen, erhalten Sie das traditionelle logarithmisch kostenpflichtige RAM-Modell. Einige Ganzzahl-RAM-Algorithmen sind jedoch für größere Wortgrößen ausgelegt, wie der Linear-Time-Ganzzahl-Sortieralgorithmus von Andersson et al. erfordert . $w = \Theta(\log n)$ $w = \Omega(\log^{2+\varepsilon} n)$

Für viele in der Praxis auftretende Algorithmen ist die Wortgröße einfach kein Problem, und wir können (und können) auf das weitaus einfachere RAM-Modell mit einheitlichen Kosten zurückgreifen. Die einzige ernsthafte Schwierigkeit ist die verschachtelte Multiplikation, mit der sehr große ganze Zahlen sehr schnell erstellt werden können. Wenn wir mit beliebigen ganzen Zahlen in konstanter Zeit rechnen könnten, könnten wir jedes Problem in PSPACE in polynomialer Zeit lösen . $w$

Update: Ich sollte auch erwähnen, dass es Ausnahmen zum "Standardmodell" gibt, wie den Ganzzahlmultiplikationsalgorithmus von Fürer , der Multitape-Turing-Maschinen (oder äquivalent das "Bit-RAM") verwendet, und die meisten geometrischen Algorithmen, die theoretisch analysiert werden sauberes aber idealisiertes "echtes RAM" Modell .

Ja, das ist eine Dose Würmer.

JeffE
quelle

3

Ich weiß, dass ich nur wählen soll, kann mich aber nicht davon abhalten, es zu sagen: Dies ist die beste Antwort. Der Trick besteht darin, dass (1) arithmetische Operationen per Definition eine konstante Zeit sind und dies in Ordnung ist, da Sie theoretisch ein beliebiges Modell auswählen können und (2) Sie einige Gründe für die Auswahl eines bestimmten Modells haben sollten und diese Antwort erklärt, was sie sind.

rgrig

Ich stimme rgig zu (auch ich soll nur abstimmen), aber ein kleines Problem ist, dass die Eingabegröße nicht mit den eingegebenen Zahlen zusammenhängt. Wenn ich z. B.

Eingaben habe, ist meine größte Zahl

und ich wähle das Rechenmodell so wie ich es mag, wird der pseudo-polynomielle Zeitalgorithmus zu

, oder?

n

$n$

m

$m$

P

$P$

1

Wenn Ihre Eingabe aus Zahlen mit mehr als

Bits besteht, müssen Sie diese , wie im echten Leben, in

Bit-Blöcke aufteilen, um sie an das Modell anzupassen. Wenn Ihre Eingabe beispielsweise aus

ganzen Zahlen zwischen

und

, ist Ihre wahre Eingabegröße

. Somit pseudo-Polynom Laufzeiten wie

Zeit sind noch in der exponentielle Eingangsgröße , wenn

groß ist.

w

$w$

w

$w$

N

$N$

0

$0$

M

$M$

N \log_{w} M = (N \lg M) / (\lg w)

$N\log_w M = (N\lg M)/(\lg w)$

O (N M)

$O(NM)$

M

$M$

JeffE

Gibt es Algorithmen, die im Real RAM-Modell analysiert wurden und keine geheimen "Order Type RAM" -Algorithmen sind? Ich habe noch nie viel darüber nachgedacht, kann mir aber nicht so schnell ein Beispiel einfallen lassen, das es nicht ist.

Louis

1

@ Louis: Ja, viele: Voronoi-Diagramme, kürzeste euklidische Pfade, rekursive Ausschnitte, einfache Partitionsbäume, .... Das beste Beispiel ist jedoch die Gaußsche Eliminierung, die in

-Zeit auf dem realen RAM-Modell (oder dem RAM) ausgeführt wird Ganzzahl-RAM zu Stückkosten, benötigt jedoch

O (n^{3})

$O(n^3)$

O (n^{4})

$O(n^4)$

-Zeit

24

Es kommt nur auf den Kontext an. Wenn wir uns mit der Komplexität von Algorithmen auf Bitebene befassen , sagen wir nicht, dass die Addition von zwei Bit-Zahlen , wir sagen, dass es . Ähnliches gilt für Multiplikation usw. $n$ $O(1)$ $O(n)$

Massimo Cafaro
quelle

In dem Artikel, auf den Sie sich beziehen, heißt es: "Kann auf zwei verschiedene Arten gemessen werden: eine anhand der getesteten oder multiplizierten Ganzzahlen und eine anhand der Anzahl der Binärziffern (Bits) in diesen Ganzzahlen." sollte immer an der Größe der Eingabe gemessen werden.

1

@ SaeedAmiri: es kommt nur auf die verwendete Kodierung an. In dem Artikel, zum Beispiel, wenn der Eingang eine ganze Zahl

angegeben unären Codierung, Versuch der Division nur erfordert

. Dies ist in der Größe der Eingabe polynomisch! Bedeutet dies, dass das Factoring nach Prozessteilen in

? Nein, der Algorithmus ist pseudopolynomiell . Bei Verwendung der allgemeinen binären Codierung erhalten Sie einen exponentiellen Algorithmus, ebenfalls in der Größe der Eingabe. Wie gesagt, geschieht dies, weil die Anzahl der Bits in dem Eingang

exponentiell kleiner geworden ist, was seine Codierung ändert.

n

$n$

θ (n^{1 / 2})

$\theta(n^{1/2})$

P

$P$

n

$n$

Massimo Cafaro

Übrigens können Pseudo-Polynom-Algorithmen tatsächlich nützlich sein, wenn die Größenordnung ihrer Parameter in tatsächlichen Fällen vernünftigerweise niedrig ist. Das bekannteste Beispiel ist wahrscheinlich der Pseudo-Polynom-Algorithmus zur Lösung des Rucksack-Problems.

Massimo Cafaro

Zuerst sollte ich erwähnen, dass Ihre Wiki-Seite, auf die verwiesen wird, nicht gut ist, weil sie keine guten Referenzen hat. Außerdem weiß ich nicht, warum Sie glauben, dass es sich um pseudo-polynomiale Zeitalgorithmen handelt, möglicherweise, weil die Eingabegröße normalerweise ein Engpass ist in diesen fällen? aber ich spreche nicht über sie, ich spreche hauptsächlich über Probleme, die in

selbst wenn man von der Eingabegröße ausgeht, wie etwa Sortieren, weil wir nicht schummeln können und sagen, dass das NPC-Problem in

denke ich, wir sollten es nicht tun Sagen wir, die Sortierung ist

denn, wir haben einen formalen Beweis, um den Vergleich zu ignorieren.

P

$P$

P

$P$

O (n \log n)

$O(n \log n)$

Ich diskutiere Pseudo-Polynom-Algorithmen, um Ihre Aufmerksamkeit auf die Größe der Eingabe zu lenken und Ihnen zu zeigen, dass sie irreführend sein kann. Hier ist ein weiteres Beispiel. Sie erhalten eine natürliche Zahl als Eingabe, z. B.

, und der Algorithmus führt eine Schleife aus, in der er

-Zeitoperationen für

Iterationen ausführt. Die Komplexität dieses einfachen Schleifenalgorithmus, gemessen als Funktion der Eingangsgröße, beträgt

. Da

n

$n$

O (1)

$O(1)$

n

$n$

O (n) = O (2^{l g n})

$O(n) = O(2^{lg n})$

l g n

$lg n$ ist die Eingabegröße, der Algorithmus ist exponentiell in der Eingabegröße! Denk darüber nach. Jetzt verstehen Sie vielleicht, was ich mit "Es kommt nur auf den Kontext an" meine.

Massimo Cafaro

16

Um die Frage wie folgt zu beantworten: Algorithmiker tun dies einfach ziemlich oft unter Verwendung des RAM-Modells. Zum Sortieren wird in vielen Fällen sogar das einfachere Vergleichsmodell analysiert , auf das ich in der verknüpften Antwort etwas näher eingehen werde.

Um die implizite Frage zu beantworten, warum sie es tun: Ich würde sagen, dass dieses Modell für bestimmte Arten von kombinatorischen Algorithmen, bei denen die Zahlen alle "klein" sind und auf realen Maschinen in Register passen, eine ziemlich gute Vorhersagekraft hat.

Um implizite Folgemaßnahmen zu numerischen Algorithmen zu beantworten: Nein, das einfache alte RAM-Modell ist hier nicht der Standard. Auch die Eliminierung nach Gauß kann einige Sorgfalt erfordern. Typischerweise wird für Rangberechnungen das Schwartz-Lemma eingegeben (z. B. Abschnitt 5 hier ). Ein weiteres kanonisches Beispiel ist die Analyse des Ellipsoid-Algorithmus, dessen Analyse einige Sorgfalt erfordert .

Und schließlich: Die Leute haben schon vor kurzem über das Sortieren von Zeichenketten nachgedacht .

Update: Das Problem bei dieser Frage ist, dass "wir" und "vermuten" nicht so genau spezifiziert sind. Ich würde sagen, dass die Leute, die im RAM-Modell arbeiten, keine numerischen Algorithmen oder Komplexitätstheorien anwenden (wo die Bestimmung der Komplexität der Teilung ein gefeiertes Ergebnis war ).

Louis
quelle

Hmmmm, es scheint eine interessante Antwort zu sein ...

Gibt es einen Grund, warum die Frage nicht vollständig beantwortet wird?

Louis

7

$O(1)$ $O(1)$

python -mtimeit "$a * $b"$a $10^{\{1,2,...,66\}}$ $b = 2*$a

$10^{50}$ $\log_{10}(\tt{sys.maxint})$

Dougal
quelle

O (n)

$O(n)$

O (n \cdot \log n \cdot \log m)

$O(n \cdot \log n \cdot \log m)$

7

$O(1)$

$O(\log M)$ $O (N \log N)$ $O (N \log N \log M)$

$M$

Erel Segal-Halevi
quelle

O (\log m)

$O(\log m)$

O (\log n)

$O(\log n)$

m

$m$

O (l o g N)

$O(log N)$

n

$n$

n^{n^{n}}

$n^{n^n}$

Du hast recht, ich habe meine Antwort korrigiert.

Erel Segal-Halevi

4

Ich würde sagen, dass wir normalerweise O (1) -Arithmetikoperationen annehmen, weil wir normalerweise Dinge im Kontext von 32-Bit-Ganzzahlen oder 64-Bit-Ganzzahlen oder IEEE 754-Gleitkommazahlen tun. O (1) ist wahrscheinlich eine ziemlich gute Näherung für diese Art von Arithmetik.

Aber im Allgemeinen stimmt das nicht. Im Allgemeinen benötigen Sie einen Algorithmus, um Addition, Subtraktion, Multiplikation und Division durchzuführen. Boolos, Burgess und Jefferies ' Computability and Logic kommen in den Sinn, um die Beweise dafür in Bezug auf einige verschiedene formale Systeme, rekursive Funktionen und Abacus-Maschinen zumindest in meiner 4. Ausgabe zu verstehen.

Sie können sich die Lambda-Kalkül-Terme für die Subtraktion und Division mit Church Numerals ansehen, um eine leicht verständliche Erklärung dafür zu erhalten, warum diese beiden Operationen nicht O (1) sind. Es ist etwas schwieriger zu sehen, was Addition, Multiplikation und Potenzierung angeht, aber wenn man die Form der Gemeindezahlen selbst betrachtet, ist dies der Fall.

Bruce Ediger
quelle

Wie können wir annehmen, dass grundlegende Operationen mit Zahlen eine konstante Zeit benötigen?

Antworten: