mapa reducir la complejidad

Question

vamos a suponer que tengo esta entrada: una lista de la lista

(def lista-de-list-3 (lista (lista 1 2 3) (lista 4 5 6) (lista 7 8 9)))

(mapa # (* reducir% 1) de lista de list3)

El mapa-reducir tiene un O (n ^ 2) la complejidad en este caso?

es el mapa-Reducir traduce como dos anidado para?

Así que cuando corro el ejemplo anterior en el REPL clojure, el tiempo parece que la complejidad O (n).

cuando i duplicar el tamaño de entrada (6 lista-de-list-(lista (lista 1 2 3) (lista 4 5 6) (lista 7 8 9) (lista 8 2 3) (lista 9 8 1) ( lista 7 6 4))) el aumento de tiempo de una manera lineal, no cuadrática.

Puede alguien decir por qué?

gracias de antemano

Answer 1

El mapa-reducir tiene una complejidad O(n^2) en este caso?

imposible decir, menos que nos diga lo que corresponde a n en la expresión list-of-list-3.

Por cierto, O(n^2) o O(n*n) es la complejidad cuadrática, no complejidad exponencial. complejidad exponencial que O(e^n).

cuando i [doble] el tamaño de entrada

( 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)) )

el aumento de tiempo de una manera lineal, no exponencial.

A partir de esto, yo conjeturan que el n se supone que es la longitud de la lista externa. Si es así, entonces el reduce es en realidad no O(n) O(n^2). Para conseguir el crecimiento cuadrática, lo que se necesita para definir list-of-list-6 como:

( 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

No es O (n ^ 2), que es más o menos O (n * m) donde n es el no de listas y m es la longitud de ellos. Habrá otros factores también que ver con las longitudes de varios números. Hacerlo a mano y el tiempo usted mismo para ver por qué!