0
私はゲームの行を解決できるかどうかをチェックするアルゴリズムを持っています。ゲーム行は、最後の要素が0である正の整数の配列です。ゲームマーカはインデックス0から始まり、配置されている整数で示されるステップ数を配列に沿って移動します。再帰アルゴリズムの時間複雑さと空間の複雑さはどのようなものですか？オペレーター？
たとえば、[1,0,1]は[1、2、0]がfalseを返している間にtrueを返します。 マーカーは、ゲームを解決するために左右に移動することもできます。 つまり、[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）にもっと傾いています...
私は空間の複雑さについて、私はそれを見つける方法がありません。