Karte reduzieren Komplexität

Question

Läßt nehmen, dass ich diese Eingabe haben: eine Liste der Liste

(def list-of-list-3 (Liste (Liste 1 2 3) (Liste 4 5 6) (list 7 8 9)))

(Karte # (reduzieren *% 1) list-of-list3)

die Karten reduzieren hat eine O (n^2) Komplexität in diesem Fall?

ist map-reduce übersetzt als zwei verschachtelt für?

Also, wenn ich das obige Beispiel auf der Clojure REPL ausführen, scheint die Komplexität Zeit wie O (n).

wenn ich die Eingabegröße dupliziere (Liste-Liste-6 (Liste (Liste 1 2 3) (Liste 4 5 6) (Liste 7 8 9) (Liste 8 2 3) (Liste 9 8 1) (Liste 7 6 4))) Die Zeit steigt linear, nicht quadratisch.

Kann jemand sagen warum?

Dank im Voraus

Answer 1

Die Map-reduzieren hat eine O(n^2) Komplexität in diesem Fall?

Unmöglich zu sagen, es sei denn, Sie sagen uns, was n in dem Ausdruck list-of-list-3 entspricht.

Übrigens, O(n^2) oder O(n*n) ist quadratische Komplexität, nicht exponentielle Komplexität. Exponentielle Komplexität es O(e^n).

wenn i [double] die Eingangsgröße

(list-of-list-6 (list (list 1 2 3) (list 4 5 6) (list 7 8 9) 
         (list 8 2 3) (list 9 8 1) (list 7 6 4))) 

erhöhen die Zeit in einer linearen Art und Weise, nicht exponentiell.

Davon vermute ich, dass die n die Länge der äußeren Liste sein soll. Wenn ja, dann ist die reduce eigentlich O(n) nicht O(n^2). Um quadratisches Wachstum zu bekommen, müßten Sie definieren list-of-list-6 als:

(list-of-list-6 (list (list 1 2 3 4 5 6) (list 4 5 6 1 3 2) 
         (list 7 8 9 1 2 3) (list 8 2 3 2 3 4) 
         (list 9 8 1 2 3 4) (list 7 6 4 5 6 7))) 

Answer 2

Es ist nicht O ist (n^2), ist es in etwa O (n * m), wobei n die Anzahl der Listen und m ist die Länge von ihnen. Es gibt noch andere Faktoren, die mit den Längen verschiedener Zahlen zu tun haben. Tun Sie es von Hand und Zeit sich selbst zu sehen, warum!