理解算法时间复杂度中的“递归”

Question

我正在做CLRS的算法导论练习。这不是评分作业或其他什么，我只是想理解问题。

问题如下：

我们可以将插入排序表示为以下递归过程。为了对A[1..n]进行排序，我们递归地对A[1..n-1]进行排序，然后将A[n]插入到已排序的数组A[1..n-1]中。编写此递归版本的插入排序的运行时间的递归式。

问题的解决方案：

由于在最坏情况下将A[n]插入已排序的数组A[1. .n−1]需要O(n)时间，因此如果n=1，则得出递归式T(n)=O(1)，否则为T(n−1)+O(n)。解决此递归式的方法是T(n)=O(n^2)。

所以我知道如果n=1，则它已经排序，因此需要O(1)时间。

但我不理解递归部分（T(n-1)）。 T(n-1)是否意味着每次递归调用时，我们都会对数组的一个元素进行排序？这似乎不正确。

- Harrison

Answer 1

是的，它来自于：

为了对A[1..n]进行排序，我们先递归地对A[1..n-1]进行排序，然后再将A[n]插入到已排好序的数组A[1..n-1]中。

"递归地对A[1..n-1]进行排序"部分需要T(n-1)的时间（这很容易理解：我们定义T(n)为“排序n个元素所需的时间”，因此排序n-1个元素所需的时间是显而易见的T(n-1)），而“将A[n]插入到已排好序的数组A[1..n-1]中”部分最坏情况下需要O(n)的时间。将它们相加得到：

T(n) = T(n-1) + O(n)

- Tim Peters

Answer 2

我将使用Python代码解释递归插入排序的理解如下：

def insert_sort_r(A,n)

意思是定义一个名为insert_sort_r的函数，它接受两个参数A和n。

if n==1:

    pass

else:------------------------------------ c1
    insert_sort_r(A,n-1) ---------------- T(n-1)

    key = A[n-1]------------------------- c2
    i = n-2 ------------------------------c3

    while i>-1 and A[i] > key:------------c4*(n)
        A[i+1] = A[i]---------------------c5*(n-1)
        i = i-1---------------------------c6*(n-1)
    A[i+1] = key--------------------------c7

每个步骤所需的时间由“c”值表示，同时还显示了所采取的步骤数。我们将排序（n-1）个元素所需的时间在步骤“insert_sort_r(A，n-1)”中表示为T（n-1），因为我们不知道这个值与n的关系是什么。这就是递归的思想。表示值为n时的方程式与值为（n-1）时的情况相同。

- CASE

---

这个答案有点混乱。格式混乱，不清楚你想表达什么。 - user1531971

请指出您没有理解的部分，以便我可以详细说明。 - CASE

希望格式现在清晰了。所以问题是他不理解n>1的情况。对于n>1，运行时间公式中有两个部分。一个是T(n-1)，另一个是O(n)。所以我展示了如何用Python代码来说明这两个部分的生成过程。并且一旦你解决了这个递归问题，就会发现它的解是一个二次多项式，这就是为什么总运行时间是O(n^2)的原因。希望现在您已经明白了。如果您想看看递归是如何被解决的，请让我知道。 - CASE

请仅翻译以下有关编程的内容，不需要注释或解释。即不要向“我”解释，而是向“每个人”解释。 - user1531971

这正是我在正文中解释的内容。既然你理解有困难，我就进一步阐述了它。如果其他人也有理解上的困难，我会在正文中包含同样的内容。 - CASE