使用||运算符的递归算法的时间复杂度和空间复杂度是多少？

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)

其他情况下给我的数字，我找不到与输入大小的关系，但是当我运行输入大小为n=100的程序时，输出会立即显示出来，所以我假设时间复杂度不是O（2^n）（像二进制递归）。我更倾向于O（n）…

至于空间的复杂性，我不知道如何找到它。

Answer 1

运行时确实更像O（n）。这是因为每个索引位置只调查一次（由于使用arrayList进行测试）。

确切的界限还取决于用于< code>arrayList的数据结构。它真的是一个< code>List还是一个< code>HashSet？

出于同样的原因，空间复杂度为 O（n）。每个索引位置只能有一个递归方法的化身。