このアルゴリズムを別の投稿から取得しただけですが、このアルゴリズムの計算方法を知る必要がありtemporal complexity
ますか? 私は学生で、やり方がよくわかりません。
public static void getSum(int[] numbersArray, int starting, int sum)
{
if(numbersArray.length == starting)
{
// Now we print sum here
System.out.println(sum);
return;
}
int value = sum + numbersArray[starting];
getSum(numbersArray, starting + 1, value);
getSum(numbersArray, starting + 1, sum);
}
numbersArray
長さが 5 であるとします。誰かがこれをstarting
= 0 で呼び出す、つまりgetSum(numbersArray, 0, 0)
. 今:
これはgetSum(numbersArray, 1, x)
2 回呼び出します。
の各呼び出しは2 回getSum(numbersArray, 1, x)
呼び出しますgetSum(numbersArray, 2, x)
。
の各呼び出しは2 回getSum(numbersArray, 2, x)
呼び出しますgetSum(numbersArray, 3, x)
。等々。
に到達するgetSum(numbersArray, 5, x)
と、時間は一定です。baseTimeと呼びましょう。
T(n) が実行時間であるとしgetSum(numbersArray, n, x)
ます。T(5) はbaseTimeです。T(4) = 2*T(5); T(3) = 2*T(4); 等々。これは、呼び出し全体の時間 T(0) = 2*T(1) = 2*2*T(2) = 2*2*2*T(3) = 2*2*2*2* T(4) = 2*2*2*2*2*T(5) = 2*2*2*2*2* baseTime。これが示すことは、アルゴリズムの時間は 2 mに比例するということです。ここで、mは配列の長さです。したがって、答えは O(2 m )と書かれます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加