问回溯算法的时间复杂度澄清

EN

我写了以下算法来解决一个经典的回溯问题:编写一个程序，它接受一个n个整数的数组，其中Ai表示您可以从索引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次(从range(1，L+1)开始运行一次)，最终得到O(L^2)。如果我在回答一个算法问题，或者甚至试图分析时间复杂度，说时间复杂度O(N)，因为时间复杂度与数组长度成比例，这似乎具有误导性，因为它没有考虑到输入的重要性。