Har*_*son 8 sorting algorithm recursion recurrence
我正在通过CLRS进行算法简介练习.这不是分级作业或任何东西,我只是想了解问题.
问题如下:
我们可以将插入排序表达为递归过程,如下所示.为了对A [1..n]进行排序,我们递归地对A [1..n-1]进行排序,然后将A [n]插入到排序的数组A [1..n-1]中.写一个递归版本的插入排序的运行时间的重复.
解决问题的方法:
由于在最坏的情况下花费O(n)时间将A [n]插入到排序的数组A [1中..n -1],如果n = 1则得到递归T(n)= O(1),如果n> 1则得到T(n-1)+ O(n).该复发的解决方案是T(n)= O(n ^ 2).
所以如果n = 1那么我得到它,那么它已经被排序,因此需要O(1)时间.但是我不理解重复的第二部分:O(n)部分是我们将被排序的元素插入到数组中的步骤,该数组在最坏的情况下采用O(n)时间 - 我们必须的情况遍历整个数组并在其末尾插入.
我无法理解它的递归部分(T(n-1)).T(n-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)