这个函数在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))))

如您所知,追加的时间复杂度为Θ(n),其中n是列表的总体大小.我试着看看如果我将append和accum积累为Θ(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)

对于 lst 的每个元素，都会创建 2^n 个元素，即 l*2^n。该算法只会更糟。

显然这很糟糕。函数accumulate 不是尾递归，因此func 也不是。2^n 非尾递归函数毫无用处。