Độ phức tạp thời gian của hàm này trong sơ đồ là gì?

Question

Tôi đang cố gắng tìm độ phức tạp thời gian của hàm này trong ký hiệu Theta. Bây giờ, n là một số nguyên dương và lst là một danh sách có 2 số.

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

Như bạn đã biết, thời gian phức tạp của phụ thêm là Θ (n) trong đó n là kích thước tổng thể của danh sách. Tôi đã cố gắng để xem điều gì sẽ xảy ra nếu tôi xử lý phụ thêm và tích lũy dưới dạng hàm Θ (1), sau đó tôi nhận được:

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

Điều này có nghĩa là độ phức tạp thời gian thực của điều này trong ký hiệu Theta có lớn hơn Θ (2^n) không?

Tôi thậm chí không chắc chắn rằng tôi đúng với giả thiết này một mình, và dù sao, tôi tránh khỏi thất bại trên phải làm gì nếu tôi cần phải đi vào xem xét cả tích lũy và thêm ...

tôi đã lãng phí thời gian trên này, và tôi thực sự không hiểu tại sao tôi không thể tìm ra nó trên của riêng tôi ... Bất kỳ trợ giúp sẽ được vui vẻ đánh giá cao.

btw, đây là mã của tích lũy:

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

Answer 1

Nghe có vẻ hợp lý, nếu bạn có một cái nhìn tại đầu ra.

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

Đối với mọi thành phần của phần tử 2^n được tạo là l * 2^n. Thuật toán chỉ có thể tồi tệ hơn.

Và rõ ràng là xấu. Hàm tích lũy không phải là đệ quy đuôi và func do đó không. Hàm đệ quy 2^n không đuôi khá vô ích.