Какова временная сложность этой функции в схеме?

Question

Я пытаюсь найти временную сложность этой функции в обозначениях Тэта. Теперь n является положительным целым числом, а lst - списком с двумя числами.

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

Как вы знаете, временная сложность Append является Θ (п), где п общий размер списков. Я попытался понять, что произойдет, если я обработаю append и накапливаю функции Θ (1), затем получаю:

T (n) = 2T (n-1) + Θ (1), который есть -> Θ (2^n)

Означает ли это, что фактическая временная сложность этой вещи в обозначениях Тэта больше, чем Θ (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. Алгоритм может быть только хуже.

И, очевидно, это плохо. Функция накапливается не хвост рекурсивный и func поэтому либо нет. 2^n не хвостовая рекурсивная функция совершенно бесполезна.