Qual è la complessità temporale di questa funzione in Scheme?

Question

Sto cercando di trovare la complessità temporale di questa funzione nella notazione Theta. Ora, n è un numero intero positivo, e lst è una lista con 2 numeri.

(define (func n lst) 
    (if (= n 0) lst 
     (accumulate append null 
        (map (lambda (x) 
         (func (- n 1) (list x x))) 
         lst)))) 

Come sapete, la complessità temporale di accodamento è Θ (n), dove n è la dimensione complessiva delle liste. Ho provato a vedere cosa succede se tratto App e accumulo come Θ (1) funzioni, poi ottengo:

T (n) = 2T (n-1) + Θ (1) che è -> Θ (2^n)

Ciò significa che la complessità temporale attuale di questa cosa nella notazione Theta è molto più grande di Θ (2^n)?

io non sono nemmeno sicuro che ho ragione con questo assunto da solo, e in ogni modo, io sono all'oscuro su cosa fare se ho bisogno di prendere in considerazione sia accumulano e aggiungere ...

I Ho perso ore su questo, e davvero non capisco perché non riesco a capirlo da solo ... Qualsiasi aiuto sarebbe gradito.

btw, ecco il codice di accumulo:

(define (accumulate op init lst) 
    (if (null? lst) 
     init 
      (op (car lst) 
      (accumulate op init (cdr lst))))) 

Answer 1

Sembra plausibile, se si dà un'occhiata in uscita.

(func 3 (list 1 2 3)) 
=> (1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3) 

Per ogni elemento di lst 2^n vengono creati elementi che è l * 2^n. L'algoritmo potrebbe essere solo peggio.

E ovviamente è male. La funzione accumula non è ricorsiva della coda e quindi non funziona. Una funzione ricorsiva non a coda 2^n è abbastanza inutile.