mappa ridurre la complessità

Question

Consente crediate che io sia questo ingresso: un elenco di lista

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

(Mappa # (ridurre *% 1) lista-dei-list3)

La mappa-riduzione ha un O (n ^ 2) la complessità in questo caso?

viene mappa-Reduce tradotto come due nidificato per?

Così, quando ho eseguito l'esempio di cui sopra sul REPL clojure, la complessità temporale sembra O (n).

quando i duplicare il formato di ingresso (lista-di-list-6 (lista (1 2 3) (elenco 4 5 6) (elenco 7 8 9) (elenco 8 2 3) (elenco 9 8 1) ( elenco 7 6 4))) l'aumento tempo in modo lineare, non quadratica.

Qualcuno può dire perché?

grazie in anticipo

Answer 1

La mappa-riduzione ha una complessità O(n^2) in questo caso?

Impossibile da dire, a meno che non ci dite che cosa corrisponde n al nell'espressione list-of-list-3.

A proposito, O(n^2) o O(n*n) è complessità quadratica, non complessità esponenziale. complessità esponenziale è O(e^n).

quando i [doppio] la dimensione dell'input

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

l'incremento di tempo in modo lineare, non esponenziale.

Da questo, suppongo che la n dovrebbe essere la lunghezza della lista esterna. Se è così, allora il reduce è in realtà non O(n) O(n^2). Per ottenere la crescita quadratica, si avrebbe bisogno di definire list-of-list-6 come:

( 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

Non è O (n ^ 2), è più o meno O (n * m), dove n è il no di liste ed m è la lunghezza di loro. Ci saranno altri fattori a che fare con le lunghezze dei vari numeri. Farlo a mano e il tempo a voi stessi di capire il perché!