Разъяснение сложности времени по алгоритму возврата

Question

Я написал следующий алгоритм для решения классического вопроса о возврате: напишите программу, которая принимает массив из n целых чисел, где A [i] обозначает максимум, который вы можете продвинуться по индексу i, и возвращает, можно ли перейти к последний индекс, начинающийся с начала массива.

Другими словами, i-я запись в A - это максимум, который мы можем продвинуть из 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 ( L ^ 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