Bu İşlevin Şemadaki Zaman Karmaşıklığı nedir?

Question

Bu işlevin zaman karmaşıklığını Theta gösterimde bulmaya çalışıyorum. Şimdi, n pozitif bir tamsayı ve lst 2 sayı içeren bir listedir.

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

Bildiğiniz gibi

, append zaman karmaşıklığı Θ n listelerinin genel boyutudur (n) 'dir. Ben treat (1) işlevleri olarak ekleme ve birikir gibi davranırsanız ne olur görmeye çalıştım, o zaman -

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

Bu, Theta gösterisindeki bu şeyin gerçek zaman karmaşıklığının Θ (2^n) 'den daha büyük olduğu anlamına mı geliyor? Ben yalnız bu varsayımı ile Haklıyım ve her durumda, ben hem birikir ve ekleme dikkate almak gerekiyorsa yapılması gerekenler konusunda clueless olduğumu bile emin değilim

...

ben Bunun üzerine saat harcadım, ve neden bunu kendi başıma çözemediğimi anlamıyorum ... Herhangi bir yardım memnuniyetle karşılanacaktır. Eğer çıkışta bir göz atın eğer

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

Answer 1

Bu akla yatkın geliyor:

btw burada biriktiği kodudur.

(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 öğelerinin her öğesi için, l * 2^n olan oluşturulur. Algoritma sadece daha kötü olabilirdi.

Ve açıkçası kötüdür. Biriktirme, kuyruk özyineleme ve func değil, bu yüzden ya değil. 2^n olmayan kuyruk özyinelemeli işlevi oldukça kullanışsızdır.