以下 python 代码的时间复杂度是多少

Question

def lcs(X,Y,i,j):
  if (i == 0 or j == 0):
    return 0
  elif X[i-1] == Y[j-1]:
    return 1 + lcs(X,Y,i-1,j-1)
  else:
    return max(lcs(X,Y,i,j-1),lcs(X,Y,i-1,j))

def lcs(X,Y,i,j):
  if c[i][j] >= 0:
    return c[i][j]
  if (i == 0 or j == 0):
    c[i][j] = 0
  elif X[i-1] == Y[j-1]:
    c[i][j] = 1 + lcs(X,Y,i-1,j-1)
  else:
    c[i][j] = max(lcs(X,Y,i,j-1),lcs(X,Y,i-1,j))
  return c[i][j]

第二个比第一个运行得更快。但是我发现他们的时间复杂度和O(N2)一样。

Answer 1

第一个函数的复杂度呈指数级增长。每个递归调用都会进行 2 次新的递归调用。许多值被计算不止一次。这是一个经典的“陷阱”，例如在为 Fibonacci 函数编写代码时经常遇到。

第二个函数是第一个函数的“记忆”版本。所有计算的值都存储在tablec中，以避免重新计算它们。因此，双重递归调用 max(lcs(X,Y,i,j-1),lcs(X,Y,i-1,j)) 不会增加递归调用的数量，因为大多数递归调用会立即终止，“哦，这个值已经计算出来了，它在 table 中”。

以下 python 代码的时间复杂度是多少

What is the time complexity of the following python codes

python

recursion

time-complexity