Какова временная сложность и пространственная сложность рекурсивного алгоритма с || оператор?

Question

У меня есть алгоритм, который проверяет, может ли решаться строка игры. Строка игры представляет собой массив положительных целых чисел, где последний элемент равен 0. Маркер игры начинается с индекса 0 и перемещает вдоль массива количество шагов, указанных целым числом, на котором оно расположено.

Например, [1, 1, 0] возвращает true, а [1, 2, 0] возвращает false. Маркер также может перемещаться влево или вправо, чтобы решить игру. То есть [3, 3, 2, 2, 0] разрешима.

Algorithm recursiveSolvable(gameArray, index) 
    if index = gameArray.length - 1  // the last element has been reached 
      return true 
    if index < 0 || index >= gameArray.length || arrayList.contains(index) 
      return false 
    arrayList.add(index)  // store visited indices to avoid infinite loop 
    else 
      // move towards the goal (last element) if possible 
      // otherwise, trace back steps to find another way 
      return recursiveSolvable(gameArray, index + gameArray[index]) 
       || recursiveSolvable(gameArray, index - gameArray[index]) 

Я попытался несколько примеров игровых строк и вычислили временную сложность в худшем случае:

[2, 0] has 2 recursive calls where the first one returns false, and the second one as well 
[1, 1, 2, 0] has 5: 
    go right || go left - false 
     | 
    go right || go left - false 
     | 
    go right || go left - false (because index 0 has been visited) 
     | 
     false (then go left) 

Другие случаи дали мне номера, которые я не мог найти связь с входом size, но когда я запускаю программу с размером ввода n = 100, вывод отображается мгновенно, поэтому я предполагаю, что временная сложность не O (2^n) (например, двоичная рекурсия). Я больше склоняюсь к O (n) ...

Что касается сложности пространства, я понятия не имею, как его найти.

Answer 1

Время выполнения действительно больше похоже на O (n). Это связано с тем, что каждое положение индекса исследуется только один раз (из-за теста с arrayList).

. Точная граница также зависит от структуры данных, используемой для arrayList. Действительно ли это List или HashSet?

Сложная сложность O (n) по той же причине. Для каждой позиции индекса может быть только одно воплощение рекурсивного метода.