現在、私は挿入ソートアルゴリズムの再帰バージョンを書くように割り当てられました。そして、私はそれをしました。実際、これは次のとおりです。
void recursiveInsertionSort(int* inputArray, int p, int q)
{
while (q > p)
{
recursiveInsertionSort(inputArray, p, q-1);
if (inputArray[q-1] > inputArray[q])
{
int temp = inputArray[q];
int temp2 = inputArray[q-1];
inputArray[q] = temp2;
inputArray[q-1] = temp;
q--;
}
}
}
私の問題は 2 つあります。まず、思いついた再帰関係が正しいかどうかわかりません。私が思いついた
T(n) = T(n-1) + T(n^2)
私の再帰関係として。そうですか？私はそれとちょうどの間で跳ね返っています
T(n) = T(n^2)
第二に、私は代数を使ってそれを証明することになっています
f(n) = ((n+1)n / 2)
その再帰関係を解きます。A. 自分の繰り返しが正しいかどうかわからないのと、B. 数学全般が苦手なときがあるからです。
問題のいずれかに関するヘルプは大歓迎です。
ありがとう。
よし、私は数学の教授の助けを借りてそれを理解することができました:P 他の人がそれを行う方法を知っているように、これをここに残しておきます. 誰かがこれを答えとしてコピーする必要があります:D
したがって、これの再帰関係は T(n) = T(n-1) + n である必要があり、私が最初に持っていたものではなく、それが主な問題でした。なんで？n-1 である再帰的な backtravel を実行するのにかかる時間です。なぜなら、n に行く場合、要素は 1 つしかなく、それはすでにソートされているからです。さらに、1 回の挿入または 1 回の実際の並べ替えにかかる時間。
それが n である理由は、そこに降りると、その前のすべての数字に対して 1 つの数字を n 回チェックしているためです。
では、その関数 f(n) が T(n) を解くことをどのように示しますか?
f(n) が T(n) を解くことはよく知られています。つまり、これを行うことができます：
We know that f(n) is equal to (n(n+1))/2 . So if T(n) is equal to T(n-1) + n, that means we take away 1 from every n in f(n) and then plug that into T(n).
That gives us T((n+1-)n-1)/2)) + n . That simplifies to T((n(n-1)/2) + n. Take that + n thats out there and multiply it by 2/2 to be able to have it all over a common denominator. Giving you (n^2 - n + 2n)/2 . Simplifies down to ((n^2) + n)/2 which further simplifies to, if you factor out an n, (n(n+1))/2. Which is f(n).
ウー！