Integer Zeit Komplexität in Haskell

Question

Ich hatte eine Aufgabe in der Schule letzte Woche, um eine Funktion zur Berechnung der n: th-Nummer in der Fibonacci-Sequenz zu implementieren. Eine 'Sub-Zuweisung' bestand darin, sie unter Verwendung von Akkumulation (möglicherweise keine korrekte Übersetzung) zu implementieren, um der Funktion O (n) Zeitkomplexität zu geben. Das alles hat gut funktioniert, bis ich versuchte, die Funktion zu machen (Int -> Integer). Indem ich ein bisschen experimentierte, erkannte ich, dass die Zeitkomplexität nahe bei O (n^2) für wirklich große Zahlen war. Es kommt mir vor, dass dies wegen der Integer-Implementierung sein muss, was mich ein bisschen neugierig macht, wie es funktioniert. Ich habe ein paar Google-Suchen durchgeführt und nichts gefunden, was nützlich schien, also wende ich mich an euch, in der Hoffnung, entweder eine Erklärung oder einen Link zu bekommen, der es gründlich erklärt.

Mein Code:

ackfib 0 = 0 
ackfib 1 = 1   
ackfib n = loop n 1 0 1 
    where 
     loop n n1 n2 i 
      | i < n  = loop n (n1+n2) n1 (i+1) 
      | i == n = n1 
      | i > n  = error "n must be greater than or equal to 0" 

ich für alle dankbar bin Antworten

Viktor

Answer 1

Das hat nichts mit Haskell zu tun hat, wirklich, es ist nur eine Folge der Tatsache, dass die Fibonacci-Zahlen wachsen exponentiell schnell. Genauer gesagt hat die n-te Fibonacci-Zahl ungefähr (φ) n oder ungefähr 0,48 n Bits, wobei φ das goldene Verhältnis (1 + sqrt 5)/2 ist. Da die Addition von k-Bit-Ganzzahlen O (k) -Zeit benötigt, Ihre O (n) -Zusätze benötigen tatsächlich eine O (n^2) -Zeit, da die von Ihnen hinzugefügten Zahlen im Durchschnitt 0 (n) Bits haben.

(Hinweis für Pedanten. Großes O wirklich große Theta in der oben sein soll)

Answer 2

-Reid's answer hinzuzufügen, die Tatsache, dass Ihr Algorithmus O (N) Zeitkomplexität hat, hängt von was Sie als das sein Schritt der Ausführung. Dies ist ein häufiges Missverständnis der zeitlichen Komplexität: Diese zeitliche Komplexität entspricht immer der Ausführungszeit.

Der Schritt hängt davon ab, wie tief wir das Problem analysieren möchten. Wenn Sie einen Schritt als eine Addition von Integer definieren, ja, wird Ihr Algorithmus mit Akkumulatoren in O (N) -Zeit ausgeführt. Wenn Sie einen Schritt als Addition von einem Wort (eine 32- oder 64-Bit-Addition) definieren, wird er in O (N^2) ausgeführt, wie Reid erklärt.

Wenn Sie möchten, dass Ihre Komplexitätsanalyse der Ausführungszeit entspricht, müssen Sie einen Ausführungsschritt verwenden, dessen Ausführungszeit oben durch eine Konstante begrenzt ist, wie das Hinzufügen von zwei Prozessorwörtern. Addition von Ganzzahlen ist nicht, da Ganzzahlen beliebig groß sein können.