9

我正在做 CLRS 的算法介绍中的练习。这不是评分作业或任何东西，我只是想理解这个问题。

问题如下：

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

问题的解决方案：

因为在最坏的情况下将 A[n] 插入排序数组 A[1. .n -1]，我们得到递归 T(n) = O(1) 如果 n = 1 ， T(n-1)+ O(n) 如果 n > 1 。此递归的解决方案是 T(n) = O(n^2)。

所以我知道如果 n = 1，那么它已经排序，因此需要 O(1) 时间。但我不明白递归的第二部分：O(n) 部分是我们将要排序的元素插入到数组中的步骤，这在最坏的情况下需要 O(n) 时间——在这种情况下，我们必须遍历整个数组并在其末尾插入。

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

4

2 回答 2

10

是的，它来自：

为了对 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)

于 2013-09-15T02:54:10.293 回答
1

我将使用递归来解释我对插入排序的python代码的理解，如下所示：

def 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”值表示，同时还显示了所采取的步骤数。我们将步骤“insert_sort_r(A,n-1)”中对 (n-1) 个元素进行排序所用的时间表示为 T(n-1)，因为我们不知道这个值在 n 方面的确切含义。这就是递归的思想。用值为 (n-1) 时的情况来表示值为 n 时的情况的方程。

于 2018-01-08T21:13:13.457 回答