この関数の時間複雑度はどのくらいですか？

Question

私はTheta記法でこの関数の時間複雑さを見出そうとしています。 ここで、nは正の整数で、lstは2つの数字を持つリストです。

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

ご存じのように、appendの時間の複雑さはΘ（n）です（nはリスト全体のサイズ）。 Θ（1）関数として追加して累積すると、何が起こるかを調べようとしました。

T（n）= 2T（n-1）+Θ（1） 2^n）

これは、Theta記法におけるこの事実の実際の時間複雑さがΘ（2^n）よりも大きいことを意味しますか？私は一人で、この前提で、右だし、とにかく、私は両方が蓄積し、追加を考慮に入れる必要がある場合に何をすべきかについて無知だということさえわからない

...

Iこれで何時間も無駄になってしまったのですが、どうして私が自分でそれを理解することができないのか分かりません。 助けてくれれば嬉しいです。

ところで、ここでの累積のコードは次のとおりです。

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

Answer 1

あなたは出力を見ている場合それは、もっともらしく聞こえます。

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

lst 2^n要素のすべての要素がl * 2^nで作成されます。アルゴリズムは悪化する可能性があります。

明らかに悪いです。関数accumulateは末尾再帰型ではなく、関数funcはそうではありません。 2^nの非テール再帰関数は全く役に立たない。