具有递归和循环的程序的时间复杂度

Question

根据可变的循环限制调用f时，时间复杂度是多少？

示例代码：

def rec(i,j,k,n):
for h in range(1,j):
f(i,j,k,h)// function call O(1)
if k<=n:
rec(i+1,j+i+1,k+j+1,n)
else:
pass

使用 i=0，j=0，k=0 并传递 n 调用的程序

rec(0,0,0,n)

Answer 1

i

随调用深度线性增长。ji积分，因此随调用深度二次增长k集成了j，因此随着调用深度的增大而增长。

因此，达到的最大深度为Θ(n^(1/3((

还有深度>n^1/3/2的Θ(n^1/3(调用，使其使其他调用相形见绌。

这些调用在循环中每次占用 Θ(n^2/3( 时间，因此最终复杂度为 Θ(n^1/3* n^2/3( = Θ(n(

所以这很棘手，但需要线性时间。 不过，你真的应该做一个实验来确保。