python - 回溯算法的时间复杂度说明

Question

我写了下面的算法来解决一个经典的回溯问题:写一个程序，它接受一个 n 个整数的数组，其中 A[i] 表示你可以从索引 i 前进的最大值，并返回是否可以前进到从数组开头开始的最后一个索引。

换句话说，A 中的第 i 个条目是我们可以从 i 前进的最大值。

例如，如果 A = [3, 3, 1, 0, 2, 0, 1]，则可以到达最后一个索引。如果 A = [3, 2, 0, 0, 2, 0, 1]，则不能。

我写了下面的代码:

from collections import defaultdict 
def array_advance(lst):
  dict = defaultdict(lambda: 0)
  return advance(0, lst, dict)

def advance(start_idx, lst, memo):
  if start_idx >= len(lst): return False 
  if start_idx == len(lst) -1: return True 
  step_size = lst[start_idx]
  for i in range(1, step_size + 1):
    memo[step_size] |= advance(start_idx + step_size, lst, memo)
    if memo[step_size]:
      return True 
  return False

通过这段代码，我了解到只有 N 次函数调用。如果我们内存，每个索引都会被访问并且函数(索引)输出被缓存。

但是，我无法理解时间复杂度。关于输入的大小，时间复杂度当然与 O(N) 成比例。但是，输入的内容也很重要。例如，如果每个元素是 L，并且输入的大小是 10L，则 for 循环将以 O(L) 缩放，运行 L 次(从范围 (1, L + 1) 开始一次)，导致 O(大号 ^ 2)。如果我正在回答一个算法问题，或者甚至试图分析时间复杂度，说时间复杂度为 O(N) 因为时间复杂度与数组长度成比例似乎具有误导性，因为它没有考虑输入的重要性。

Answer 1

假设步长永远不会超过数组，您可以说它是 O(sum(A))，因为这是一个考虑到数组元素的严格界限。您也可以说它是 O(N^2)，因为这是最坏的情况。

您可以通过向后遍历数组并记录到目前为止找到的最少索引来解决问题，时间复杂度为 O(N)，空间复杂度为 O(1)。

def array_advance(a):
    i = len(a) - 1
    for j in range(i, -1, -1):
        if j + a[j] >= i: i = j
    return i == 0