scheme - Scheme中此功能的时间复杂度是多少？

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是列表的整体大小。我试图看看如果我将append和累加作为Θ(1)函数会发生什么，那么我得到:

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

这是否意味着该事物在Theta表示法中的实际时间复杂度远大于Θ(2 ^ n)？

我什至不确定仅凭此假设我是对的，无论如何，如果我需要同时考虑累加和追加，我对如何做一无所知。

我在这上面浪费了很多时间，我真的不明白为什么我不能自己解决这个问题...
任何帮助将不胜感激。

顺便说一句，这是累加的代码:

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

对于第一个元素，将创建2 ^ n个元素，即l * 2 ^ n。该算法只会更糟。

显然这是不好的。该函数累加不是尾递归的，因此func也不是。 2 ^ n非尾递归函数是完全没有用的。