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

Question

Я пытаюсь найти временную сложность этой функции в тета-нотации.Теперь 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 - общий размер списков.Я попытался увидеть, что произойдет, если я буду рассматривать добавление и накопление как Θ (1) функций, а затем получаю:

T (n) = 2T (n-1) + Θ (1), что ->Θ (2 ^ n)

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

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