Komplexität der Berechnung

10

Was ist die Komplexität der Berechnung ?nn2,nN

Raphael
quelle
2
Was hast du versucht? Welches Maschinen- und Kostenmodell nehmen Sie an?
Raphael

Antworten:

12

Mit der schnellen Fourier-Transformation können Multiplikationen mit Bit-Zahlen in der Zeit ˜ O ( k ) durchgeführt werden (wobei die Tilde anzeigt, dass wir polylogarithmische Faktoren ignorieren). Durch wiederholtes Quadrieren können wir n n 2 mit O ( log n ) -Multiplikationen berechnen , und jede Multiplikation beinhaltet keine Zahl größer als n n 2 , die ungefähr n 2 log 2 n Bits hat. Die Gesamtzeit beträgt also ˜ O ( n 2 (kO~(k)nn2O(logn)nn2n2log2n .O~(n2(logn)2)=O~(n2)

Micah
quelle
3

Als Antwort auf Kommentare bearbeitet Die Zeit zum Berechnen von kann in die Zeit zerlegt werden, die zum Berechnen von f 1 ( n ) = n 2 erforderlich ist, und die Zeit, die zum Ausführen von n f 1 ( n ) erforderlich ist . Ich gehe davon aus, dass das Multiplizieren einer m- Bit-Zahl mit einer n- Bit-Zahl nach der Schulbuchmethode genau m n Zeit benötigt. Ergänzungen usw. sind konstante Zeit. Als Ergebnis der Berechnung n 2 nimmt log 2f(n)=nn2f1(n)=n2nf1(n)mnmnn2Zeit.log22(n)

Angenommen, wir verwenden die binäre Exponentiation zur Berechnung von . Die binäre Exponentiation führt bei der Berechnung von f ( n ) zwei Arten von Operationen aus : Quadrieren des aktuellen Produkts und Multiplizieren des aktuellen Produkts mit n , je nachdem, ob das aktuelle Bit in der binären Erweiterung von n 2 0 oder 1 ist. Im schlimmsten Fall n 2 ist eine Zweierpotenz ist , so daß binäre Potenzierung wiederholt Quadrate seine aktuelle Produkt , bis er die answer.Note erreicht , dass n 2 ist m ' = 2 log 2 ( nf(n)f(n)nn2n2n2 Bits, so dass die Anzahl solcher Quadrate m = m ' - 1 ist . Dies ist der Fall, den wir weiter unten analysieren.m=2log2(n)m=m1

Das erste Quadrieren dauert , was zu einem o 1 = 2 log 2 ( n ) -Bit-Produkt führt. Das zweite Quadrieren nimmt zwei o 1 -Bit-Zahlen auf und läuft in t 2 = o 2 1- mal, was zu einem o 2 = 2 o 1- Bit-Produkt führt. Wenn Sie fortfahren, dauert der i- te Schritt t i = 4 i - 1 logt1=log22(n)o1=2log2(n)o1t2=o12o2=2o1iZeit und gibt einoi=2ilog2(n)-Bit-Produkt aus. Dieser Vorgang stoppt beimm-ten Schritt; Infolgedessen braucht es Zeitti=4i1log22noi=2ilog2(n)m

. Texp=[1..m]ti=log22(n)[1..m]4i=4m13log22n

Wenn die anfänglichen Quadrierungskosten enthalten sind, brauchen wir höchstens Zeit

Texp+log22n

Hinweis

  • Ich habe einige Böden und Decken in den Berechnungen weggelassen, in der Hoffnung, dass sie die Antwort nicht wesentlich beeinflussen würden.
  • O
  • OtiO(logn)
  • Die Multiplikationen können immer durch FFT und andere Methoden beschleunigt werden.
PKG
quelle
1
O(1)n2
4
nO(logn)O(1)
2
n2log2nn2log2nO(logn)
Fairer Punkt, ich werde zur Kenntnis nehmen
PKG
1
@ ThomasAndrews: Das hängt von der Maschine und dem Kostenmodell ab. Es ist nicht ungewöhnlich, ein RAM-Modell mit konstanten Kosten für Ergänzungen anzunehmen.
Raphael