递归插入排序的运行时间的递归

Question

目前，我被分配编写插入排序算法的递归版本。我就这么做了。事实上，这是这样的：

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--;
     }
  }
}

我的问题是双重的。首先，我不确定我提出的递归关系是否正确。我想出了

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，因为如果你要转到 n，你将只有一个元素，并且已经排序。加上进行一次插入或一次实际排序所需的时间。

之所以是 n 是因为当你到达那里时，你正在将一个数字与它之前的每个数字进行检查，这恰好是 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).

哇！