我试图在Theta表示法中找到此函数的时间复杂度.现在,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是列表的总体大小.我试着看看如果我将append和accum积累为Θ(1)函数会发生什么,然后我得到:
T(n)= 2T(n-1)+Θ(1),它是 - >Θ(2 ^ n)
这是否意味着Theta表示法中该事物的实际时间复杂度大于Θ(2 ^ n)？
我甚至不确定我是否对这个假设是正确的,无论如何,如果我需要考虑累积和追加,我对如何做是一无所知......
我在这个上浪费了几个小时,我真的不明白为什么我不能自己解决这个问题...任何帮助都会很高兴.
顺便说一句,这是累积的代码:
(define (accumulate op init lst)
(if (null? lst)
init
(op (car lst)
(accumulate op init (cdr lst)))))