योजना में इस कार्य की समय जटिलता क्या है?

Question

मैं थेटा नोटेशन में इस फ़ंक्शन की समय जटिलता को खोजने का प्रयास कर रहा हूं। अब, एन एक सकारात्मक पूर्णांक है, और lst 2 संख्याओं के साथ एक सूची है।

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

आप जानते हैं, संलग्न के समय जटिलता Θ (एन) जहां n सूचियों का कुल आकार है। मैंने यह देखने की कोशिश की कि क्या होता है यदि मैं संलग्न करता हूं और Θ (1) कार्यों के रूप में जमा करता हूं, तो मुझे मिलता है:

टी (एन) = 2 टी (एन -1) + Θ (1) जो है -> Θ (2^एन)

क्या इसका मतलब यह है कि थेटा नोटेशन में इस चीज़ की वास्तविक समय जटिलता Θ (2^एन) से बड़ी है?

मैं भी लगता है कि मैं अकेला इस धारणा के साथ सही हूँ, और वैसे भी, मैं अगर मैं विचार दोनों जमा होते हैं और संलग्न में लेने की जरूरत क्या करना है पर पता कर रहा हूँ नहीं कर रहा हूँ ...

मैं इस पर घंटों बर्बाद हो गए हैं, और मैं वास्तव में समझ में नहीं आता कि मैं इसे अपने आप क्यों नहीं समझ सकता ... किसी भी मदद की खुशी से सराहना की जाएगी।

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

Answer 1

यह प्रशंसनीय लगता है अगर तुम उत्पादन पर एक नज़र डालें:

btw, यहाँ जमा की कोड है।

(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 तत्वों के प्रत्येक तत्व के लिए एल * 2^एन बनाया गया है। एल्गोरिदम केवल खराब हो सकता है।

और जाहिर है यह बुरा है। समारोह संचित नहीं होता है इसलिए पूंछ रिकर्सिव और func नहीं है। एक 2^एन गैर पूंछ पुनरावर्ती समारोह काफी बेकार है।